A* 알고리즘

참고
https://mawile.tistory.com/239

1. A* 알고리즘이란?

• 그래프 탐색 기반 경로 계획의 대표적인 알고리즘 중 하나
• 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 휴리스틱(Heruristic) 기반의 그래프 탐색 알고리즘
  • A* 알고리즘의 특징은 경로 계획 시 '추정 비용(=휴리스틱)' 을 고려하여 경로 계획
• A* 알고리즘 관련 용어
  • 열린 목록(Open list) : 아직 방문하지 않은 노드의 집합
  • 닫힌 목록(Closed list) : 이미 방문했거나 갈수없는 노드의 집합
  • 부모 노드 : 전에 방문했던 노드

2. A* 알고리즘의 원리

탐색 방법

순서	행위
1	그래프상에서 모든 정점의 부모노드를 -1로 초기화하고, 비용은 INF(무한대)값으로 설정
2	시작노드의 비용을 0으로 초기화하고, 시작노드의 부모노드는 시작노드를 가르킨다.
3	현재노드를 기준으로 모든 방향의 노드에 대한 비용을 계산한다.
4	비용이 계산된 노드들중 최소비용을 가지는 노드가 다음노드가 된다.
5	비용노드의 부모노드는 현재노드를 가르킨다.
6	3~5를 반복한다.
7	만약 다음노드가 도착노드라면, 탐색을 중지하고 최적의 경로를 계산한다.

최적의 경로를 계산하는 방법

순서	행위
1	도착노드를 스택에 푸쉬(push)한다. (현재 가르키고 있는 노드는 부모노드이다.)
2	현재 가르키고있는 노드의 부모노드를 스택에 푸쉬(push)한다.
3	2를 반복한다.
4	만약 현재 가르키고 있는 노드와 부모노드가 같다면(시작노드라면) 3을 중지한다.
5	그러면 이 스택은 최적의 경로에 대한 정보를 담고 있게 된다.

3. 휴리스틱 기법

탐색하는 방법에서 설명했던 '비용을 계산한다' 부분에는 계산 방법을 담고있다.
이를 평가함수라고 부르는데 평가함수는 다음과 같다.

• $f(n)$ : 비용
• $g(n)$ : 시작 노드에서 노드n(다음 노드)까지의 실제 비용
• $h(n)$ : 노드 n(다음 노드)에서 도착 노드까지의 추정 비용

• 추정 비용
  • 경로 계획 문제에서는 유클리디안 거리 또는 맨해튼 거리 등이 주로 이용된다.
  • 유클리디안 거리(Euclidean distance)
    $\sqrt{(x_{1}-x_{2})^2 + (y_{1}-y_{2})^2}$
  • 맨해튼 거리(Manhattan distance)
    $|{x_{1}-x_{2}| + |y_{1}-y_{2}}|$

4. A* 알고리즘 특징

• 추정 비용을 통해 경로의 탐색이 도착 노드를 향하도록 함
  • 도착 노드에서 멀어질수 있는 노드들을 탐색 범위에서 제외함으로써, 전체적인 탐색 범위가 축소됨에 따라 시간 및 메모리 사용량 등도 감소

• $h(n) = 0$ 일 때, 다익스트라 알고리즘과 동일하게 동작($f(n) = g(n)$, 역추적 방식)

• 열린 목록(Open List) : 탐색 중인 노드들을 저장

• 닫힌 목록(Closed List) : 탐색을 완료한 노드들을 저장

5. 퍼즐 문제

• 숫자판의 숫자를 한 칸씩 움직이면서 목표로 하는 배열이 되도록 하는 것
• 다음과 같은 목표 배열을 가정

• $\color{red}{f(n)}$ = 경로
• $\color{blue} {g(n)}$ = 숫자판을 움직인횟수
• $\color{green}{h(n)}$ = 목표 배열과 다른 위치에 있는 숫자판의 개수

1. 시작 배열

• 빈칸으로 이동할 수 있는 숫자는 5, 6, 7 : 3가지 경우에 대해 비용 계산
  • 5를 움직이는 경우 : 현재 비용($g(n)$) : 1, 추정 비용($h(n)$) : 5 -> 평가 함수($f(n)$) : 6
  • 6을 움직이는 경우 : 현재 비용($g(n)$) : 1, 추정 비용($h(n)$) : 3 -> 평가 함수($f(n)$) : 4
  • 7을 움직이는 경우 : 현재 비용($g(n)$) : 1, 추정 비용($h(n)$) : 5 -> 평가 함수($f(n)$) : 6
