A star 알고리즘

Posted on: 2019년 06월 03일 2019년 06월 03일
Categories: 강의자료, 자료구조

휴리스틱 탐색
1. 해답을 구하기 위해 솔루션 공간을 탐색할 때 사용하는 기법
2. 기존의 깊이우선탐색(DFS), 너비우선탐색(BFS) 등의 방법은 해답을 구하기까지 많은 시간 소요
3. 경험에 따라 명백히 잘못된 방안을 제거해 탐색 공간을 좁혀가는 방법, 여기서 경험이 휴리스틱임
4. 휴리스틱(heuristic)을 적용하여 탐색 속도를 향상
5. 주어진 정보나 규칙을 이용해 불필요한 경로를 걸러내는 정보 탐색(information search) 방법
A*(A star) 알고리즘
1. 휴리스틱 탐색 방법 중 하나
2. 시작 위치에서 목적지까지의 최소 비용이 드는 경로를 찾아가지 위해 3개의 함수 사용
3. 함수 1 : G(x) = 시작 위치로부터 현재까지 소요되는 비용
4. 함수 2 : H(x) = 현재위치에서 목적지까지의 예상 비용
5. 함수 3 : F(x) = G(x) + H(x) ; 현재까지의 비용과 예상비용의 합
미로찾기에 사용되는 그래프이론 : URL Sample,
미로 찾기에 A* 적용 과정 : 상하좌우의 4방향 이웃만 사용.

opened_list = ( )
closed_list = ( )
1. 시작 위치를 opened_list에 추가
2. opened_list에 노드가 없을 때까지 반복
  1. opened_list에서 F가 가장 작은 노드(cur_node)를 가져옴
  2. cur_node를 opened_list에서 삭제
  3. cur_node를 closed_list에 추가
  4. 목적지에 도착하면 경로를 추출한 후 리턴
    1. 현재 노드가 None이 될 때까지 반복
      1. path에 현재 노드의 위치 저장
      2. 현재 노드를 현재 노드의 부모로 변경
    2. path 리턴
  5. cur_node의 상하좌우의 G,H,F를 구함
    1. 상하좌우의 위치가 벽이거나 미로 밖이면 생략
    2. 상하좌우의 위치가 closed_list에 있으면 생략
    3. 상하좌우의 위치가 opened_list에 있고 기존 노드보다 G가 작다면 새 값으로 교체
미로 찾기에 A* 적용 과정 : 상하좌우/대각선4개 모두 8방향 이웃 사용

A* 알고리즘을 직접 구현하여 미로 찾기

미로 만들기 : 제공된 엑셀파일을 이용하여 미로 만들기

파이썬으로 미로 출력하기

MAP = """
##################################
#O#         #       #            #
# # ### # # # # ### # # ###### # #
#     #   #  ##   # # #        # #
# ### ### ### ### #   ###### # ###
# # #   # #     # # # #      # #X#
# # # ### # ### # # # ## ### # # #
#   #   # #   # #   #    # # # # #
# # # ### # ###   # # #### # #   #
# #    #        # #        #     #
##################################
"""
maze_ini = [list(x) for x in MAP.split("\n") if x]

for y in range(len(maze_ini)):    # A-star 알고리즘 결과 출력
    for x in range(len(maze_ini[y])):
        print(maze_ini[y][x], end='')
    print()

MAP = """

##################################

#O# # # #

# # ### # # # # ### # # ###### # #

# # # ## # # # # #

# ### ### ### ### # ###### # ###

# # # # # # # # # # #X#

# # # ### # ### # # # ## ### # # #

# # # # # # # # # # # #

# # # ### # ### # # #### # # #

# # # # # # #

##################################

"""

maze_ini = [list(x) for x in MAP.split("\n") if x]

for y in range(len(maze_ini)): # A-star 알고리즘 결과 출력

for x in range(len(maze_ini[y])):

print(maze_ini[y][x], end='')

print()

Node 클래스 생성 : 맨 앞쪽에 추가하고 이전 코드 MAP과는 2줄 띄기

class Node:  # 클래스 생성
    def __init__(self, parent=None, location=None):
        self.parent = parent
        self.location = location

        self.G = 0
        self.H = 0
        self.F = 0

    def __eq__(self, other):
        return self.location == other.location

    def is_inside(self, maze):
        if (self.location[0] < 0) or (self.location[1] < 0) or (self.location[0] > len(maze) - 1) or (self.location[1] > len(maze[0]) - 1):
            return False
        else:
            return True

class Node: # 클래스 생성

