AI Search tree와 Tree search, graph search

Tree Search : 문제 정의 후 solution을 찾는 과정

1. Initial state를 현재 state로 지정

2. 현재 state가 goal 인지 확인 : goal 이라면 정답으로 리턴

3. 아니라면 가능한 action들을 고려한 뒤 EXPAND

4. 적당한 Action을 선택

5. 선택한 Action으로 파생된 state를 현재 state로 지정한 뒤 2번으로 돌아가 반복

 

 

Expanding 작업은 정답을 찾거나 더 이상 expand 할 수 있는 state가 없을 때까지 반복합니다.

Frontier : Expandable node 를 모두 갖고 있는 리스트와 같은 자료구조

 

function TREE-SEARCH(problem) returns a solution, or failure
  initialize the frontier using the initial state of problem // initial state를 현재 state로 지정
  loop do
  if the frontier is empty then return failure
  chose a leaf node and remove it from the forntier // 프론티어에서 노드를 하나 뺌
  if node contains a goal state then return the corresponding solution // 노드가 goal state를 갖고 있으면 리턴
  expand the chosen node, adding the resulting nodes to the frontier // 노드를 expand 하고, 새로 생긴 노드들을 forntier 에 추가

 

Loopy paths

Tree search의 문제점으로, Redundant path가 발생하면 사이클이 생겨 무한루프가 생길 수 있다는 것이다. 이런 경우 step cost 가 음수가 아닌경우에 path cost가 계속 증가된다는 문제가 발생합니다.

 

Graph search

Tree search의 Loopy path 문제를 해결하기 위해 방문했던 노드에 대한 정보를 유지, 관리하는 검색 방법입니다.

 

function GRAPH-SEARCH(problem) returns a solution, or failure
  initialize the frontier using the initial state of problem
  initialize the explored set to be empty
  loop do
  if the forntier is empty then return failure
  choose a leaf node and remove it from the frontier
  if the node contains a goal state then return the corresponding solution
  add the node to the explored set // 방문했던 모든 노드를 저장해둠
  expand the chosen node, adding the resulting nodes to the frontier only if not in the frontier or explored set // 이미 frontier나 explored set 에 들어있는 노드라면 추가하지 않음

 

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

 

Node 구조

• Node.state

• Node.parent

• Node.action,

• Node.path-cost

Goal 을 찾았을 때 재귀적으로 Route를 복원하고 cost를 알아내기 위함입니다.

 

자료구조

• Node vs state : 여러 노드는 같은 state를 가질 수 있습니다. (부모가 다르거나 action이 다를 수도 있음)

• Frontier

• Queue

• FIFO, LIFO

• Priority queue

• Explored set

• Hash table

 

검색 알고리즘의 평가 지표

• Completeness : 정답이 있다면 무조건 찾아내는가?

• Optimality : 최적화 : 찾은 정답이 최적의 정답인가?

• Time complexity : 알고리즘 내에 만들어낸 총 state의 수

• Space complexity : 알고리즘 동작 중의 어느 시점에 필요한 최대 state의 수

 

Problem size의 측정요소

• Branching factor = b  = 브랜치의 수

• Depth of the shallowest goal  = d  =  가장 얕은 정답의 depth

• Maximum length of any path in the state space =  m  = state 의 path 중 가장 길이가 긴 path의 길이

 

Total cost = search cost + execution (path) cost