[python] 8-puzzle problem (2) Heuristic, A*

https://comdoc.tistory.com/entry/python-8-puzzle-problem-1-BFS-DFS

앞서 우리는 맹목적 탐색의 한계를 경험했으니 그에 대한 대안을 찾아보자. 

8 퍼즐을 자주 해보면 본인만의 풀이법이 생긴다. 

본인의 경우 고등학교 때 연예인 사진을 이용한 퍼즐 게임을 만든 적 있고..
번호가 연결된 블록끼리 회전을 하면서
필요한 블록을 채우거나 필요 없는 블록을 빼는 방식으로
퍼즐을 풀었던 기억이 있다. 

사전에서 heuristic(휴리스틱)을 찾아보면 '체험에서 (스스로 발견하는)'이라는 뜻을 가지고 있다. 
이렇게 heuristic 한 방법을 사용하는 탐색법을 heuristic search method(경험적 탐색법)라고 한다. 

위키 백과에는 다음과 같이 설명되어 있다,
휴리스틱(heuristics) 또는 발견법(發見法)이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편 추론의 방법이다.

개인적으론 '완벽한 정답은 아니지만 정답에 가까운 방법을 (경험에 의해) 추론하여 얻은' 정도로 생각한다. 

본인이 발견한 방법은 프로그래밍하기 까다로우니 목표까지의 거리의 합을 사용하자.
이때 목표까지의 거리의 합을 리턴해주는 함수를 휴리스틱 함수라고 한다. 

이때 주의할 점은 순수하게 휴리스틱이 높은 값만 찾아보는 탐색법(Hill-Climbing)을 사용하면 문제가 생긴다. 
휴리스틱이 높은 길만 따라간다면, 막다른 길을 만날 수 있다.
예를 들자면, 앞서 맹목적 탐색에서는 경험한 배열은 제외했다.
거기서 휴리스틱을 도입했을 때, 순수한 힐-클라이밍 법을 사용한다면,
휴리스틱이 높은 값만 찾다가 앞에서 경험한 배열이 나와 버리면 알고리듬은 중단되어 버린다. 

그래서 휴리스틱이 높은 값부터 순차적으로 검색하는 방식(Best-first-Search)으로 코딩해야 한다. 
이는 A* 알고리듬과 유사하다. 

A* 알고리듬의 평가 함수는 'f(n) = g(n) + h(n)'이다. 
g(n)은 n까지 오는 비용, h(n)은 n에서 목표까지의 예상 비용이다. 

이전 코드를 최소한만 수정해 보았다. 

from queue import PriorityQueue
from random import randint


class State:
    goal: str = ''

    def __init__(self, board: str, moves: int = 0):
        self.board = board
        self.moves = moves

    def __lt__(self, other):
        """비교 연산자 < 오버로딩. 우선순위큐를 사용하기 위해 필요함"""
        return self.f() < other.f()

    def f(self):
        """상태함수"""
        return self.g() + self.h()

    def g(self):
        """지금까지 경로 비용"""
        return self.moves

    def h(self):
        """휴리스틱"""
        dist = 0
        size = 3
        for n in range(9):
            piece = self.goal[n]
            goal_x = n // size
            goal_y = n - goal_x * size
            board_x = self.board.index(piece) // size
            board_y = self.board.index(piece) - board_x * size
            dist += abs(goal_x - board_x) + abs(goal_y - board_y)
        return dist


def bfs(start: State, goal: str) -> dict:
    que = PriorityQueue()
    que.put(start)
    marked = {start.board: None}
    while que and (current := que.get()).board != goal:
        for state in expand(current):
            if state.board not in marked:
                marked[state.board] = current.board
                que.put(state)
    return marked


def exchange(state: State, prev_pos: int, new_pos: int) -> State:
    new_board = list(state.board)
    new_board[prev_pos], new_board[new_pos] = new_board[new_pos], new_board[prev_pos]
    return State(''.join(new_board), state.moves + 1)


def expand(state: State) -> list:
    result = []
    position = state.board.index('0')
    if position not in (0, 1, 2):  # UP
        result.append(exchange(state, position, position - 3))
    if position not in (0, 3, 6):  # LEFT
        result.append(exchange(state, position, position - 1))
    if position not in (2, 5, 8):  # RIGHT
        result.append(exchange(state, position, position + 1))
    if position not in (6, 7, 8):  # DOWN
        result.append(exchange(state, position, position + 3))
    return result


def pprint(board: str):
    print(' '.join(board[:3]))
    print(' '.join(board[3:6]))
    print(' '.join(board[6:]))
    print('-----')


def randomize_start() -> str:
    board = []
    while not is_solvable(board):
        board = []
        while len(board) != 9:
            temp = str(randint(0, 8))
            if temp not in board:
                board.append(temp)
    return ''.join(board)


def is_solvable(board: list) -> bool:
    if not board:
        return False
    inversion = 0
    for i in range(len(board) - 1):
        if board[i] == '0':
            continue
        for j in range(i + 1, len(board)):
            if board[j] == '0':
                continue
            if board[i] > board[j]:
                inversion += 1
    return inversion % 2 == 0


def print_path(start: str, goal: str, marked):
    path = []
    node = goal
    while node != start:
        path.append(node)
        node = marked[node]
    path.append(start)
    for each in path[::-1]:
        pprint(each)


def main():
    start = State('123506784')
    # start = State(randomize_start())
    State.goal = '123456780'
    marked = bfs(start, State.goal)
    print_path(start.board, State.goal, marked)
    print(start.board)
    print(len(marked))


if __name__ == '__main__':
    main()

 

1 2 3
5 0 6
7 8 4
-----
1 2 3
0 5 6
7 8 4
-----
1 2 3
7 5 6
0 8 4
-----
1 2 3
7 5 6
8 0 4
-----
1 2 3
7 5 6
8 4 0
-----
1 2 3
7 5 0
8 4 6
-----
1 2 3
7 0 5
8 4 6
-----
1 2 3
7 4 5
8 0 6
-----
1 2 3
7 4 5
0 8 6
-----
1 2 3
0 4 5
7 8 6
-----
1 2 3
4 0 5
7 8 6
-----
1 2 3
4 5 0
7 8 6
-----
1 2 3
4 5 6
7 8 0
-----
123506784
128

128회 반복으로 답을 찾았다. 
3067회 반복했던 맹목적 탐색보다 확연히 반복이 줄었다.
하지만 중간 연산이 많아져서 빨라진지는...