def __init__(self, parent=None, location=None):

self.parent = parent

self.location = location

self.G = 0

self.H = 0

self.F = 0

def __eq__(self, other):

return self.location == other.location

def is_inside(self, maze):

if (self.location[0] < 0) or (self.location[1] < 0) or (self.location[0] > len(maze) - 1) or (self.location[1] > len(maze[0]) - 1):

return False

else:

return True

get_location(maze, v) 메소드 추가 : Node 클래스 아래에 추가(2줄 띄기)

def get_location(maze, v):
    for y in range(len(maze)):
        for x in range(len(maze[y])):
            if maze[y][x] == v:
                maze[y][x] = " "
                return y, x     # (y, x)로 리턴

def get_location(maze, v):

for y in range(len(maze)):

for x in range(len(maze[y])):

if maze[y][x] == v:

maze[y][x] = " "

return y, x # (y, x)로 리턴

astar() 메소드 추가 : get_location(maze, v) 메소드 아래에 추가(2줄 띄기)

def astar(maze, start, goal):  # AStar 알고리즘
    start = Node(parent=None, location=start)
    goal = Node(parent=None, location=goal)

    opened_list = []
    closed_list = []

    opened_list.append(start)  # 시작 위치를 opened_list에 추가

    while opened_list:  # opened_list가 빌 때까지 반복
        cur_node = opened_list[0]

        for element in opened_list:   # 가장 작은 F값을 가지는 노드 찾기
            if element.F < cur_node.F:
                cur_node = element

        opened_list.remove(cur_node)
        closed_list.append(cur_node)

        if cur_node == goal:   # 도착지에 도착하면 멈추고 경로를 추출한 뒤 리턴
            path_list = []
            node = cur_node

            while node is not None:
                path_list.append(node.location)
                node = node.parent

            return path_list[::-1]

        for pos in [(0, -1), (0, 1), (-1, 0), (1, 0)]:     # 상하좌우 4방향의 위치에 대한 F 계산
            cur_pos = ((cur_node.location[0] + pos[0]), (cur_node.location[1] + pos[1]))
            new_node = Node(parent=cur_node, location=cur_pos)

            # 현 위치가 미로 밖이면 무시
            if not new_node.is_inside(maze):
                continue
            # if (cur_pos[0] < 0) or (cur_pos[1] < 0) \
            #         or (cur_pos[0] > len(maze) - 1) or (cur_pos[1] > len(maze[0]) - 1):
            #      continue

            if maze[cur_pos[0]][cur_pos[1]] == "#":     # 미로에서 현 위치가 벽이면 무시
                continue

            if new_node in closed_list:    # 미로에서 현 노드가 closed_list에 있다면 무시
                continue

            # 현 위치의 F, G, H 구하기
            new_node.G = (cur_node.G + 1)
            new_node.H = (((cur_pos[0] - goal.location[0]) ** 2) ** 0.5) + \
                          (((cur_pos[1] - goal.location[1]) ** 2) ** 0.5)
            new_node.F = (new_node.G + new_node.H)

            for element in opened_list:
                if (new_node == element) and (new_node.G > element.G):
                    opened_list.remove(element)

            opened_list.append(new_node)

def astar(maze, start, goal): # AStar 알고리즘

start = Node(parent=None, location=start)

goal = Node(parent=None, location=goal)

opened_list = []

closed_list = []

opened_list.append(start) # 시작 위치를 opened_list에 추가

while opened_list: # opened_list가 빌 때까지 반복

cur_node = opened_list[0]

for element in opened_list: # 가장 작은 F값을 가지는 노드 찾기

if element.F < cur_node.F:

cur_node = element

opened_list.remove(cur_node)

closed_list.append(cur_node)

if cur_node == goal: # 도착지에 도착하면 멈추고 경로를 추출한 뒤 리턴

path_list = []

node = cur_node

while node is not None:

path_list.append(node.location)

node = node.parent

return path_list[::-1]

for pos in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # 상하좌우 4방향의 위치에 대한 F 계산

cur_pos = ((cur_node.location[0] + pos[0]), (cur_node.location[1] + pos[1]))

new_node = Node(parent=cur_node, location=cur_pos)

# 현 위치가 미로 밖이면 무시

if not new_node.is_inside(maze):

continue

# if (cur_pos[0] < 0) or (cur_pos[1] < 0) \

# or (cur_pos[0] > len(maze) - 1) or (cur_pos[1] > len(maze[0]) - 1):

# continue

