[Search_8] Suboptimal Search (1)

※ 이 글은 "UC Berkeley CS188 Intro to AI"의 "Project 1: Search"를 해결하는 과정을 정리한 글입니다.

 

Suboptimal Search

A* 탐색 알고리즘과 좋은 휴리스틱 함수를 사용했음에도 불구하고 때때로 모든 점을 지날 수 있는 최적의 경로를 찾는 것이 어려울 때가 있습니다. 이러한 경우에도 합리적인 좋은 경로를 빠르게 찾아야 합니다. 이번 과제에서는 팩맨이 항상 가장 가까운 점을 탐욕스럽게 먹게끔 코드를 구현해야 합니다. searchAgents.py 파일 안에 ClosestDotSearchAgent는 구현되어 있지만 가장 가까운 점으로 가는 길을 찾는 중요한 함수가 빠져있습니다.

 

searchAgents.py 파일안에 있는 findPathToClosestDot 함수를 구현 십시오. 구현된 함수를 통해 이 미로를 350의 비용으로 1초 안에 해결할 수 있을 것입니다.
- python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5

 

python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5 실행 시 시작되는 게임 화면

python pacman.py -l bigSearch -p ClosestDotSearchAgent -z .5 실행 시 출력 화면

 

findPathToClosestDot을 완성하는 가장 빠른 방법은 goal test가 없는 AnyFoodSearchProblem을 채우는 것입니다. 그다음 적절한 탐색 함수로 문제를 해결하십시오. 코드는 굉장히 간단할 것입니다.

 

ClosestDotSearchAgent는 항상 미로를 통과하는 가장 짧은 경로를 찾지는 않을 것입니다. 항상 가장 가까운 점을 향해 이동하는 것이 모든 점을 먹는 가장 짧은 경로가 아닐 수도 있음을 이해하고 이것의 작은 예시를 생각해보십시오.