Search Tree, Tree search, Graph search

A Search Tree

- 문제를 형식화 한 뒤, 문제를 풀어야 한다.

- 이때, solution 은 하나의 action sequence인데, 이 동작열을 찾기 위해 검색 알고리즘을 사용한다.

- 검색 알고리즘은 가능한 여러 sequence 들을 살펴본다.

- Initial state -> root

- actions -> branches

- states -> nodes

 

 

 

Tree Search

- initial state을 현재 state 로 설정한다.

- Iterate

• 현재 state 가 Goal 인가?
  • 그렇다면, 지금까지 찾은 solution (action sequence) 를 리턴
• 아니라면 가능한 action 들을 고려한 뒤 EXPAND
• 액션 선택
• 선택한 action 으로 파생된 state 를 현재 state 로 지정한 뒤 반복

- 예시 / Romania 문제

 

(a) : initial state 를 현재 state 로 설정, goal 인지 확인 -> NO -> EXPAND

(b) : Arad 를 확장 후 action 선택

(c) : 파생된 state 인  Sibiu 를 현재 state 로 지정하고, Sibiu 가 Goal 인지 확인 -> NO -> EXPAND

 

 

Tree Search Algorithm

- Expanding 작업은 solution 을 찾거나, 더이상 확장할 state 가 없을 때까지 계속한다.

- Frontier : Expansion 이 가능한 모든 노드들의 집합

 

1. initial state 를 현재 state 로 지정, 현재 state 로 frontier 초기화

2. frontier 에서 노드를 하나 뺌

3. node 가 goal state 라면 리턴

4. 아니라면, 그 노드를 expand 하고 새로 파생되는 노드들을 frontier 에 추가

 

 

Loopy Paths

- Tree Search 의 문제점으로, redundant paths 가 발생하면 사이클이 생겨 무한루프가 생길 수 있다.

이런 경우 step cost 가 음수가 아닌 경우에 path cost 가 계속 증가된다는 문제가 발생한다.

(c) 에서 Sibiu 를 expand 하고, 파생되는 4개의 노드들을 frontier에 추가한다.

다음으로 frontier 에서 Arad를 선택하는 경우 loop 가 생기는 것이다.

 

- Redundant Path example

 

 

 

Search in a Rectangular Grid

- Search tree 의 깊이 d는 4^d 의 leaves 를 가진다.

- 그러나, 중복되는 state 때문에 실제로는 2d^2 에 가깝다.

2d x d x 1/2 x 2 = 2d^2

 

 

 

Graph Search

- Tree search 의 loopy path 문제를 해결하기 위해 expand 한 모든 노드들에 대한 정보를 저장하는 검색 방법이다.

- 따라서 한번 방문한 state 는 절대 다시 방문하지 않아서, 중복이 발생하지 않는다.

- tree search 와 달라진 점

1. add the node to the explored set : expand 된 노드들 (방문한 노드) 을 모두 저장해 둔다.

2. only if not in the frontier or explored set : 이미 frontier 나 explored set 에 들어있는 노드라면 추가하지 않는다

 

즉, 모든 state 는 무조건 frontier 를 거친 뒤, explored set 에 들어가게 된다

 

- search in the state space

All states -> frontier -> explored set 이 순서를 거쳐서 explored set 에 들어갈 수 있다.

 

 

 

Node Structures

• Node.state
• Node.parent
• Node.action,
• Node.path-cost

-> Goal 을 찾았을 때 재귀적으로 route 를 복원하고 cost 를 알아낼 수 있다.

-위 그림에서 현재 node 는 initial node 로 부터 6번을 거쳐서 온 것을 알 수 있다.

 

 

 

Data Structures

- Node vs states : 여러 노드는 같은 state 를 가질 수 있다.

- Frontier

• Queue
• FIFO(선입선출), LIFO(후입선출)
• Priority queue (우선순위 큐)

- Explored set -> Hash table

 

 

 

Evaluation of Serach Algorithms

검색 알고리즘의 성능 평가 지표는 다음과 같다.

- Completeness : 정답이 있다면 무조건 찾아내는가? (solution 이 있다면 반드시 찾고 종료하는지, 무한루프인지)

- Optimality : 최상의 solution인가? (비용이 최적인지)

- Time complexity

- Space complexity

 

 

 

Measure of Problem size

다음 요소들은 input size, problem size 를 결정한다.

- Branching factor (b) : 브랜치의 수

- Depth of the shallowest goal (d) : 가장 얕은 goal 의 깊이

- Maximum lengh of any path in the state space : state 의 path 중 가장 길이가 긴 path 길이

 

- Time : 검색 동안 만들어진 노드 개수

- Space : 순간에 저장된 최대 node 개수

- Total cost = search cost(탐색 비용) + execution cost(실행 비용)