Informed search, Greedy Best-first Search, A* Search

Informed search, Greedy Best-first Search, A* Search

Informed Search

- 지금까지의 Uninforemd 와는 달리, 문제 정의 이외의 정보를 더 활용하여 효율적으로 검색을 하는 방법이다.

- Best-First Search : 트리 내 evaluation function f(n) 에 의해 cost가 가장 적은 노드를 판별하여 먼저 탐색한다.

f(n) 은 heuristic function h(n) 을 포함하고 있다.

은 을 포함하고 있다. h(n) 이란 n에서부터 goal 까지의 최소 비용을 예측하는 함수이다 예를 들어, Romania 문제에서 원래는 도시간의 비용이 지도에 주어졌지만, h(n)을 사용한다면 도시 n에서부터 goal 까지의 직선거리를 사용할 수 있다. ( 직선거리 = straight line distance -> SLD )

Greedy Best-First Search

- f(n) = h(n) 으로 오직 heuristic 한 추정치만을 사용하여 검색을 진행하는 방법이다.

- 즉, goal 에 가장 가까운 node를 expand 한다.

- Romania 문제에서 SLD 가 heuristic 을 결정한다.

- 위 사진은 각각의 도시에서 Bucharest 로 이르는 직선 거리를 보여준다.

- 위 정보는 문제에서 정의된 지식이 아닌, 추가적인 지식이다.

- 이를 통해서 Tree-Based Search를 하면 다음과 같다.

- 검색 비용은 optimal 하지만, 결과는 optimal 하지 않음을 볼 수 있다.

-> (Sibiu -> Rimmicu -> Pitesti -> Burcharest) 가 optimal 한 solution이다.

Performance of Greedy Best-First Search

- Completeness

Graph version : yes

Tree version : No (DFS와 같음)

- Optimal : No

- Time and Space Complexity : O(b^m) , m은 트리구조에서 Search space 에서의 depth 의 최대값이다.

A* Search

- best-first search 로 가장 널리 알려진 알고리즘이다.

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

- 노드 n에 도달하기 위한 실제 비용 g(n) 과 노드 n 에서 goal 까지의 최소 비용을 예측한 추정 비용 h(n) 을 더한 값이다.

-> 노드 n을 거쳐서 goal 로 가는 경로 중에서 가장 비용이 저렴하다고 추정되는 비용의 추정치

- A* search 는 complete 하고, 최적의 경로를 알려주는데 적합하다.

- Uniform-cost-search 와 동일한 알고리즘이지만, priority queue 에 들어가는 가중치가 g(n) 이 아니라,

f(n) = g(n) + h(n) 이라는 것이 다르다.

- h(n) 이 특정한 조건들을 만족한다면, complete 하고 optimal 하다.

-> 최적화의 조건 : Admissibility, Consistency

Admissibility

- h(n) 이 Goal 까지 도달하는데 드는 비용을 절대로 과대평가 하지 않을 때 admissible 하다.

- 즉, 추정치 f(n) (= g(n) + h(n)) 는 절대로 실제 측정값보다 더 크게 추정해서는 안된다.

- 예를 들어, 서울에서 부산으로 가는 경로는 엄청 많으나 heuristic 함수인 서울-부산의 지도상 SLD 를 이용해서 최단경로를 검색한다고 했을 때, 서울-부산의 직선거리(heuristic 함수) 보다 짧은 실제 경로는 없을 것이기 때문이다. -> fn 이 실제 측정값보다 항상 크지 않은, 가장 작은 비용이다.

Consistency

- h(n) 이 h(n) <= c(n, a, n`) + h(n') 을 만족한다.

- 모든 n 노드와 자식노드(Successor) n′ 에 대해서, 노드 n에서 Goal에 도달하는 추정 비용은

노드 n에서 노드 n′ 까지 a라는 action 으로 가는 실제 비용과 노드 n′에서 Goal에 도달하는 추정 비용을 합한 것보다 작거나 같아야 한다.

- 이는 admissibility 보다 강력한 조건이다.

Consistency 한다면 admissible 하다.

Admissible 하더라도, Consistency 이지 않을 수 있다.

Consistency → admissible (O)

Admissible → Consistency (X)

Consistency 가 Admissible 보다 더 강력한 조건임

- Tree-search version : Admissible 하다면 Optimal 하다.

- Graph-search version : Consistent 하다면 Optimal 하다.

from http://jyeonnyang2.tistory.com/90 by ccl(A) rewrite - 2021-10-17 17:00:43