8-Puzzle Solving using the BFS,DFS using Python
깊이 우선 탐색과 넓이 우선 탐색
깊이 우선 탐색(DFS)
넓이 우선 탐색(BFS)
| 깊이 우선 탐색(depth-first search) | 넓이 우선 탐색(breadth-first search) |
|---|---|
| 해가 존재할 가능성이 존재하는 한 앞으로 계속 전진하여 탐색하는 방법이다. | 생성된 순서에 따라 노드를 확장시키는 방법이다. |
| 이 과정에서 더 이상 진행할 경로가 없을 때에는, 이전 상태 중 다른 경로의 선택을 할 수 있는 위치로 복귀하여 탐색을 계속한다. | 만일 해가 존재한다면, 출발노드에서 목표노드까지 최단 길이 경로(연산자의 적용 횟수를 최소화 하는 경로)를 찾는 것을 보장한다. 즉, 최초로 찾게 되는 해가 최단길이를 갖는 해가 된다. |
8puzzle.py
코드 설명
(1) 시작상태와 목표상태
start = [2,8,3,1,6,4,7,0,5] goal = [8,3,0,2,6,4,1,7,5]
시작상태와 목표상태를 나타내는 파이썬 리스트를 각 각 생성해준다.
(2) 자식 리스트 생성 (up,down,right,left)
def up,down,right,left():
이 up , down, right, left 함수들은 현재 상태에 대한 자식리스트를 생성해 주는 함수들이다.
각 함수들은 현재 상태의 각 인덱스 값을 탐색하여 0이 있는 인덱스(공백이 있는 칸)를 각 각 up,down,left,right 해준다.
up은 공백을 올려주는 함수이기 때문에 위로 움직일 수 없는 상태 ( 공백이 맨 위에 있는 상태 ) 를 따져줘야 한다. 이때 0 , 1 , 2 번째 인덱스에 공백이 있다면 이는 그냥 현재 상태를 리턴하고 그러지 않는 경우 ( 공백이 맨 위에 있지 않는 상태 ) 에는 자신의 바로 위 (index-3) 에 인덱스의 값을 현재 자신의 인덱스에 저장하고 바로 위(index-3)에는 0을 저장하여 이렇게 생성된 자식리스트를 호출자에게 리턴해준다.
down은 공백을 바로 아래로 내려주는 함수로, up 과 같이 아래로 움직일 수 없는 상태 ( 공백이 맨 밑에 있는 상태 ) 를 제외하고는 공백들을 다 바로 아래로 이동시켜준다. up과 같이 현재 0이 있는 인덱스를 탐색하여 공백이 아래로 움직일 수 없는 인덱스 값인 6,7,8 에 존재하면 현재 상태를 호출자에게 리턴해주고 그렇지 않은 경우에는 바로 아래(index+3) 인 인덱스 값을 현재 0이 존재하는 인덱스에 저장하고 바로 아래 인덱스에는 0을 저장하여 새로운 자식을 만든 뒤 호출자에게 리턴한다.
right,left 도 역시 현재 공백이 있는 인덱스를 탐색하여 해당 인덱스가 각 각 더 이상 오른쪽(i+1)으로 이동할 수 없는 상태 (인덱스 값이 2,5,8) 와 더 이상 왼쪽(i-1)으로 이동할 수 없는 상태 (인덱스가 0 ,3,6)가 아닌 경우에 새로운 자식 리스트를 생성 하여 호출자에게 리턴해준다.
(3)깊이 우선 탐색
def depth_first_search():
깊이 우선 탐색을 시작하는 함수 부분이다.
open 리스트는 아직 탐색하지 않은 리스트들을 담는 리스트다. 예를 들면 현 상태의 자식 노드들이 생성되면 이 자식 노드들은 아직 탐색되지 않았기 때문에 open 리스트에 들어가있게 된다. 이 open 리스트는 start 리스트부터 시작하여 탐색을 하기 위해 start 리스트를 담게 된다.
closed 리스트는 탐색이 끝난 상태의 리스트들을 담는 리스트로 이는 중복된 리스트를 알아내기 위해서 사용 된다.
while 문을 사용하여 open 리스트가 빈 상태라서 탐색이 실패하거나, open 리스트가 빈 상태가 아니라서 탐색이 성공할 때 까지 탐색을 계속 하게 된다.
X는 현재상태를 가지는 변수로 open리스트의 맨 첫 번째 값을 가지게 되며 이 X가 목표상태(goal)가 된다면 success 를 출력하며 탐색이 끝나게 되고, 그렇지 않으면 이 현재상태에서 나올 수 있는 자식 리스트들을 생성한다. 그러기 위해서는 생성된 자식 리스트를 담는 child 리스트를 하나 생성하고 현재 상태를 매개변수로 보내주면서 현재 상태에서 만들어 질 수 있는 자식들을 만들게 된다. 이때 현재 상태를 매개변수로 보내줘야 하는데, 파이썬에서 리스트는 변경가능(mutable)한 객체로 처음 down 메소드를 실행시키게 되면 만들어지는 자식리스트 값이 현재 X의 값이 되어버린다. 그렇기 때문에 이를 방지해주기 위해 변경 불가능한(immutable) 객체인 튜플(tuple)을 사용했다. (나는 여기서 tuple을 사용했지만 deepcopy를 사용하여 깊은 복사를 해도 된다.) 현재 상태 리스트(X)의 값을 변경 불가능한 tuple 형식으로 만들어 주기 위한 변수가 바로 tmp 이다. 이 tmp 는 각 각 down,right,up,left의 매개변수로 넘어는데, 각 메소드에서 받는 매개변수가 list 자료형이기 때문에 보내줄 때 이 tuple 형식을 list 형식으로 형 변환 시켜준다. 그리고 각 메소드들에서 반환된 각 자식 리스트들은 child 리스트에 append 된다. append는 리스트의 앞에서부터 뒤로 차곡 차곡 넣는 것이다.
자식리스트 생성이 완료되면 현재 상태 리스트(X)의 값은 이미 탐색을 끝냈기 때문에 closed 리스트에 추가한다. 그리고 open 리스트에서 이 X를 제거한다.
그런 다음 중복된 리스트( 이미 탐색을 끝냈거나, 이미 생성된 상태리스트 )들을 제거하기 위해서 새로 만들어진 자식들을 담은 child 리스트의 요소들이 open 리스트와 closed 리스트와 비교하여 같은 요소가 있다면 해당 요소를 제거 하고 그렇지 않은 리스트들은 open리스트의 첫 부분에 추가된다.
깊이 우선 탐색 (Depth First Search) 은 해가 존재할 가능성이 있으면 한 앞으로 계속 전진하는 방법으로 만일 더 이상 진행할 경로가 없을 때에는, 이전 상태 중 다른 경로를 선택할 수 있는 위치로 복귀하여 탐색을 계속하는 방식이다. 이는 open 리스트를 스택처럼 사용하기 때문에 첫 부분에 추가되는 것이다.
원래 라면
처럼 하나 하나 if 문을 사용하여 조건을 따져 줄 수도 있지만 코드를 조금 더 간결하게 만들기 위해 child[i] 가 open 리스트에도 closed 리스트에도 없는 경우에 open리스트의 첫 번째 인덱스에 각 자식리스트들을 넣게 하였다. 이 서술한 과정을 탐색이 성공할 때까지 반복하게 된다.
(4) 너비 우선 탐색
def breadth_first_search():
너비 우선 탐색은 깊이 우선 탐색과 다 동일하게 진행되는데 한 부분만 바뀐다.
깊이 우선 탐색은 open 리스트의 처음에 추가하는 반면 너비 우선은 open 리스트의 마지막에 추가하여 큐 처럼 사용한다.
결과
…
너비 우선 탐색 이하 생략