pizzaplanet

A* Search전혀 새로울 것이 없는 탐색 방법이다.2018/05/04 - [Artificial intelligence] - Uninformed Search and Informed Search2018/05/04 - [Artificial intelligence] - 탐욕 탐색 Greedy Search실제 거리 + 예측거리식을 이용하는데 이 두가지를 섞은 것이 A* Search이다. Combining UCS and Greedy - Uniform-cost orders by path cost, or backward cost g(n)- Greedy orders by goal proximity, or forward cost h(n) A* Search orders by the sum: f(n)=g(n)+h(n)만약..

Greedy Search 휴리스틱h(x) 가 가장 작은 노드부터 확장해 나가는 것이다. 이 휴리스틱 값은 우리가 입력 혹은 설정해주어야 하는 값이다. Arad -> Bucharest 상황을 가정해보자.우측 Red Box는 각 노드에서 Bucharest까지의 휴리스틱을 나열해놓은 것이다.Arad에서 Bucharest까지의 휴리스틱은 366, Bucharest에서 Bucharest까지의 휴리스틱은 0.다시 짚고 넘어가야 할 것은 휴리스틱은 real cost 즉, 실제 거리가 아닌 예상 거리이다.Arad와 닿아있는 노드는 Zerind, Sibiu, Timlsoara 3가지. Rad Box를 참고하면h(Zerind)=374h(Sibiu)=253h(Timlsoara)=329이 3가지중 가장 작은 값을 가진 Sib..

Heuristics 간단하게는 A노드에서 B노드까지 가는 예상 거리를 휴리스틱이라 할 수 있다.이 휴리스틱은 실제값보다 작거나 같아야(h

지금까지는 Uninformed Search(DFS, BFS, UCS) 즉, 정보를 사용하지 않았을때의 탐색방법에 대해 배워보았다.앞으로는 어떠한 정보(Heuristics)를 사용하여 탐색하는 Informed Search에 배워볼까 한다. Uninformed Search- DFS- BFS- UCS Informed Search- Heuristics- Greedy Search- A* Search- Graph Search

Uniform Cost Search Strategy: Cost가 가장 낮은 노드를 우선 탐색한다.Implementation: 우선순위큐로 작성한다. (우선순위: 누적 cost) Uniform Cost Search Properties- 탐색시간: - 프린지 필요 용량: - Complete 한가? Yes (cost가 양수값을 가질때)- Optimal 한가? Yes( 다음에 배울 A*를 통해 증명됨) Uniform Cost Search Issues- Remember: UCS는 cost 등고선의 증가를 설명함- The good: UCS는 complete하고 optimal 하다.- The bad:목표에 대한 정보가 없다.모든 방향에서 옵션을 탐색한다.