[Search_2] Breadth First Search (1)

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

 

Breadth First Search

search.py 파일 안에 있는 breadthFirstSearch 함수 안에 너비 우선 탐색(Breadth First Search, BFS) 알고리즘을 구현하십시오. 이미 방문한 state에서의 확장을 방지하는 그래프 탐색 알고리즘을 작성해야 합니다. 깊이 우선 탐색(Depth First Search, DFS)에서 했던 것처럼 아래에 있는 명령어로 당신의 코드를 테스트하십시오.

- python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs

 

python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs 실행 시 시작되는 게임 화면

python pacman.py -l mediumMaze -p SearchAgent -a fn=bfs 실행 시 출력 화면

 

- python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5

 

python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5 실행 시 시작되는 게임 화면

python pacman.py -l bigMaze -p SearchAgent -a fn=bfs -z .5 실행 시 출력 화면

 

너비 우선 탐색은 최소 비용의 해결 방법을 찾아내었나요? 만약 아니라면 구현한 코드를 다시 한번 확인해 보길 바랍니다. 만약 팩맨이 너무 천천히 움직인다고 생각되면 --frameTime 0이라는 옵션을 사용해 보십시오.

 

만약 구현한 탐색 코드가 일반화가 잘 되어있다면, 8-puzzle 탐색 문제에서 아무런 수정을 하지 않은 채로 사용하여도 잘 작동할 것입니다.

- python eightpuzzle.py

 

python eightpuzzle.py 실행 시 출력 화면