본문 바로가기

Study

인공지능과 시뮬레이션

 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

 

 

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

'Study' 카테고리의 다른 글

Web Information System  (0) 2012.08.25
Real-time System  (0) 2012.08.25
Sigmoid Function  (0) 2012.08.25
Reality Mining  (0) 2012.08.25
Ontology  (0) 2012.08.25