인공지능과 시뮬레이션

 Search Method

1. Basic Search

   1. Blind Search: Search tree를 만든 후, (모든 경우가 탐색 가능 ==> 너무 많은 시간 소요)

      1. DFS: 깊이 우선으로 탐색 (Local Max에 빠질 가능성)
      2. BFS: 너비 우선으로 탐색 (너무 많은 시간 소요)

   2. Heuristic Search: Search tree에서 경험에 의한 기대치를 반영 ==> 시간 개선을 위해

      1. Hill-Climb(DFS with weight): 각 노드에 경험에 의한 가중치를 부여한 후 우선하여 검색 (local max에 빠질 가능성, 방향전환의 어려움, 평평한 고원 문제)
      2. Beam(BFS with weight): level로 확장한 후 확장된 곳에서 노드의 경험적 가중치를 기반으로 w만큼 선택, 이 과정을 goal를 찾을 때까지 반복
      3. Best First: 어떠한 휴리스틱에 따라서 최근의 모든 경로들을 순서화하여 DFS를 최적화하는 탐색 알고리즘 (???)

2. Optimal Search

   1. British Museum:
   2. Branch and Bound: branch(노드 확장)한 후 확장된 노드 중 가장 좋은 노드로 bound, goal을 찾을 때까지 이 과정을 반복
   3. Branch and Bound with Underestimates: B&B의 과정을 휴리스틱 가중치를 합산하여 적용
   4. A*: 3번 방법(B&B with U)에 Dynamic Programming Principle를 적용한 방법

#. Dynamic Programming Principle: 노드 탐색시 같은 이름의 노드가 존재하면 효율적인 하나만 확장

(예) S-A-D(8) S-D(4)이면 D까지 가는데 후자가 4만큼의 비용이 절약되므로 전자는 고려하지 않음

 

Rule Based Expert System

1. 개   요

E.S

  |

----------------------------

|                                       |

 Knowledge Base                Inference Engine

|

 -------------------------

|                                    |

    Rule                      Facts, Assertions

 

예) A toy deduction system identifies animals: 사용자와 system이 질의응답을 통해 어떤 동물인지 알아내는 것

1. Inference Engine

   1. Forward Chaining: Facts, Assertions과 Rule을 이용한 Inference Engine을 기반으로 사실을 찾아내는 방법 (Bottom-Up)

      1. A Toy Deduction System Identifies Animals
         "우유를 주다"  ==> If x가 우유를 준다 then x는 포유동물 이다
         "chews cud(되새김질을 하다)" ==> If x가 표유동물이고 되새김질을 한다 then x는 발굽을 가진 유제동물이다
         "다리가 길다", "목이 길다', "황갈색이다", "얼룩 점이 있다" ==> If x가 발굽을 가진 유제동물이고, 다리와 목이 길고, 황갈색에 얼룰점이 있다. then x는 기린이다
      2. A Toy Reaction System Bags Groceries
         
   2. Backward Chaining: 사실이 주어지고 그 사실이 되기위한 조건을 찾아가며 검증하는 방법 (Top-Down)
      

2. Conflict Resolution Strategies

   1. Rule Ordering: Rule에 우선순위를 두라
   2. Context Ordering: 특정 상황에 맞는 Rules를 그룹화 해라
   3. Specificity Ordering: Superset of the conditions of triggered rule을 이용하라 (???)
   4. Data Ordering: 어떤 우선순위된 list에서 가능한 모든 assertions를 정렬하고 가장 우선순위가 높은 assertions를 이용하라 (???)
   5. Size Ordering: 조건(conditions)의 수가 많은 rule을 사용하라
   6. Recency Ordering: Use the least recently used rule

 

Simulation Methodology

1. Simulation System Classification

   1. Discrete (time) simulation
   2. Continuous (time) simulation
   3. Discrete event simulation

 

 

이 글은 스프링노트에서 작성되었습니다.