[인공지능] 3. Solving problems by searching - 1
1. Problem-Solving Agents
1) Problem Formulation
- Problem은 initial state, actions, transition model, goal test, path cost로 정의된다.
- Problem formulation은 goal이 주어진 상황에서, 무슨 action 과 states를 고려할 것인지 결정하는 과정을 말한다.
- Problem의 solution은 initial state가 goal state로 가게 만드는 action들의 sequence이다.
- goal에 다다르기 위한 sequence of actions을 찾아나가는 과정이 search이다.
- solution이 찾아지면 action이 수행되도록 추천된다. 이것이 바로 execution이다.
* State Space : initial state에서부터 어떤 action squence를 통해 도달할 수 있는 모든 states들의 집합
* path : sequence of actions에 의해 연결된 states들의 sequence
2). Abstraction (추상화)
: representation에서 detail을 제거해나가는 과정이 abstraction이다. Abstraction은 우리가 어떤 abstract solution을 더 detailed 한 환경에서 solution으로 확장시킬 수 있다면 valid하다. Abstraction은 원래의 문제보다 solution에 있는 각각의 actions들을 수행하는 것이 더 쉬울 경우에 유용하다. 따라서 더 좋은 abstraction을 하기 위해서는, validity를 유지하고 abstract action이 수행하기 쉽도록 유지하면서도 가능한 많은 detail을 제거해야 한다.
2. Example Problems
3. Searching for Solutions
1) Search Tree
- Solution은 action sequence의 형태로 나타남. 그래서 search 알고리즘은 여러가지 가능한 action sequences들을 고려하여 작동한다.
- 모든 가능한 action sequence는 initial state에 시작하는데, search tree에서는 그게 바로 root!!
- branches는 각각 action이고 nodes는 state space에 속하는 state에 해당한다.
2) Search Strategy and Performance Evaluation
i. Search Strategy
- First-in first-out (FIFO)
- Last-in first-out (LIFO)
- Highest priority first
ii. Performance evaluation
- Completeness
- Optimality
- Time complexity
- Space complexity