A* 알고리즘 코드
Astar Algorithm.py
Astar Algorithm_2(8Puzzle).py
from queue import PriorityQueue
from math import sqrt
class State(object):
def __init__(self, value, parent, start = "801234567", goal="012345678") :
self.children= []
self.parent = parent
self.value = value #"801234567" position을 의미
self.dist = 0 #cost의미
if parent: #parent가 존재한다면
self.path = parent.path[:] #parent의 path를 물려받아 새롭게 추가한다
self.path.append(value)
self.start = parent.start # parent의 start를 따라간다. (start)
self.goal = parent.goal #parent의 goal을 따라간다. (goal)
else:
self.path = [value]
self.start = start
self.goal = goal
def GetDist(self): #뒤에서 정의
pass
def CreateChildren(self): #뒤에서 정의
pass
#cost를 계산, 경로를 찾는 코드
class State_Puzzle(State):
def __init__(self, value, parent, start=0, goal=0):
#상속받은 State객체를 불러옴(State객체의 __init__함수를 실행)
super(State_Puzzle, self).__init__(value, parent, start, goal)
self.dist = self.GetDist() #State_Puzzle을 실행함과 동시에 GetDist()를 실행하겠다.
def GetDist(self):
#goal에 도달 한 경우
if self.value == self.goal:
return 0
dist = 0 #시작 값
# 9줄짜리 goal
# -> 3*3을 의미함
# 한줄에 3개가 있따.
# 3개 -> size
# self.goal = '012345678'
# self.goal = '876543210'
# len(self.goal) = 9
# 801
# 345
# 672
# 012
# 345
# 678
size = sqrt(len(self.goal)).real #한 줄에 몇개 있는가, 실수 값으로 표현
# 휴리스틱 계산 (Manhattan distance로 계산)
for n in range(len(self.goal)):
piece = self.goal[n]
# 목표 상태(goal state)를 2D로 표현하면 그 위치는 어떻게 되는가
# goal state = "012345678"
goal_x = int(n / size) # 1 (4를 기준으로)
goal_y = n - goal_x * size # 1 (나머지와 같은 의미)
# 줄글로 표현되어있는 퍼즐을 시제로 2D space로 표현했을 때 x, y 좌표가 무엇인가
# 현재 상태(goal state)를 2D로 표현하면 그 위치는 어떻게 되는가
# self.value "801234567"
value_x = int(self.value.index(piece) / size)
value_y = self.value.index(piece) - value_x * size
dist += abs(goal_x - value_x) + abs(goal_y - value_y) #heuristic, 앞으로 goal까지 몇칸을 움직여야 하는지 알 수 없...
#현재 6이라는 piece가 (2,1 )위치에 있고,
# 사실 목표로하는 state에서, 6은 (2,0)위치에 있어야 함
# -> "6"이라는 piece에 대한 cost를, |2-2| + |1-0|이라고 heuristic하게 정의한다. (맨하탄 디스턴스)
#dist = 1 + 1 + 2 + 0 + 0 + 0 + 0 + 0 + 4 -> 라고 heuristic을 정의할 것
# dist = h
# len(self.path) = g # 현재 상태로 오기 위해서 실제로 몇번 움직였나
# f = g + h로 놓고, f를 최소화하는 방향으로 A*를 돌릴 것이다.
return dist + len(self.path)
def CreateChildren(self):
size = int(sqrt(len(self.goal)).real)
if not self.children:
# self.value = "823407561"
i = self.value.index("0")
# 현재 상태에서, 0의 위치를 확인
# 0의 상하좌우를 봐서, 움직일 수 있는 state가 있는지 확인한다.
if not int(i % size) == size -1:
val = self.value #"823407561"
val = val[:i] + val[i] + val[i-1] + val[i+1:] # "823" + "0" + "4" + "7561"
child = State_Puzzle(val, self)
self.children.append(child)
if not int(i % size) == 0 : #0의 위치가 맨 아랫줄에 있지 않다면(0이 위치하는 index가 6/7/8이 아니라면)
val = self.value
val = val[:i-1] + val[i] + val[i-1] + val[i+1:]
child = State_Puzzle(val, self)
self.children.append(child)
if i>size - 1 : #0의 위치가 맨 윗줄에 있지 않다면(0이 위치하는 index가 0/1/2가 아니라면)
val = self.value
val = value[:i-size] + val[i] + val[i-size+1:i] + val[i-size] + val[i+1:] # 8 + 0 + 34+ 2 + 7561
child = State_Puzzle(val, self)
self.children.append(child)
# Astar 알고리즘 실행
class Astar_solver:
def __init__(self, start, goal):
self.path = []
self.visitedQueue = [] #closed list
self.priorityQueue = PriorityQueue() # 우선순위 queue(비용과 node를 함께 넣는 개념), open list에 해당
self.start = start
self.goal = goal
def Solve(self):
# parent는 해당 state를 방문하기 전에 어떤 static를 거쳐왔는지를 저장하는 list
# start는 시작지점 state, goal은 목표지점 state
# (현재상태), parent, start, goal)
startState = State_Puzzle(self.start, [], self.start, self.goal)
# count는 A*에 직접적으로 이용되지는 않을 것.
# 코드를 돌리는 이용자 입장에서, A*알고리즘을 통해 총 몇번의 탐색 과정을 거쳤는지 확인하기 위함
count = 0 #아무것도 세지 않은 상태.
# priorityQueue는 fringe의 개념, 탐색 후보군을 모아놓는 list
# (해당 후보군에 대한 cost, 해당 후보군을 몇번째로 탐색했는가, 탐색 후보군 state)
# 여기서 해당 후보군에 대한 cost가 낮은 순서대로 priorityQuue에서 꺼내 탐색할 예정
self.priorityQueue.put((0, count, startState)) #제일 먼저, start state를 집어넣는다. start state에 대한 cost = 0
# 앞서 정의해둔 cost에 따라, 비용을 최소화하는 방향으로 탐색을 진행하겠다.
# self.priorityQueue는 open list와 유사한 개념
# self.visitedQueue는 closed list와 유사한 개념
# while loop안에서는 priorityQueue(open list)에 있는 state를 한개 한개씩 꺼내서 goal state인지 확인하고, 아니라면 다음 state(children)을 확인하는 과정이 진행됩니다.
# 1. priorityQueue에서 하나의 state를 뺀다
# 2. 해당 state가 goal인지 확인하고, 아니라면 해당 state의 다음 state를 priorityQueue에 추가한다.
# 3. 이 과정을 self.path가 없거나, priorityQueue가 배어있을 때 까지 반복합니다
# priorityQueue가 비어있을 때 까지 반복함이라 함은, startstate에서부터 탐색을 시작했을 때, 도달할 수 있는 모든 경로를 고려한다는 의미로
# self.path가 비어있을 때까지 반복이라 함은 goal을 찾을 때 까지 반복한다는 의미
while(not self.path and self.priorityQueue.qsize()):
closestChild = self.priorityQueue.get()[2] # cost가 가장 낮은 state를 뽑습니다.
closestChild.CreateChildren() #뽑은 대상에 대해서, 다음 탐색 후보군을 탐색합니다.
self.visitedQueue.append(closestChild.value) # 현재 탐색하고 있는 state가, 이전에 탐색해본 노드가 아닐 경우에만 돌아간다.
for child in closestChild.children: #뽑은 대상에 대한 다음 탐색 후보군들, 이들에 대한 cost 산출
if child.value not in self.visitedQueue: #child에는 child로 오기까지 어떤 state를 거쳐 왔는지에 대한 정보가 path에 저장되어있음
count += 1 #몇번째로 해당 state를 탐색하는지.
if not child.dist: #child.dist=0인 경우. 이는 곧 goal을 찾은 경우를 의미함
self.path = child.path # child에넌 child로 오기까지 어떤 state를 거쳐 왔는지에 대한 정보가 path에 저장되어있음
break
self.priorityQueue.put((child.dist, count, child)) # goal을 찾지 못한 경우에는 cost, count, child를 openlist에 추가하여 다음 탐색 단계에서
if not self.path:
#위 while 루프가, goal을 찾음으로써 끝난다면 self.path = []이므로 여기에 걸리지않음
#모든 state를 탐새갷ㅆ는데 최종 goal을 찾지 못한 경우에만 이 if에 걸려서 path를 찾을 수 없다는 문장이 출력됨
print("Goal of " + self.goal + "is not possible")
return self.path
start = ("801526347")
goal = ("012345678")
print('starting...')
a = Astar_solver(start, goal)
a.Solve()
for i in range(len(a.path)):
print(i)
print(a.path[i][:3])
print(a.path[i][3:6])
print(a.path[i][6:9])
print('\n')
JH.velog