※ 이 글은 "UC Berkeley CS188 Intro to AI"의 "Project 1: Search"를 해결하는 과정을 정리한 글입니다.
A* search
search.py 파일 안에 있는 비어있는 aStarSearch 함수에 A* 탐색 알고리즘을 구현하십시오. A* 탐색 알고리즘은 휴리스틱 함수를 인수로 갖고 있습니다. 휴리스틱은 2가지 인수(탐색 문제에서의 state와 자기 자신에 관한 정보)를 갖고 있습니다. search.py 파일 안에 있는 nullHeuristic 휴리스틱 함수는 간단하게 구현한 예제입니다.
구현이 완료된 A* 탐색 알고리즘은 Manhattan Distance 휴리스틱을 사용하여 미로에서 길을 찾을 수도 있습니다.(searchAgents.py 에 이미 manhattanHeuristic이 구현되어 있습니다.)
- python pacman.py -l bigMaze -z .5 -p SearchAgent -a fn=astar, heuristic=manhattanHeuristic
A* 탐색 알고리즘이 균일 비용 탐색(Uniform Cost Search, UCS) 보다 빠르게 최적의 답을 찾는 것을 확인할 수 있습니다. 다른 다양한 탐색 알고리즘들이 openMaze에서는 어떻게 동작할지 궁금하지는 않으신가요?
'UC Berkeley CS188 Intro to AI > [Pacman Project 1] Search' 카테고리의 다른 글
| [Search_5] Finding All the Corners (1) (0) | 2022.05.24 |
|---|---|
| [Search_4] A* search (2) (0) | 2022.05.23 |
| [Search_3] Varying the Cost Function (2) (0) | 2022.05.21 |
| [Search_3] Varying the Cost Function (1) (0) | 2022.05.20 |
| [Search_2] Breadth First Search (2) (0) | 2022.05.19 |