Heuristic Search

Search Techniques

Blind : near optimal은 고려하지 않고 decision을 결정
- DFS (depth first search)

- BFS (breadth first search)

Heuristic : near optimal인 경우 decision

- Hill climbing

- Best-first search

- greedy search

- A* search

 

Generate-and-Test

generator가 possible solution을 생성

tester가 actual solution인지 확인

  - incorrect solution –> generator가 다시 possible solution 생성

  - correct solution -> stop

 

Hill climbing

-> new state가 goal state이거나 current state보다 좋으면 선택

evaluate the initial state.

Loop until a solution is found or no new operators left

    select an operator and produce a new state

    evaluate the new state

        if it is a goal state -> quit

        if it is not a goal state but it is better than the current state, then make it the current state

        if it is not better than the current state, continue the loop

 

 

Steepest-Ascent Hill Climbing

가능한 new sate들 중 제일 좋은 new state을 선택

문제점 : goal state에 도달하려면 worse state를 선택해야 하는데, Steepest-Ascent Hill Climbing에서는 worse state 선택 x

 

Best-first Search

현재 open된 노드들 중에 f’이 최선인 것을 우선적으 로 검색

 

Greedy best-first search

open된 모든 node들을 고려하는 것이 아니라, 당장 눈 앞에 보이는 최선을 따라서 탐색

loop에 빠질 수 있다.

optimal 하지 않다

 

A* search

출발 노드부터 목표 노드까지의 최적경로를 탐색

f(n) = g(n) + h(n)

- f(n) : 출발 노드에서 시작하여 노드 n을 거쳐서 목표 노드까지 도달하는 비용

- g(n) : 출발 노드로 부터 노드 n까지의 경로비용 (현재 경로까지 확정 비용)

- h(n) : 노드 n으로 부터 목표 노드까지의 경로비용 (현재부터 goal 까지 확정 비용)

f(n)이 최소인 노드를 따라 탐색하면, 최소 비용의 경로를 탐색

- h(n)은 아직 탐색하지 않은 경로이므로 정확히 계산하기 어렵거나 불가능함 -> 경험적 규칙 사용