인공지능 탐색 알고리즘 3-Informed Search

Uninformed Search가 f(n)=g(n)+h(n)에서 h(n)=0이었다면

Informed Search는 h(n)이 0이 아닌 값을 같은 알고리즘입니다.

h(n)은 heuristic 함수로 현재 노드부터 목표(goal)까지의 추정비용입니다.

1. Greedy Best-first Search

이 알고리즘은 무조건 가장 좋은 것만 선택하는 알고리즘입니다.

길찾기 문제에 유용하며 h(n)값은 목표(goal)까지의 직선거리를 사용합니다.

그리고 g(n)에 대해서는 무시하고 계산을 합니다. g(n)=0.

Arad에서 Bucharest까지 가는 길찾기 문제입니다.

그리고 오른쪽은 Bucharest까지 각 노드별 추정거리 값입니다.

이 값을 h(n)으로 이용하여 문제를 푸는 겁니다.

초기 Arad에서 g(n)=0이므로 f(n)=0+366이 되어 366이 됩니다.

Arad를 expanding하면 Sibiu와 Timisoara, Zerind가 나옵니다.

마찬가지로 위 3개의 노드중 가장 작은 h(n)값인 Sibiu를 expanding합니다.

Arad, Fagaras, Oradea, Rimnicu Vilcea가 나옵니다.

Arad가 나오긴하지만 Arad는 값이 크므로 무시되어지고, Fagaras가 전개됩니다.

Fagaras를 전개하면 Bucharest가 나타납니다.

Bucharest의 h(n)은 0이므로 더이상 진행이 안되고 끝납니다.

하지만 Arad-Sibiu-Fagaras-Bucharest 가 최적의 길일까요?

Uninformed Search의 Uniform-cost Search로 하면 어떻게 될까요?

최적해가 Arad-Sibiu-Rimnicu Vilcea-Pitesti-Bucharest로 나옵니다.

Greedy best-first Search는 g(n)값을 고려하지 않으므로 최적해가 나오지 않습니다.

또한 경우에 따라서 complete 하지 못할수도 있습니다.

Iasi에서 Bucharest로 가는 경로의 경우입니다.

Iasi-Neamt로 이동된 후 길이없어집니다.

2. A* Search

위 Greedy best first Search의 단점인 g(n)=0되신 g(n)값을 같이 이용한 것이 

A* Search입니다.

A* Search는 Greedy best first Search와 Uniform cost Search를 결합한 것입니다.

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

A* Search를 이용하여 위의 문제를 풀면 아래와 같습니다.

초기상태 Arad=366이고, 전개하여 Sibiu, Timisoara, Zerind가 나오는 것 까진 같습니다.

여기서 각각의 값을 보면 f(n)=g(n)+h(n)이므로

Sibiu=140+253=393

Timisoara=118+329=447

Zerind=75+373=449 이므로 Sibiu를 expanding합니다.

전개하면 Arad=646, Fagaras=415, Oradea=671, Rimnicu Vilcea=413, Timisoara=447, Zerind=449

가장 작은값인 Rimncu Vilcea를 expanding합니다.

하지만 Fagaras가 415로 제일 작아 Fagaras를 expanding합니다.

Fagaras밑에 Bucharest가 나왔습니다.

하지만 450으로 Pitesti의 417보다 큽니다.

제일 작은 Pitesti를 expanding합니다.

마침내 Bucharest가 나왔고, Arad-Sibiu-Rimnicu Vilcea-Pitesti-Bucharest가 418로 제일 작아 

더이상 expanding 할수 없고, 최적의 해가 됩니다.

Uniform-cost Search와 동일한 최적해가 구해졌습니다.

h(n) 값이 과대값만 되지않으면(실제값보다 작아야) optimal한 값을 구할 수 있습니다.

그렇다고 h(n)이 0이 되면 Uniform-cost Search가 됩니다.

하지만 복잡해지게 되면 시간및 메모리가 너무 커지는 단점이 존재합니다.

좋은 h(n)이 사용되면 Uniform-cost Search에 비해 시간을 엄청 단축시킬 수 있습니다.