Best-First Search(최선우선탐색) / A* 알고리즘 이용한 8-puzzle 문제

8-puzzle을 파이썬으로 프로그래밍 해보자

 
문제는 다음과 같다 initial 초기의 배열에 있는 원소를 한번씩 움직여서 내가 원하는 배열(goal)을 찾게되면 탐색을 종료하고 goal이라는 배열을 반환하면 된다.

---

Best-First Search(최선우선탐색)

 

최선우선탐색은 확장 중인 노드들 중에서 목표 노드까지 남은거리가 가장 짧은 노드를 확장하여 탐색하는 방법을 말한다.

 

f(n) = h(n) 함수로 표현 할 수 있으며, h(n)은 n이라는 지점에서 가장 저렴한 비용의 예상비용이다.

import queue

# 상태를 나타내는 클래스
class State:
    def __init__(self, board, goal, moves=0):
        self.board = board
        self.moves = moves
        self.goal = goal

    # i1과 i2를 교환하여서 새로운 상태를 반환한다. 
    def get_new_board(self, i1, i2, moves):
        new_board = self.board[:]
        new_board[i1], new_board[i2] = new_board[i2], new_board[i1]
        return State(new_board, self.goal, moves)
    
    #자식 노드를 확장하여서 리스트에 저장하여서 반환한다. 
    def expand(self, moves):
        result = []
        i = self.board.index(0)# 숫자 0(빈칸)의 위치를 찾는다. 
        if not i in [0, 1, 2] :# UP 연산자 
            result.append(self.get_new_board(i, i-3, moves))
        if not i in [0, 3, 6] :# LEFT 연산자 
            result.append(self.get_new_board(i, i-1, moves))
        if not i in [2, 5, 8]:# DOWN 연산자 
            result.append(self.get_new_board(i, i+1, moves))
        if not i in [6, 7, 8]:# RIGHT 연산자 
            result.append(self.get_new_board(i, i+3, moves))
        return result
    
    #f(n)을 계산하여 반환한다.
    def f(self):
        return self.h()
    
    #휴리스틱 함수 값인 h(n)을 계산하여 반환한다.
    #현재 제 위치에 있지 않은 타일의 개수를 리스트 함축으로 계산한다.
    def h(self):
        return sum([1 if self.board[i] != self.goal[i] else 0 for i in range(8)])
    
    #상태와 상태를 비교하기 위해 less than 연산자를 정의한다.
    def __lt__(self, other):
        return self.f() < other.f()
    
    # 객체를 출력할 때 사용한다. 
    def __str__(self):
        return "------------------ f(n)=" + str(self.f()) +"\n"+\
        "------------------ h(n)=" + str(self.h()) +"\n"+\
        str(self.board[:3]) +"\n"+\
        str(self.board[3:6]) +"\n"+\
        str(self.board[6:]) +"\n"+\
        "------------------"

# 초기 상태
puzzle = [2, 8, 3, 
          1, 6, 4, 
          7, 0, 5]

# 목표 상태
goal = [1, 2, 3, 
        8, 0, 4, 
        7, 6, 5]

# open 리스트는 우선순위 큐로 생성한다. 
open_queue = queue.PriorityQueue()
open_queue.put(State(puzzle, goal))

closed_queue = [ ]
moves = 0

while not open_queue.empty():
    current = open_queue.get()
    print(current)
    
    if current.board == goal:
        print("탐색 성공")
        print(moves)
        break
        
    moves = current.moves + 1
    
    for state in current.expand(moves):
        if state not in closed_queue:
            open_queue.put(state)
    closed_queue.append(current)
else:
    print ('탐색 실패')

 

---

A* 알고리즘

 

A* 알고리즘은 최선우선탐색 알고리즘에서 현재까지의 비용을 추가하면 된다.

 

f(n) = g(n) + h(n) 함수로 표현 할 수 있다.

 

g(n) : 시작 노드에서 현재 노드 𝑛 까지의 비용이다.

h(n) : 현재 노드 𝑛 에서 목표(goal)까지의 비용을 말한다.

f(n) : 노드 𝑛 을 경유하여 목표까지 도달 하는데 드는 전체 비용을 말한다.

 

import queue

class State:
    def __init__(self, board, goal, moves=0):
        self.board = board
        self.moves = moves
        self.goal = goal
        # f(n) = g(n) + h(n) 계산
        self.f_value = self.g() + self.h()

    def get_new_board(self, i1, i2, moves):
        new_board = self.board[:]
        new_board[i1], new_board[i2] = new_board[i2], new_board[i1]
        return State(new_board, self.goal, moves)

    def expand(self, moves):
        result = []
        i = self.board.index(0)  # 숫자 0(빈칸)의 위치를 찾는다.
        if i not in [0, 1, 2]:  # UP 연산자
            result.append(self.get_new_board(i, i-3, moves))
        if i not in [0, 3, 6]:  # LEFT 연산자
            result.append(self.get_new_board(i, i-1, moves))
        if i not in [2, 5, 8]:  # RIGHT 연산자
            result.append(self.get_new_board(i, i+1, moves))
        if i not in [6, 7, 8]:  # DOWN 연산자
            result.append(self.get_new_board(i, i+3, moves))
        return result

    def g(self):
        return self.moves

    def h(self):
        # 현재 위치에 있지 않은 타일의 개수를 계산
        return sum(1 for i in range(9) if self.board[i] != self.goal[i] and self.board[i] != 0)

    def __lt__(self, other):
        return self.f_value < other.f_value

    def __str__(self):
        return "f(n)=" + str(self.f_value) + "\n" + \
               "h(n)=" + str(self.h()) + "\n" + \
               str(self.board[:3]) + "\n" + \
               str(self.board[3:6]) + "\n" + \
               str(self.board[6:]) + "\n" + \
               "------------------"

 

# 초기 상태
puzzle = [2, 8, 3, 
          1, 6, 4, 
          7, 0, 5]

# 목표 상태
goal = [1, 2, 3, 
        8, 0, 4, 
        7, 6, 5]

open_queue = queue.PriorityQueue()
open_queue.put(State(puzzle, goal))

closed_set = set()

while not open_queue.empty():
    current = open_queue.get()
    print(current)

    if current.board == goal:
        print("탐색 성공")
        print("총 이동 횟수:", current.moves)
        break

    for state in current.expand(current.moves + 1):
        if tuple(state.board) not in closed_set:
            open_queue.put(state)
            closed_set.add(tuple(state.board))
else:
    print('탐색 실패')