if maze[cur_pos[0]][cur_pos[1]] == "#": # 미로에서 현 위치가 벽이면 무시

continue

if new_node in closed_list: # 미로에서 현 노드가 closed_list에 있다면 무시

continue

# 현 위치의 F, G, H 구하기

new_node.G = (cur_node.G + 1)

new_node.H = (((cur_pos[0] - goal.location[0]) ** 2) ** 0.5) + \

(((cur_pos[1] - goal.location[1]) ** 2) ** 0.5)

new_node.F = (new_node.G + new_node.H)

for element in opened_list:

if (new_node == element) and (new_node.G > element.G):

opened_list.remove(element)

opened_list.append(new_node)

astar()를 호출하고 결과를 생성하는 코드 추가

start_loc = get_location(maze_ini, 'O')
goal_loc = get_location(maze_ini, 'X')
path = astar(maze_ini, start_loc, goal_loc)

for point in path:
    maze_ini[point[0]][point[1]] = '*'
maze_ini[start_loc[0]][start_loc[1]] = 'O'
maze_ini[goal_loc[0]][goal_loc[1]] = 'X’

start_loc = get_location(maze_ini, 'O')

goal_loc = get_location(maze_ini, 'X')

path = astar(maze_ini, start_loc, goal_loc)

for point in path:

maze_ini[point[0]][point[1]] = '*'

maze_ini[start_loc[0]][start_loc[1]] = 'O'

maze_ini[goal_loc[0]][goal_loc[1]] = 'X’

실행 결과

전체 코드

class Node:  # 클래스 생성
    def __init__(self, parent=None, location=None):
        self.parent = parent
        self.location = location

        self.G = 0
        self.H = 0
        self.F = 0

    def __eq__(self, other):
        return self.location == other.location

    def is_inside(self, maze):
        if (self.location[0] < 0) or (self.location[1] < 0) or (self.location[0] > len(maze) - 1) or (self.location[1] > len(maze[0]) - 1):
            return False
        else:
            return True


def get_location(maze, v):
    for y in range(len(maze)):
        for x in range(len(maze[y])):
            if maze[y][x] == v:
                maze[y][x] = " "
                return y, x     # (y, x)로 리턴


def astar(maze, start, goal):  # AStar 알고리즘
    start = Node(parent=None, location=start)
    goal = Node(parent=None, location=goal)

    opened_list = []
    closed_list = []

    opened_list.append(start)  # 시작 위치를 opened_list에 추가

    while opened_list:  # opened_list가 빌때까지 반복
        cur_node = opened_list[0]

        for element in opened_list:   # 가장 작은 F값을 가지는 노드 찾기
            if element.F < cur_node.F:
                cur_node = element

        opened_list.remove(cur_node)
        closed_list.append(cur_node)

        if cur_node == goal:   # 도착지에 도착하면 멈추고 경로를 추출한 뒤 리턴
            path_list = []
            node = cur_node

            while node is not None:
                path_list.append(node.location)
                node = node.parent

            return path_list[::-1]

        for pos in [(0, -1), (0, 1), (-1, 0), (1, 0)]:     # 상하좌우 4방향의 위치에 대한 F 계산
            cur_pos = ((cur_node.location[0] + pos[0]), (cur_node.location[1] + pos[1]))
            new_node = Node(parent=cur_node, location=cur_pos)

            # 현 위치가 미로 밖이면 무시
            if not new_node.is_inside(maze):
                continue
            # if (cur_pos[0] < 0) or (cur_pos[1] < 0) \
            #         or (cur_pos[0] > len(maze) - 1) or (cur_pos[1] > len(maze[0]) - 1):
            #      continue

            if maze[cur_pos[0]][cur_pos[1]] == "#":     # 미로에서 현 위치가 벽이면 무시
                continue

            if new_node in closed_list:    # 미로에서 현 노드가 closed_list에 있다면 무시
                continue

            # 현 위치의 F, G, H 구하기
            new_node.G = (cur_node.G + 1)
            new_node.H = (((cur_pos[0] - goal.location[0]) ** 2) ** 0.5) + \
                          (((cur_pos[1] - goal.location[1]) ** 2) ** 0.5)
            new_node.F = (new_node.G + new_node.H)

            for element in opened_list:
                if (new_node == element) and (new_node.G < element.G):
                    opened_list.remove(element)
            opened_list.append(new_node)


