[인공지능] 탐색 알고리즘
Updated:
탐색(Search)
탐색이란 상태공간에서 연산자를 가하며 시작 상태에서 목표 상태까지의 경로를 찾는 것 입니다. 상태공간(state space)은 상태들이 모여있는 상태이고 연산자는 다음 상태를 생성하는 것 입니다.
탐색 알고리즘 유형
깊이 우선 탐색(DFS, Depth-First Search)
깊이 우선 탐색은 루트 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 쉽게 말해 해가 존재할 가능성이 있는 한 계속 탐색하는 방법입니다. 깊이 우선 탐색에서는 리스트를 스택처럼 사용합니다. 후입선출(LIFO, Last-In, Last-Out)을 원칙으로 탐색합니다. 깊이 우선 탐색 알고리즘을 구현할 때, 무한루프에 빠질 수 있기 때문에 꼭 어떤 노드를 방문했었는지 중복 여부를 반드시 검사해야 합니다. 깊이 우선 탐색의 구현 방법에는 순환 호출 이용과 명시적인 스택 사용이 있습니다.
너비 우선 탐색(BFS, Breadth-First Search)
너비 우선 탐색은 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 즉, 시작 노드로부터 가까운 노드를 방문하고 멀리 있는 노드를 후에 방문하는 방법입니다. 트리의 관점에서 보면 같은 레벨 상에 있는 형제 노드들을 방문한 후, 다음 레벨로 넘어가서 순회하는 방식입니다. 너비 우선 탐색에서는 리스트를 큐처럼 사용합니다. 선입선출(FIFO, First-In, First-Out)을 원칙으로 탐색합니다. 깊이 우선 탐색과 마찬가지로 너비 우선 탐색 또한 어떤 노드를 방문했었는지 검사해야 합니다.
8-puzzle
8-puzzle은 섞인 숫자를 최소 횟수의 이동으로 원래대로 맞추는 문제입니다. 깊이 우선 탐색과 너비 우선 탐색 알고리즘을 이용하여 8-puzzle 문제를 해결해 보았습니다.
깊이 우선 탐색
#8-puzzle dfs(깊이 우선 탐색)
#---------- DFS ----------#
#깊이 우선 탐색
def depth_first_search(puzzle):
visit = [] #closed
stack = collections.deque([puzzle]) #open
print("Goal : ", goal)
while stack is not Node:
print("\n====================")
print("stack : ", stack)
xNode = stack.pop() #가장 마지막 노드를 꺼
print("xNode : ", xNode, "\n")
display(xNode) #현재 상태 노드 출력
if xNode == goal: #현재 상태 노드가 목표상태와 같다면 성공
return print("\nSUCESS!")
else: #아니면
visit.append(xNode) #현재 노드를 visit에 추가
print("visit : ", visit)
#0 위치를 확인한 후 0 위치 인덱스 반환
index = checkPosition(xNode)
print("'0'index :", index)
#모든 연산자에 대해 조회
for oper in op:
#새로운 노드 생성
newNode = createNode(stack, visit, copy.deepcopy(xNode), index, oper)
print("\nnewNode : ", oper, newNode)
if newNode is not None: #새로운 노드가 있다면
stack.append(newNode) #stack(opnen)에 추가
#print("stack : ", stack)
print()
너비 우선 탐색
#8-puzzle bfs(너비 우선 탐색)
#---------- BFS ----------#
#너비 우선 탐색
def breadth_first_search(puzzle):
visit = [] #closed
queue = collections.deque([puzzle]) #open
print("Goal : ", goal)
while queue is not Node:
print("\n====================")
print("초기 queue : ", queue)
xNode = queue.popleft() #가장 먼저 들어간 노드를 꺼냄
print("xNode : ", xNode, "\n")
display(xNode) #현재 상태 노드 출력
if xNode == goal:
return print("\nSUCESS!")
else:
visit.append(xNode)
print("visit : ", visit)
index = checkPosition(xNode)
print("'0'index :", index)
for oper in op:
newNode = createNode(queue, visit, copy.deepcopy(xNode), index, oper)
print("\nnewNode : ", oper, newNode)
if newNode is not None:
queue.append(newNode)
print(" : ", queue)
print()
전체 코드
#8-puzzle bfs(너비 우선 탐색), dfs(깊이 우선 탐색)
import collections
import copy
import time
goal = [1,2,3,
4,5,6,
7,8,0]
puzzle = [1,2,3,
4,5,6,
0,7,8]
op = ['UP', 'DOWN', 'RIGHT', 'LEFT']
#노드 클래스
class Node:
def __init__(self, state):
self.state = state
#---------- DFS ----------#
#깊이 우선 탐색
def depth_first_search(puzzle):
visit = [] #closed
stack = collections.deque([puzzle]) #open
print("Goal : ", goal)
while stack is not Node:
print("\n====================")
print("stack : ", stack)
xNode = stack.pop() #가장 마지막 노드를 꺼냄
print("xNode : ", xNode, "\n")
display(xNode) #현재 상태 노드 출력
if xNode == goal: #현재 상태 노드가 목표상태와 같다면 성공
return print("\nSUCESS!")
else: #아니면
visit.append(xNode) #현재 노드를 visit에 추가
print("visit : ", visit)
#0 위치를 확인한 후 0 위치 인덱스 반환
index = checkPosition(xNode)
print("'0'index :", index)
#모든 연산자에 대해 조회
for oper in op:
#새로운 노드 생성
newNode = createNode(stack, visit, copy.deepcopy(xNode), index, oper)
print("\nnewNode : ", oper, newNode)
if newNode is not None: #새로운 노드가 있다면
stack.append(newNode) #stack(opnen)에 추가
#print("stack : ", stack)
print()
#---------- BFS ----------#
#너비 우선 탐색
def breadth_first_search(puzzle):
visit = [] #closed
queue = collections.deque([puzzle]) #open
print("Goal : ", goal)
while queue is not Node:
print("\n====================")
print("초기 queue : ", queue)
xNode = queue.popleft() #가장 먼저 들어간 노드를 꺼냄
print("xNode : ", xNode, "\n")
display(xNode) #현재 상태 노드 출력
if xNode == goal:
return print("\nSUCESS!")
else:
visit.append(xNode)
print("visit : ", visit)
index = checkPosition(xNode)
print("'0'index :", index)
for oper in op:
newNode = createNode(queue, visit, copy.deepcopy(xNode), index, oper)
print("\nnewNode : ", oper, newNode)
if newNode is not None:
queue.append(newNode)
print(" : ", queue)
print()
#---------- checkPosition ----------#
#0의 위치를 체크하는 함수
def checkPosition(xNode):
i = xNode.index(0) #0의 인덱스를 반
return i
#---------- createNode ----------#
#newNode생성 함수
def createNode(stack, visit, newNode, i, oper):
if oper == 'UP':
if (i >= 3):
newNode[i] = newNode[i - 3]
newNode[i - 3] = 0
if newNode in visit or newNode in stack:
return None
else:
return newNode
if oper == 'DOWN':
if (i < 6):
newNode[i] = newNode[i + 3]
newNode[i + 3] = 0
if newNode in visit or newNode in stack:
return None
else:
return newNode
if oper == 'RIGHT':
if ((i%3) < 2):
newNode[i] = newNode[i + 1]
newNode[i + 1] = 0
if newNode in visit or newNode in stack:
return None
else:
return newNode
if oper == 'LEFT':
if ((i%3) > 0):
newNode[i] = newNode[i - 1]
newNode[i - 1] = 0
if newNode in visit or newNode in stack:
return None
else:
return newNode
#---------- display ----------#
def display(puzzle):
print(" -----------")
print("| %d | %d | %d |" %(puzzle[0], puzzle[1], puzzle[2]))
print(" -----------")
print("| %d | %d | %d |" %(puzzle[3], puzzle[4], puzzle[5]))
print(" -----------")
print("| %d | %d | %d |" %(puzzle[6], puzzle[7], puzzle[8]))
print(" -----------")
#---------- main ----------#
node = Node(puzzle)
print("\n*깊이 우선 탐색*\n")
start1 = time.time() #시간측정 시작
depth_first_search(puzzle)
print("DFS 소요 시간 : ", time.time() - start1) #종료
start2 = time.time() #시간측정 시작
print("\n*너비 우선 탐색*\n")
breadth_first_search(puzzle)
print("BFS소요 시간 : ", time.time() - start2) #종료
메인 메소드에는 8-puzzle 객체를 생성하여 node에 저장한 후, 깊이 우선 탐색 메소드 depth_first_search(node)와 breadth_first_search(puzzle)에 생성된 퍼즐 객체를 인수로 전달하고 메소드를 호출하였습니다. 깊이 우선 탐색메소드 depth_first_search(puzzle)과 너비 우선 탐색메소드 breadth_first_search(puzzle)에서 stack과 queue를 구현해야 했기 때문에 deque 자료구조를 사용하였습니다. deque는 양방향 큐로 양쪽 방향에서 요소를 추가하거나 삭제할 수있어서 스택과 큐를 쉽게 구현할 수 있습니다.
depth_first_search(puzzle)는 먼저 stack에 인수로 전달 받은 puzzle을 넣어주고 만약 stack이 비어있지 않다면 while문을 계속 돌면서 노드들을 생성하고 목표 상태까지 탐색합니다. 스택에 가장 마지막에 들어온 노드를 꺼내서 목표 상태와 비교한 후 아니면 현재 노드를 visit 리스트에 추가합니다. 이유는 어떤 노드를 탐색했는지 중복 여부를 체크해주지 않으면 무한 루프에 빠지기 때문입니다. 그 후 0의 위치를 확인해주는 checkPosition()메소드를 호출하여 0의 위치를 확인한 후 그 위치의 인덱스를 반환 받습니다. 모든 연산자에 대해 조회해야 하기 때문에 for문을 돌려주었습니다. createNode()메소드를 호출하여 연산자를 조회함과 동시에 새로운 노드를 생성해 확장 시켜 주었습니다. 새로운 노드를 생성하기 전에 연산자로 조건문을 검사하면서 0이 갈 수 있는 경우를 구분지어 주었습니다.
3*3 행렬에 0-8까지의 인덱스 번호를 부여하여 0이 갈 수 있는 경우를 확인해 보았습니다.
해당 조건들을 검사한 후 0과 기존에 있던 요소의 위치를 바꿔준 후 새로운 노드가 기존에 방문했던 노드와 중복 되는지 검사합니다. 만약 중복이 된다면 None을 반환하여 새로운 노드가 생성되지 않도록 합니다. 중복이 되지 않는다면 생성된 newNode를 반환합니다. 반환 받은 newNode를 stack에 추가하여 줍니다. 너비 우선 탐색은 깊이 우선 탐색과 매우 유사합니다. 차이점이 있다면 탐색을 하면서 가장 먼저 들어간 노드를 꺼낸다는 것입니다.
결과
깊이 우선 탐색 알고리즘 실행 결과
위의 결과를 트리 형식으로 나타내자면 아래와 같습니다.
너비 우선 탐색 알고리즘 실행 결과
위의 결과를 트리 형식으로 나타내자면 아래와 같습니다.
Leave a comment