• 3가지의 경우 평가 함수가 가장 작은 4를 움직이는 경우를 선택하여, 다음 단계에서 비용을 다시 계산

2. 6을 움직인 경우에서

• 6을 제외하고 빈칸으로 이동할 수 있는 숫자는 1, 4, 8 : 3가지 경우에 대해 비용 계산
  • 1을 움직이는 경우 : 현재 비용(g(n)) : 2, 추정 비용(h(n)) : 3 -> 평가 함수(f(n)) : 5
  • 4을 움직이는 경우 : 현재 비용(g(n)) : 2, 추정 비용(h(n)) : 4 -> 평가 함수(f(n)) : 6
  • 8을 움직이는 경우 : 현재 비용(g(n)) : 2, 추정 비용(h(n)) : 3 -> 평가 함수(f(n)) : 5

• 평가함수가 가장 작은 1의 경우와 8의 경우에 대해 다음 단계에서 비용을 다시 계산

3. 1와 8을 움직인 경우에서
(1) 1을 움직인 경우에서

• 1을 제외하고 빈칸으로 이동할 수 있는 숫자는 2, 7 : 2가지 경우에 대해 비용 계산
  • 2를 움직이는 경우 : 현재 비용(g(n)) : 3, 추정 비용(h(n)) : 3 -> 평가 함수(f(n)) : 6
  • 7을 움직이는 경우 : 현재 비용(g(n)) : 3, 추정 비용(h(n)) : 4 -> 평가 함수(f(n)) : 7

(2) 8을 움직인 경우에서

• 8을 제외하고 빈칸으로 이동할 수 있는 숫자는 2, 3 : 2가지 경우에 대해 비용 계산
  • 2를 움직이는 경우 : 현재 비용(g(n)) : 3, 추정 비용(h(n)) : 2 -> 평가 함수(f(n)) : 5
  • 3을 움직이는 경우 : 현재 비용(g(n)) : 3, 추정 비용(h(n)) : 4 -> 평가 함수(f(n)) : 6
• 1을 움직인 경우와 8을 움직인 경우에서 총 평가 함수 값이 작은 8에서 2를 움직이는 경우를 선택하여, 다음 단계에서 비용을 다시 계산

4. 2를 움직인 경우에서

• 2를 제외하고 빈칸으로 이동할 수 있는 숫자는 1 : 1가지 경우에 대해 비용 계산
  • 1을 움직이는 경우 : 현재 비용(g(n)) : 4, 추정 비용(h(n)) : 1 -> 평가 함수(f(n)) : 5
• 1을 움직인 경우를 가지고 다시 다음 단계에서 비용을 다시 계산

5. 1을 움직인 경우에서

• 1을 제외하고 빈칸으로 이동할 수 있는 숫자는 7, 8 : 2가지 경우에 대해 비용 계산
  • 7을 움직인 경우 : 현재 비용(g(n)) : 5, 추정 비용(h(n)) : 0 -> 평가 함수(f(n)) : 5
  • 8을 움직인 경우 : 현재 비용(g(n)) : 5, 추정 비용(h(n)) : 2 -> 평가 함수(f(n)) : 7
• 최종적으로 추정 비용(h(n))이 0이 나오는 7을 움직여 평가함수 = 5를 구하고 목표 배열에 도착

6. 퍼즐 문제 실습(코드)

class Node:
    def __init__(self, data, level, fval):
        self.data = data  # 현재 노드의 상태 데이터
        self.level = level  # 현재 노드의 깊이 레벨
        self.fval = fval  # 현재 노드의 f값 (f = g + h, 여기서 g는 루트 노드부터 현재 노드까지의 경로 비용, h는 현재 노드에서 목표 노드까지의 예상 비용)

    def generate_child(self):
        x, y = self.find(self.data, '_')  # 현재 상태에서 빈 공간 위치 찾기
        val_list = [[x+1, y], [x, y+1], [x-1, y], [x, y-1]]  # 빈 공간 주변으로 이동할 수 있는 방향 (상, 하, 좌, 우)
        children = []
        for i in val_list:
            child = self.shuffle(self.data, x, y, i[0], i[1])  # 가능한 이동 후보 생성
            if child is not None:
                child_node = Node(child, self.level+1, 0)  # 새로운 자식 노드 생성
                children.append(child_node)
        return children

    def shuffle(self, puz, x1, y1, x2, y2):
        if x2 >= 0 and x2 < len(self.data) and y2 >= 0 and y2 < len(self.data):  # 보드 범위 내에서 이동하는지 확인
            temp_puz = self.copy(puz)  # 보드 복사
            temp = temp_puz[x2][y2]
            temp_puz[x2][y2] = temp_puz[x1][y1]
            temp_puz[x1][y1] = temp
            return temp_puz  # 새로운 상태 반환
        else:
            return None  # 이동이 불가능한 경우 None 반환

    def copy(self, root):
        temp = []  # 복사할 보드
        for i in root:
            t = []
            for j in i:
                t.append(j)
            temp.append(t)  # 보드의 각 행을 복사하여 temp에 추가
        return temp  # 새로운 보드 반환

    def find(self, puz, x): # 공백의 위치를 찾기 위한 함수
        for i in range(0, len(self.data)):
            for j in range(0, len(self.data)):
                if puz[i][j] == x:  # 주어진 문자 x가 있는 위치 찾기 여기서 x는 '_'
                    return i, j  # 해당 위치 반환