MAP = """
##################################
#O#         #       #            #
# # ### # # # # ### # # ###### # #
#     #   #  ##   # # #        # #
# ### ### ### ### #   ###### # ###
# # #   # #     # # # #      # #X#
# # # ### # ### # # # ## ### # # #
#   #   # #   # #   #    # # # # #
# # # ### # ###   # # #### # #   #
# #    #        # #        #     #
##################################
"""
maze_ini = [list(x) for x in MAP.split("\n") if x]

start_loc = get_location(maze_ini, 'O')
goal_loc = get_location(maze_ini, 'X')
path = astar(maze_ini, start_loc, goal_loc)

for point in path:
    maze_ini[point[0]][point[1]] = '*'
maze_ini[start_loc[0]][start_loc[1]] = 'O'
maze_ini[goal_loc[0]][goal_loc[1]] = 'X'

for y in range(len(maze_ini)):    # A-star 알고리즘 결과 출력
    for x in range(len(maze_ini[y])):
        print(maze_ini[y][x], end='')
    print()

100

101

102

103

104

105

106

107

108

109

110

111

112

113

class Node: # 클래스 생성

def __init__(self, parent=None, location=None):

self.parent = parent

self.location = location

self.G = 0

self.H = 0

self.F = 0

def __eq__(self, other):

return self.location == other.location

def is_inside(self, maze):

if (self.location[0] < 0) or (self.location[1] < 0) or (self.location[0] > len(maze) - 1) or (self.location[1] > len(maze[0]) - 1):

return False

else:

return True

def get_location(maze, v):

for y in range(len(maze)):

for x in range(len(maze[y])):

if maze[y][x] == v:

maze[y][x] = " "

return y, x # (y, x)로 리턴

def astar(maze, start, goal): # AStar 알고리즘

start = Node(parent=None, location=start)

goal = Node(parent=None, location=goal)

opened_list = []

closed_list = []

opened_list.append(start) # 시작 위치를 opened_list에 추가

while opened_list: # opened_list가 빌때까지 반복

cur_node = opened_list[0]

for element in opened_list: # 가장 작은 F값을 가지는 노드 찾기

if element.F < cur_node.F:

cur_node = element

opened_list.remove(cur_node)

closed_list.append(cur_node)

if cur_node == goal: # 도착지에 도착하면 멈추고 경로를 추출한 뒤 리턴

path_list = []

node = cur_node

while node is not None:

path_list.append(node.location)

node = node.parent

return path_list[::-1]

for pos in [(0, -1), (0, 1), (-1, 0), (1, 0)]: # 상하좌우 4방향의 위치에 대한 F 계산

cur_pos = ((cur_node.location[0] + pos[0]), (cur_node.location[1] + pos[1]))

new_node = Node(parent=cur_node, location=cur_pos)

# 현 위치가 미로 밖이면 무시

if not new_node.is_inside(maze):

continue

# if (cur_pos[0] < 0) or (cur_pos[1] < 0) \

# or (cur_pos[0] > len(maze) - 1) or (cur_pos[1] > len(maze[0]) - 1):

# continue

if maze[cur_pos[0]][cur_pos[1]] == "#": # 미로에서 현 위치가 벽이면 무시

continue

if new_node in closed_list: # 미로에서 현 노드가 closed_list에 있다면 무시

continue

# 현 위치의 F, G, H 구하기

new_node.G = (cur_node.G + 1)

new_node.H = (((cur_pos[0] - goal.location[0]) ** 2) ** 0.5) + \

(((cur_pos[1] - goal.location[1]) ** 2) ** 0.5)

new_node.F = (new_node.G + new_node.H)

for element in opened_list:

if (new_node == element) and (new_node.G < element.G):

opened_list.remove(element)

opened_list.append(new_node)

MAP = """

##################################

#O# # # #

# # ### # # # # ### # # ###### # #

# # # ## # # # # #

# ### ### ### ### # ###### # ###

# # # # # # # # # # #X#

# # # ### # ### # # # ## ### # # #

# # # # # # # # # # # #

# # # ### # ### # # #### # # #

# # # # # # #

##################################

"""

maze_ini = [list(x) for x in MAP.split("\n") if x]

start_loc = get_location(maze_ini, 'O')

goal_loc = get_location(maze_ini, 'X')

path = astar(maze_ini, start_loc, goal_loc)

for point in path:

maze_ini[point[0]][point[1]] = '*'

maze_ini[start_loc[0]][start_loc[1]] = 'O'

maze_ini[goal_loc[0]][goal_loc[1]] = 'X'

for y in range(len(maze_ini)): # A-star 알고리즘 결과 출력

for x in range(len(maze_ini[y])):

print(maze_ini[y][x], end='')

print()

whan0623

517