Solving 8-puzzle problem with search algorithm
Abstract
8-퍼즐 문제는 3X3 크기의 프레임과 1부터 8까지의 숫자로 이루어진 슬라이딩 퍼즐을 순서대로 배열하는 문제입니다. 더 일반화된 문제는 N-퍼즐 문제로, 최적의 해를 찾는 것이 NP-hard라고 합니다. 이번 글에서는 가장 기본적인 BFS, DFS에서부터 IDS 알고리즘, A* 알고리즘까지의 방법론으로 8-퍼즐 문제를 풀어보고, 그 성능을 분석해보도록 하겠습니다.
8-퍼즐 문제
8-퍼즐은 3X3 그리드로 나누어진 정사각형 프레임 안에 8개의 타일과 하나의 빈 공간이 있는 슬라이딩 타일 퍼즐입니다. 아마 한번쯤은 해보셨을 것으로 생각됩니다.
8-퍼즐
각 타일은 서로 구분되는데, 보통은 1부터 8까지의 숫자로 구분됩니다. 이 글에서도 각 타일에 1부터 8까지의 숫자를 부여하고, 빈 공간은 0으로 표시하도록 하겠습니다. 움직을 수 있는 타일은 자명하게도 빈 공간과 이웃한 타일들입니다. 이 타일들 중 하나를 선택하여 빈 공간으로 움직일 수 있습니다. 이렇게 타일을 움직이는 작업을 반복하여 주어진 초기 상태로부터 주어진 목표 상태를 만들면 됩니다. 이 글에서는 목표 상태를 “012345678”이라고 고정하겠습니다. 이 숫자열의 의미는 아래 표와 같은 상태로 타일들이 배열된 상태를 의미합니다.
| 0 (빈 칸) | 1 | 2 |
| 3 | 4 | 5 |
| 6 | 7 | 8 |
풀 수 있는 문제인지 판단하는 방법
8-퍼즐 문제에는 9!개의 상태가 존재합니다. 이는 362880으로 비교적 많은 수라고 볼 수 있습니다. 다만 문제는 이중에서 절반의 상태에서만 목표 상태에 도달할 수 있습니다. 다시 말해, 나머지 절반의 상태에서 출발하면 어떠한 방법으로도 목표 상태에 도달할 수 없음을 의미합니다. 예를 들어서 “021345678”를 초기 상태로 설정한다면, 타일을 아무리 움직여도 목표 상태인 “012345678”에 도달할 수 없습니다.
그럼 임의의 상태로부터 목표 상태에 도달할 수 있는지를 어떻게 판단할 수 있을까요? 여기에는 inversion이라는 개념이 사용됩니다. inversion은 m < n이지만 m이 n보다 뒤에 존재하는 m과 n 쌍을 의미합니다. 말그대로 1번 타일과 3번 타일이 있을 때 3번 타일이 1번 타일보다 앞에 존재하는 경우, 1번 타일과 3번 타일 쌍은 inversion입니다.
8-퍼즐에서는 어떠한 방식으로 타일을 움직이든, 이 inversion 수의 홀짝성이 유지됩니다. 왜그런지는 몇 가지 경우를 직접 해보시면 금방 알 수 있을 것입니다. 따라서 따로 증명을 하지는 않고 넘어가겠습니다. 따라서 초기 상태와 목표 상태의 홀짝성이 다르다면, 초기 상태에서 어떤 방식으로 타일을 움직이든 목표 상태에 도달하지 못함이 증명됩니다.
이 글에서 설정한 목표 상태인 “012345678”에는 inversion이 짝수 개 존재합니다. 따라서 inversion이 홀수 개인 상태에서는 목표 상태에 도달할 수 없고, inversion이 짝수 개인 상태에서는 목표 상태로 도달할 수 있습니다.
추가로, 만약 초기 상태에서 목표 상태로 도달할 수 있는 경우라면, 31 이하의 타일 이동만으로 목표 상태에 도달할 수 있다고 합니다.
BFS 알고리즘
첫번째로는 가장 간단한 BFS 알고리즘으로 8-퍼즐 문제를 풀어보겠습니다. BFS는 완전 탐색 알고리즘이기 때문에 해가 존재하는 경우라면 반드시 해를 찾아냅니다. 또한, 깊이가 낮은 곳부터 깊이가 높은 곳까지 깊이의 오름차순으로 방문하기 때문에 처음 찾은 해가 가장 깊이가 낮은 해가 됩니다. 즉, 처음 찾은 해가 최적의 해라는 의미가 됩니다. 따라서 BFS는 완전 탐색이기에 반드시 해를 찾을 수 있다는 점, 깊이를 점차 늘려가기 때문에 처음 찾은 해가 최적의 해임이 보장된다는 점에서 큰 장점을 가지고 있습니다. 구현한 코드는 아래와 같습니다.
from collections import deque # Module for using Queue
from collections import defaultdict # Module for use with the Dictionary
import time # Module for run-time measurement
start_time = time.time() # Save Start Time
# init
visited=defaultdict(str) # Dictionary to confirm visit status
bfs=deque() # Queue to be used as Frontier for BFS
start=['724506831'] # Initial state
goal='012345678' # goal state
bfs.append(start) # Insert Initial State into Queue
visited[start[-1]]=1 # Visited Initial State
# List of indexes that can be moved in each index
list_list_index=[[1, 3], [0,2,4], [1, 5], [0,4,6], [1, 3, 5, 7], [2, 4, 8], [3, 7], [4, 6, 8], [5, 7]]
cnt=0 # Number of nodes visited
# Define a tile sliding function
def swap(s, a): # State, index of sliding element
temp=s[a]
temp_s=s
temp_s=temp_s.replace('0','9')
temp_s=temp_s.replace(temp, '0')
temp_s=temp_s.replace('9', temp)
return temp_s # Return slided State
# Define a branching function
def list_next(s): # State
list_index=list_list_index[s.index('0')]
list_leap=[]
for i in list_index:
temp=str(s)
list_leap.append(swap(temp, i))
return list_leap # Return list of child nodes
while(len(bfs)): # Repeat until all nodes are visited
# Currently visiting Node
now=bfs[0] # List that previous states (path) is stored
cnt+=1
bfs.popleft()
if now[-1]==goal: # Repeat until target state is reached
break
# Branching from now to child node
for l in list_next(now[-1]): # Of the nodes available,
if visited[l]=='': # If not visited,
temp=list(now)
temp.append(l)
bfs.append(temp) # Add to Queue
visited[l]=1 # Visited because it's going to be visited
print(now[-1], cnt, len(now)) # Goal State, Number of Visited Nodes, Level
print("time :", time.time() - start_time, "sec") # Run Time
시간 복잡도
$b$를 가지의 수라고 하고, $d$를 해까지의 깊이라고 한다면 최악의 상황에서 시간 복잡도는 $O(b^d)=1+b+b^2+ \dots + b^d$가 됩니다. 실제로 BFS 알고리즘이 수행될 때 방문한 노드의 수와 깊이, 실행시간을 분석해보면 아래와 같습니다.
| Number of Visited Nodes | Level | Run Time(sec) |
|---|---|---|
| 169741 | 27 | 1.9133 1.2010 1.1189 1.0442 2.4264 |
| Average | 1.5408 |
DFS 알고리즘
다음으로는 DFS 알고리즘으로 8-퍼즐 문제를 풀어보겠습니다. DFS 알고리즘은 BFS 알고리즘과 마찬가지로 완전 탐색 알고리즘이기 때문에 해를 반드시 찾을 수 있다는 장점이 있지만, 깊이 순으로 탐색하지 않기 때문에 처음 찾은 해가 최적의 해가 아닐 수 있다는 단점이 존재합니다. 구현한 코드는 아래와 같습니다.
import time # Module for run-time measurement
start_time = time.time() # Save Start Time
# init
start=['724506831'] # Initial state
goal='012345678' # goal state
stk=[start] # Stack to be used as Frontier for DFS
# List of indexes that can be moved in each index
list_list_index=[[3, 1], [4, 2, 0], [5, 1], [6, 4, 0], [7, 5, 3, 1], [8, 4, 2], [7, 3], [8, 6, 4], [7, 5]]
cnt=0 # Number of nodes visited
# Define a checking solvable function
def isSolvable(s):
inv=0
for i in range(8):
for j in range(i+1, 9):
if int(s[i]) and int(s[j]) and s[i]>s[j]:
inv+=1
return inv%2 == 0
# Define a tile sliding function
def swap(s, a): # State, index of sliding element
temp=s[a]
temp_s=s
temp_s=temp_s.replace('0','9')
temp_s=temp_s.replace(temp, '0')
temp_s=temp_s.replace('9', temp)
return temp_s # Return slided State
# Define a branching function
def list_next(s): # State
list_index=list_list_index[s.index('0')]
list_leap=[]
for i in list_index:
temp=str(s)
list_leap.append(swap(temp, i))
return list_leap # Return list of child nodes
while stk: # Repeat until all nodes are visited
# Currently visiting Node
now=stk.pop()
cnt+=1
if now[-1]==goal: # Repeat until target state is reached
break
# Branching from now to child node
for i in list_next(now[-1]): # Of the nodes available,
# If not visited and is solvable,
if i not in now and isSolvable(i):
temp=list(now)
temp.append(i) # Add to Stack
stk.append(temp)
print(now[-1], cnt, len(now)) # Goal State, Number of Visited Nodes, Level
print("time :", time.time() - start_time, "sec") # Run Time
시간 복잡도
DFS 알고리즘에서 최대 깊이를 $m$이라고 했을 때, 최악의 경우 최적의 해를 찾기 까지 $O(b^m)$개의 노드를 방문해야 합니다. $m$이 $d$보다 크다면, BFS 알고리즘보다 더욱 효율적이지 않습니다. 하지만 해가 다양한 위치에 분포한다면, BFS 알고리즘보다 더욱 효율적일 수 있습니다. 실제 실행 시간을 분석해보면 아래와 같습니다.
| Number of Visited Nodes | Level | Run Time(sec) |
|---|---|---|
| 10341 | 10221 | 11.5468 9.5254 10.3357 10.3892 9.6003 |
| Average | 10.2795 |
이 글에서 설정한 세팅에서는 DFS 알고리즘을 사용했을 때가 BFS 알고리즘을 사용했을 때보다 훨씬 많은 실행시간이 걸렸으며, 방문한 최대 깊이도 최적의 해에 비해서 상당히 큰 것을 확인할 수 있습니다.
IDS 알고리즘
IDS 알고리즘은 목표 상태를 찾을 때까지 최대 깊이 제한을 증가시키면서 연속적으로 DLS 알고리즘을 수행하는 알고리즘입니다. 여기서 DLS 알고리즘은 DFS with Level Limit이라는 뜻으로, 최대 깊이 제한이 있는 DFS 알고리즘을 의미합니다. 따라서 BFS 알고리즘에서와 마찬가지로 최적의 해를 찾을 수 있으며, 모든 노드를 방문하는 완전 탐색 알고리즘이기 때문에 해를 반드시 찾을 수 있음이 보장됩니다. 구현한 코드는 아래와 같습니다.
import time # Module for run-time measurement
start_time = time.time() # Save Start Time
# init
start=['724506831'] # Initial state
goal='012345678' # goal state
stk=[start] # Stack to be used as Frontier for DFS
# List of indexes that can be moved in each index
list_list_index=[[3, 1], [4, 2, 0], [5, 1], [6, 4, 0], [7, 5, 3, 1], [8, 4, 2], [7, 3], [8, 6, 4], [7, 5]]
cnt=0 # Number of nodes visited
limit=0 # maximum depth
now=start # Initial State
# Define a checking solvable function
def isSolvable(s):
inv=0
for i in range(8):
for j in range(i+1, 9):
if int(s[i]) and int(s[j]) and s[i]>s[j]:
inv+=1
return inv%2 == 0
# Define a tile sliding function
def swap(s, a): # State, index of sliding element
temp=s[a]
temp_s=s
temp_s=temp_s.replace('0','9')
temp_s=temp_s.replace(temp, '0')
temp_s=temp_s.replace('9', temp)
return temp_s # Return slided State
# Define a branching function
def list_next(s): # State
list_index=list_list_index[s.index('0')]
list_leap=[]
for i in list_index:
temp=str(s)
list_leap.append(swap(temp, i))
return list_leap # Return list of child nodes
while 1: # Repeat until goal is found / Not shut down in trees which has no goal state or is infinity
stk=[start] # Clear Stack
limit+=1 # Increase the depth limit by 1
while stk:
# Currently visiting Node
now=stk.pop()
cnt+=1
if now[-1]==goal: # Repeat until target state is reached
break
# Branching from now to child node
if len(now)<limit: # Within the maximum depth,
for i in list_next(now[-1]): # Of the nodes available,
# If not visited and is solvable,
if i not in now and isSolvable(i):
temp=list(now)
temp.append(i) # Add to Stack
stk.append(temp)
if now[-1]==goal: # Repeat until target state is reached
break
print(now[-1], cnt, len(now)) # Goal State, Number of Visited Nodes, Level
print("time :", time.time() - start_time, "sec") # Run Time
시간 복잡도
IDS 알고리즘도 BFS와 마찬가지로 최악의 경우, $O(b^d)$번 노드를 방문해야 합니다. 실제로 수행시간을 분석해보면 아래와 같습니다.
| Number of Visited Nodes | Level | Run Time(sec) |
|---|---|---|
| 12460071 | 27 | 401.0046 381.6445 411.9110 391.2918 409.0165 |
| Average | 398.9737 |
A* 알고리즘
A* 알고리즘은 휴리스틱 알고리즘의 일종입니다. A* 알고리즘은 BFS 알고리즘의 일종으로 생각할 수 있습니다. 다만, 노드 방문 순서를 휴리스틱에 따라 결정하는 것이 다릅니다. BFS 알고리즘과는 다르게 휴리스틱을 어떻게 정의하는냐에 따라서 최적의 해를 찾을 수도 있고 못찾을 수도 있습니다. 다시 말해서, A* 알고리즘을 사용하면 최적의 해를 찾을 수 있음이 보장되지 않는다는 의미입니다. A* 알고리즘을 사용할 때, 평가 함수 $f(n)$은 노드 방문에 대한 우선 순위를 정의합니다.
\[f(n)=g(n)+h(n)\]$g(n)$은 초기 상태로부터 노드 n까지의 경로에 대한 cost를 의미합니다. $h(n)$은 노드 n으로부터 목표 상태까지의 경로에 대한 cost를 휴리스틱 함수로 예측한 값을 의미합니다.
휴리스틱1: 잘못 위치된 타일의 수 활용
이 휴리스틱에서는 임의의 위치에서 타일을 제거하고 그를 다른 위치로 옮기는 것이 가능합니다. 즉 빈 공간과 이웃한 타일들만 빈 공간으로 움직일 수 있는 것이 아니라 한번에 많은 슬라이딩을 하는 것을 허용합니다. 이러한 상황에서는 현재 상태에서 목표 상태로 이동하기 위해서, 제자리가 아닌 타일의 수만큼 타일 이동이 이루어지면 됩니다. 따라서 최소 비용 경로는 제자리에 존재하지 않는 타일의 수로 볼 수 있습니다. 구현된 코드는 아래와 같습니다.
# -*- coding: utf-8 -*-
"""
Created on Sat Oct 5 03:08:06 2019
@author: Yun, Junhyuk
"""
from queue import PriorityQueue # Module for using PriorityQueue
import time # Module for run-time measurement
start_time = time.time() # Save Start Time
# init
#Constants to be used for the heuristic (weighted values to be added according to Constants to be used for the heuristic calculation (weighted value to be added according to the number of misplaced tiles).
cost_value=1
start=['724506831'] # Initial state
goal='012345678' # goal state
astar=PriorityQueue() # PriorityQueue to be used as Frontier for A*
astar.put((0,start)) # Insert Initial State into PriorityQueue
# List of indexes that can be moved in each index
list_list_index=[[1, 3], [0,2,4], [1, 5], [0,4,6], [1, 3, 5, 7], [2, 4, 8], [3, 7], [4, 6, 8], [5, 7]]
cnt=0 # Number of nodes visited
# Define a checking solvable function
def isSolvable(s):
inv=0
for i in range(8):
for j in range(i+1, 9):
if int(s[i]) and int(s[j]) and s[i]>s[j]:
inv+=1
return inv%2 == 0
# Define a tile sliding function
def swap(s, a): # State, index of sliding element
temp=s[a]
temp_s=s
temp_s=temp_s.replace('0','9')
temp_s=temp_s.replace(temp, '0')
temp_s=temp_s.replace('9', temp)
return temp_s # Return slided State
# Define a branching function
def list_next(s): # State
list_index=list_list_index[s.index('0')]
list_leap=[]
for i in list_index:
temp=str(s)
list_leap.append(swap(temp, i))
return list_leap # Return list of child nodes
# Return h(n) when string comes in
def h_diff(s):
dist = 0
for i in range(9):
if s[i]!=str(i):
dist+=cost_value
return dist
while astar.qsize(): # Repeat until all nodes are visited
# Currently visiting Node
now=astar.get()[1] # Index 0 is f(n), index 1 is the path
cnt+=1
if now[-1]==goal: # Repeat until target state is reached
break
# Branching from now to child node
for l in list_next(now[-1]):
# If not visited and is solvable,
if l not in now and isSolvable(l):
temp=list(now)
temp.append(l)
astar.put(((len(temp)+h_diff(l)),temp)) # Store the node with f(n) in priority queue
print(now[-1], cnt, len(now)) # Goal State, Number of Visited Nodes, Level
print("time :", time.time() - start_time, "sec") # Run Time
시간 복잡도
시간 복잡도는 수학적으로 계산하지 않고 실제 얼마의 시간이 걸렸는지를 분석했습니다. path cost를 1에서부터 100까지 변경하면서 실험한 결과 아래와 같습니다. 아무래도 휴리스틱 알고리즘이기에 다른 알고리즘들에 비해 훨씬 빠른 속도로 해를 찾고 있습니다. 하지만 휴리스틱 알고리즘의 특성상 실행 시간 간의 편차가 큰 것을 확인할 수 있었습니다. 또한 path cost가 커질 수록 path의 길이가 커지는 경향성을 볼 수 있었습니다. 각 path cost에 대한 실험은 5번 진행하여 그 결과들에 평균을 취했습니다.
| path cost | Number of Visited Nodes | Level | Average Run Time(s) |
|---|---|---|---|
| 1 | 119306 | 27 | 8.9983 |
| 3 | 44105 | 27 | 1.3676 |
| 5 | 8760 | 31 | 0.6352 |
| 10 | 1011 | 37 | 0.0737 |
| 100 | 30447 | 55 | 2.5788 |
휴리스틱2: 맨하탄 거리 활용
8-퍼즐에서 맨하탄 거리는 실제로 타일을 이동시켜야 할 횟수를 의미합니다. 맨하탄 거리에서 정의하는 것처럼 8-퍼즐 상에서도 타일이 상하좌우로만 움직일 수 있기 때문입니다. 이 휴리스틱에 따르면 타일은 수평 또는 수직으로 인접한 위치에서 이동할 수 있습니다. 목표 상태에 도달하기 위해서는 현재 상태에서 모든 타일들에 목표 상태에서의 제자리로 이동해야 합니다. 이때 모든 타일들이 최단 거리로 이동한다고 가정한다면 현재 위치와 목표 상태에서의 위치 간의 맨하탄 거리만큼의 이동이 발생해야 합니다. 따라서 이번에는 각 타일에 대한 맨하탄 거리의 합으로 휴리스틱을 정의해보겠습니다. 구현된 코드는 아래와 같습니다.
from queue import PriorityQueue # Module for using PriorityQueue
import time # Module for run-time measurement
start_time = time.time() # Save Start Time
# init
start=['724506831'] # Initial state
goal='012345678' # goal state
astar=PriorityQueue() # PriorityQueue to be used as Frontier for A*
astar.put((0,start)) # Insert Initial State into PriorityQueue
# List of indexes that can be moved in each index
list_list_index=[[1, 3], [0,2,4], [1, 5], [0,4,6], [1, 3, 5, 7], [2, 4, 8], [3, 7], [4, 6, 8], [5, 7]]
cnt=0 # Number of nodes visited
# Define a checking solvable function
def isSolvable(s):
inv=0
for i in range(8):
for j in range(i+1, 9):
if int(s[i]) and int(s[j]) and s[i]>s[j]:
inv+=1
return inv%2 == 0
# Define a tile sliding function
def swap(s, a): # State, index of sliding element
temp=s[a]
temp_s=s
temp_s=temp_s.replace('0','9')
temp_s=temp_s.replace(temp, '0')
temp_s=temp_s.replace('9', temp)
return temp_s # Return slided State
# Define a branching function
def list_next(s): # State
list_index=list_list_index[s.index('0')]
list_leap=[]
for i in list_index:
temp=str(s)
list_leap.append(swap(temp, i))
return list_leap # Return list of child nodes
# Return h(n) when string comes in
def h_dist(s):
dist = 0
for i in range(9):
goal_x = i//3
goal_y = i - goal_x*3
now_x = s.index(str(i))//3
now_y = s.index(str(i)) - now_x*3
dist += abs(goal_x - now_x) + abs(goal_y - now_y)
return dist
while astar.qsize(): # Repeat until all nodes are visited
# Currently visiting Node
now=astar.get()[1] # Index 0 is f(n), index 1 is the path
cnt+=1
if now[-1]==goal: # Repeat until target state is reached
break
# Branching from now to child node
for l in list_next(now[-1]):
# If not visited and is solvable,
if l not in now and isSolvable(l):
temp=list(now)
temp.append(l)
astar.put(((len(temp)+h_dist(l)),temp)) # Store the node with f(n) in priority queue
print(now[-1], cnt, len(now)) # Goal State, Number of Visited Nodes, Level
print("time :", time.time() - start_time, "sec") # Run Time
시간 복잡도
첫번째 휴리스틱에서와 마찬가지로 수학적으로 계산하지 않고 실제 실행시간만을 분석했습니다. 이 휴리스틱을 사용했을 때 해를 찾는 속도가 다른 알고리즘들에 비해 굉장히 빨랐습니다.
| Number of Visited Nodes | Level | Run Time(sec) |
|---|---|---|
| 4544 | 27 | 0.3635 0.4169 0.3660 0.4070 0.4131 |
| Average | 0.3933 |
Conclusion
8-퍼즐 문제의 풀기 위해 BFS, DFS, IDS, A* 알고리즘을 사용하고 각 성능을 살펴봤습니다. BFS 알고리즘은 최적의 목표를 찾았고 최적의 목표까지 참조되는 노드 수가 적었기 때문에 비교적 빠르게 실행되었습니다. 최적의 목표가 더 깊었다면 실행 시간이 기하급수적으로 늘어났을 것입니다. DFS 알고리즘은 최적 목표 길이의 약 400배에 해당하는 상태를 반환했습니다. 참조된 노드의 수가 적었기 때문에 BFS 알고리즘의 경우와 마찬가지로 목표 상태가 비교적 빠르게 발견되었습니다. 이것은 목표 상태가 트리에서 균일하고 다양하게 존재한다는 것을 의미합니다. 목표 상태가 균일하게 분포하지 않았다면 목표 상태를 찾는 데 BFS 알고리즘보다 더 오랜 시간이 걸렸을 것입니다. IDS 알고리즘은 목표 상태를 찾을 때까지 너무 많은 노드를 참조하여 목표 상태를 찾는 데 오랜 시간이 걸렸습니다. 마지막으로, A* 알고리즘은 사용된 휴리스틱에 따라 결과가 달라졌지만, 전체적으로 다른 알고리즘보다 목표 상태를 찾는 속도가 상당히 빨랐고, 참조된 노드의 수도 더 적었습니다. 그러나 참조된 노드의 수와 실행 시간은 휴리스틱을 정의한 방법에 따라 약 100배 차이가 났습니다. 또한 최적의 목표를 찾은 경우도 있었고 휴리스틱에 의존하지 않는 경우도 있었습니다. A* 알고리즘의 성능을 더욱 향상시키려면 휴리스틱을 포함하는 평가 함수를 정의하는 방법이 중요하다는 것을 알 수 있습니다.