class Puzzle: # 퍼즐 크기를 지정된 크기로, 열린 리스트/ 닫힌 리스트를 공백으로 초기화
    def __init__(self, size):
        self.n = size
        self.open = []  # open 리스트 (탐색할 노드들이 들어감)
        self.closed = []  # closed 리스트 (이미 탐색한 노드들이 들어감)

    def accept(self):
        puz = []
        for i in range(0, self.n):
            temp = input().split(" ")  # 사용자로부터 보드 상태 입력 받음
            puz.append(temp)
        return puz  # 입력받은 보드 상태 반환

    def f(self, start, goal): # 평가함수(휴리스틱) 값 계산
        return self.h(start.data, goal) + start.level  # f = g + h 반환

    def h(self, start, goal):  #h(n) 값 계산 함수 현재 배열과 목표 배열의 다른 숫자판 카운트 함수
        temp = 0
        for i in range(0, self.n):
            for j in range(0, self.n):
                if start[i][j] != goal[i][j] and start[i][j] != '_':
                    temp += 1  # 현재 상태와 목표 상태를 비교하여 맞지 않는 타일 수를 카운트하여 반환
        return temp

    def process(self):
        print("초기 퍼즐 상태 입력 : \n")
        start = self.accept()  # 초기 상태 입력 받음
        print("\n")
        print("퍼즐 목표 상태 입력 : \n")
        goal = self.accept()  # 목표 상태 입력 받음

        start = Node(start, 0, 0)  # 초기 노드 생성
        start.fval = self.f(start, goal)  # 초기 노드의 f값 설정
        self.open.append(start)  # 초기 노드를 open 리스트에 추가

        while True:
            cur = self.open[0]  # open 리스트에서 현재 노드 선택
            print("")
            print(" ↓ ")
            print("")
            for i in cur.data:
                for j in i:
                    print(j, end="")
                print("")
                
            print("f 값:", cur.fval)  # 현재 노드의 f값 출력

            if(self.h(cur.data, goal) == 0):  # 현재 상태가 목표 상태와 일치하는지 확인 h(n)함수가 0이면 숫자판 배열이 같으닌가!
                break

            for i in cur.generate_child():  # 현재 노드의 자식 노드들 생성
                i.fval = self.f(i, goal)  # 자식 노드의 f값 설정
                self.open.append(i)  # 자식 노드를 open 리스트에 추가
            self.closed.append(cur)  # 현재 노드를 closed 리스트에 추가
            del self.open[0]  # open 리스트에서 현재 노드 제거

            self.open.sort(key=lambda x: x.fval, reverse=False)  # open 리스트를 f값에 따라 정렬하여 최적의 다음 노드 선택


puz = Puzzle(3)  # 퍼즐 사이즈가 3x3인 퍼즐 객체 생성
puz.process()  # 퍼즐 해결 알고리즘 실행

실행 결과

초기 퍼즐 상태 입력 : 

2 8 3
1 6 4
7 _ 5


퍼즐 목표 상태 입력 : 

1 2 3 
8 _ 4
7 6 5

 ↓ 

283
164
7_5
f 값: 4

 ↓ 

283
1_4
765
f 값: 4

 ↓ 

2_3
184
765
f 값: 5

 ↓ 

283
_14
765
f 값: 5

 ↓ 

_23
184
765
f 값: 5

 ↓ 

123
_84
765
f 값: 5

 ↓ 

123
8_4
765
f 값: 5

위에서 직접 풀어본 결과와 같은 결과가 나옴