A*를 내 손으로 짠다
시뮬레이터 없이 30줄로

6차시 시뮬레이터에서 여러분은 칸마다 세 숫자를 보았습니다. 왼쪽 위에 지나온 비용 g, 오른쪽 위에 남은 어림 h, 가운데 큰 글씨로 f. 한 걸음씩 재생할 때마다 f가 가장 작은 칸이 뽑혔지요. h 배율을 0.1씩 올려 가며 둘러본 칸이 65에서 52로, 다시 21로 줄어드는 것도 보았습니다.

그런데 시뮬레이터는 누군가 미리 만들어 둔 것입니다. 여러분이 한 일은 슬라이더를 민 것이고요. 성취기준 [12인기01-04]는 "정보 이용 탐색 방법을 적용한 인공지능 프로그램을 개발한다"고 적혀 있습니다. 슬라이더를 민 것은 개발이 아닙니다. 오늘의 물음은 그래서 이렇습니다.

말로 답하면 "A*는 h를 함께 본다"입니다. 맞는 말이지만 이 문장으로는 프로그램을 못 만듭니다. 어느 줄, 어느 자리인지를 알아야 만들 수 있어요. 답을 미리 말해 두겠습니다.

바뀌지 않는 부분을 정확히 아는 일이 왜 중요할까요. 8차시에서 우리는 미로가 아닌 문제 — 조각을 밀어 맞추는 8-퍼즐 — 에 오늘 짠 함수를 그대로 옮겨 붙입니다. 그때 astar() 본체는 한 글자도 고치지 않고, 미로와 이웃 함수와 어림 함수만 갈아 끼웁니다. 오늘 "바뀌지 않는 부분"의 경계를 손으로 그어 두는 까닭이 그것입니다.

프론티어는 3차시부터 계속 나온 낱말입니다. 탐색이 하는 일은 결국 두 줄로 줄어듭니다. 대기실에서 하나를 꺼낸다. 그 이웃들을 대기실에 넣는다. 이것을 반복할 뿐이에요.

그러면 알고리즘의 이름을 정하는 것은 무엇일까요. 넣는 방식은 다 같습니다. 다른 것은 누구를 먼저 꺼내느냐 하나뿐입니다.

4차시에서 popleft()를 pop()으로 한 낱말 바꾸었더니 둘러본 칸이 64에서 22로, 경로가 17걸음에서 19걸음으로 달라졌지요. 한 낱말이 알고리즘의 이름을 바꾼 것입니다. 오늘 바꾸는 것도 딱 그만큼입니다.

파이썬에서 우선순위 큐는 heapq로 씁니다. 새 자료형을 배울 필요는 없어요. 보통의 리스트를 넣고 빼는 함수 두 개만 알면 됩니다.

from collections import deque

frontier = deque([START])
while frontier:
    cur = frontier.popleft()
    ...
        frontier.append(n)

import heapq

openq = [(0, START)]
while openq:
    f, cur = heapq.heappop(openq)
    ...
        heapq.heappush(openq, (f값, n))

heappop은 맨 앞의 가장 작은 값을 꺼냅니다. 들어 있는 것이 튜플이면 첫 칸끼리 먼저 견주고, 같으면 둘째 칸으로 넘어가요. 그러니 넣을 때 (우선순위, 칸) 꼴로 넣어 두면 꺼낼 때 자동으로 우선순위가 가장 작은 칸이 나옵니다. 그 우선순위 자리에 무엇을 적느냐가 오늘의 전부입니다.

6차시의 'h 배율' 슬라이더를 기억하나요. 그것을 코드로 옮기면 곱셈 하나가 늘어나는 것으로 끝납니다.

우선순위 = g + w × h

여기서 g는 지나온 비용, h는 남은 어림입니다. g는 이미 걸은 걸음 수라 확실히 아는 값이고, h는 벽을 무시하고 잰 맨해튼 거리라 짐작한 값입니다. 확실한 것과 짐작한 것을 한 저울에 올려 놓고, w로 짐작 쪽의 무게를 조절하는 셈이에요.

w가 0일 때 우선순위는 그냥 g입니다. 지나온 비용이 가장 작은 칸부터 꺼낸다는 뜻이고, 이것이 곧 다익스트라 알고리즘이에요. 세 알고리즘이 서로 다른 프로그램이 아니라 숫자 하나의 차이라는 것은 코드로 옮기고 나서야 보입니다. 시뮬레이터에서는 버튼 세 개가 각각 다른 것처럼 보였지만요.

여기서 A* 구현의 가장 흔한 버그를 미리 만나 두겠습니다. 4차시 BFS에는 없었고 오늘 새로 생기는 문제입니다.

어떤 칸 N에 처음 닿았을 때 비용이 7이었다고 합시다. 그래서 (7+h, N)을 대기실에 넣었어요. 그런데 탐색이 계속되다가 다른 길로 같은 칸 N에 비용 5로 닿는 경로가 나타납니다. BFS에서는 이런 일이 안 생겼습니다 — 가까운 곳부터 층층이 퍼지니 처음 닿은 값이 곧 최선이었으니까요. 우선순위 큐는 층을 건너뛰며 꺼내므로 이 일이 실제로 생깁니다.

• 대기실에 (7+h, N)과 (5+h, N)이 둘 다 들어 있게 됩니다.
• 둘 중 싼 쪽(5)이 먼저 꺼내집니다. 여기까지는 아무 문제가 없어요.
• 문제는 나중에 비싼 쪽(7)도 꺼내진다는 것입니다. 이미 5로 처리를 끝낸 칸을 7이라는 낡은 값으로 다시 처리하면서, 이웃들의 비용과 부모를 7 기준으로 덮어씁니다.
• 덮어쓰기가 되풀이되면 부모 표에 고리가 생깁니다. A의 부모가 B인데 B의 부모가 다시 A인 상태예요. 그러면 목표에서 거꾸로 되짚는 일이 영원히 끝나지 않습니다.

이 버그가 무서운 까닭은 망가지는 모습이 설정마다 다르기 때문입니다. 어떤 설정에서는 대기실이 폭발하고, 어떤 설정에서는 도착은 하는데 경로를 못 만듭니다. 오늘 실습 ③에서 그 차이를 직접 보게 됩니다. 막는 방법은 두 줄입니다.

# ① 낡은 표를 들고 온 손님은 돌려보낸다
if gc > g.get(cur, 10**9):
    continue

# ② 더 싼 길을 찾았을 때만 기록하고 대기실에 넣는다
if ng < g.get(n, 10**9):
    g[n], came[n] = ng, cur
    heapq.heappush(openq, (ng + w * h(n), ng, n))

①은 꺼낸 뒤의 방어이고 ②는 넣기 전의 방어입니다. 둘 다 있어야 해요. ①만 두면 대기실이 쓸데없이 부풀고, ②만 두면 낡은 값이 그대로 처리됩니다.

오늘 쓰는 미로는 4차시부터 계속 쓰던 그 미로입니다. 7행 12열, 벽이 아닌 칸은 65칸, 출발 S는 왼쪽 위 (0,0), 목표 G는 오른쪽 아래 (6,11), 맨해튼 거리는 17이고 최단 경로도 17걸음입니다. 같은 미로에 w만 바꿔 넣으면 이런 숫자가 나옵니다.

표를 세 번 읽어 봅시다.

• 다익스트라가 둘러본 65칸은 벽이 아닌 칸 전부입니다. 목표를 찾고도 멈추지 못하고 결국 미로를 통째로 훑은 셈이에요. h를 안 보면 어느 쪽이 목표에 가까운지 모르니 당연한 결과입니다.
• A*는 52칸으로 줄었는데 경로는 똑같이 17걸음입니다. 13칸을 아꼈는데 잃은 것이 없어요. 이것이 좋은 어림의 값어치입니다.
• 5배로 부풀리면 20칸까지 줄지만 경로가 19걸음이 됩니다. 2걸음을 더 걷는 대가로 둘러본 칸을 65에서 20으로 줄인 것이지요. 이것이 좋은 거래인지 나쁜 거래인지는 문제가 정합니다. 게임 속 유닛이라면 2걸음 손해가 눈에 안 띄지만, 수술 로봇의 경로라면 이야기가 다릅니다.

여기까지가 흔히 말하는 '맞바꿈'입니다. 그런데 w를 1.0에서 0.1씩 올려 보면 이야기가 한 겹 깊어집니다. 값이 바뀌는 지점만 추리면 이렇습니다.

문턱이 두 개이고, 둘 사이가 2.0만큼 떨어져 있습니다. 이 사실이 왜 중요할까요. "w를 올리면 빨라지는 대신 최단을 잃는다"는 흔한 설명은 이 미로에서는 절반만 맞습니다. w가 1.1에서 3.0 사이일 때는 2.5배 빨라지면서 최단도 그대로 지킵니다. 맞바꿈이 아니라 그냥 이득이에요. 이 구간이 있다는 것을 모르면 "안전하게 w=1로 두자"는 결론에 그치게 됩니다.

마지막으로, 부풀리는 쪽만 위험한 까닭입니다. 꺼낸 칸을 f 값별로 나눠 세면 이렇게 나옵니다.

최단 비용이 17이므로 f가 19나 21인 칸은 답이 될 수 없는 칸입니다. 다익스트라가 A*보다 더 꺼낸 13칸은 정확히 그 칸들이에요. h는 절대 음수가 아니니 f = g + h ≥ g이고, 따라서 A*가 꺼내는 칸은 언제나 다익스트라가 꺼내는 칸의 부분집합입니다. 맨해튼 거리는 벽을 무시하고 재므로 벽을 더 세워도 이 관계는 깨지지 않아요. 코드 상자 ②에서 벽을 하나씩·둘씩 전부 세워 보며 이 주장을 시험합니다.

코드를 짜기 전에 답을 먼저 알아 두는 것이 오늘의 순서입니다. 아래 실험실은 여러분이 곧 짤 astar()와 똑같은 규칙으로 이 페이지 안에서 직접 계산합니다. 미리 적어 둔 결과를 펼쳐 보이는 것이 아니라, 여러분이 슬라이더를 놓은 그 w로 그 자리에서 미로를 다시 풉니다. 그러니 조금 뒤 코드가 찍는 숫자와 한 자리도 다르면 안 됩니다. 다르다면 둘 중 하나가 틀린 것이고, 그것을 찾는 것이 오늘 15분의 절반입니다.

대조표 — 내가 적은 값과 계산한 값을 맞춰 본다

6차시 시뮬레이터에서 적어 둔 값이 있으면 그것을 먼저 넣어 보세요. 없으면 위 실험실이나 아래 코드에서 얻은 값을 넣습니다. 대조하기를 누르면 이 페이지가 네 설정을 그 자리에서 다시 풀어 견줍니다.

이제 코드입니다. 아래 상자에 빈칸이 두 곳 있습니다. 개념 2의 저울과 개념 3의 두 줄을 그대로 옮겨 적으면 됩니다. 나머지는 4차시에서 쓰던 것 그대로예요 — MAZE·find()·neighbors()는 한 글자도 바꾸지 않았습니다.

오늘의 실습은 넷입니다. 코드가 찍는 【1】~【3】이 그 자리를 하나씩 맡습니다.

• 실습 ① 빈칸 두 곳을 채운다. ?????가 있는 자리는 둘뿐입니다. 실행해서 【1】에 65/17 · 52/17 · 21/17 · 20/19가 나오면 성공.
• 실습 ② 대조한다. 위 실험실과 6차시에서 적은 값이 【1】과 같은가요? 52가 아니라 65가 나왔다면 빈칸 ①에서 w * h(n)을 빠뜨린 것입니다 — 그러면 배율이 무시되어 어느 w를 넣어도 다익스트라가 됩니다. 오류 없이 조용히 틀리는 가장 흔한 실수예요.
• 실습 ③ 일부러 부순다. 【3】이 조건문을 지운 판을 함께 돌립니다. 세 설정이 서로 다르게 망가지는 것을 확인하세요. 더 확실히 하려면 빈칸 ②에 채운 식을 True로 바꿔 직접 지워 보세요. 그러면 【1】의 네 줄이 전부 ⚠️ 경고로 바뀌고, 【2】의 41줄은 경로 자리가 모두 순환이 됩니다. 그 조건문 하나가 오늘 본 모든 숫자를 떠받치고 있었다는 뜻이에요.
• 실습 ④ 문턱을 잰다. 【2】가 w를 1.0에서 0.1씩 5.0까지 올린 41줄을 그대로 찍습니다. 눈으로 훑어 값이 달라지는 자리를 직접 찾아 보세요. 그다음에 밑에 붙는 요약 세 줄과 맞춰 봅니다. 몇에서 꺾이고 몇에서 깨집니까?

두 번째 코드 상자는 확인 문제 6번의 증거입니다. "벽을 하나 더 세워 A*가 다익스트라보다 더 많이 둘러보게 만들 수 있을까?" 말로 다투기보다 가능한 벽을 전부 세워 보는 편이 빠릅니다. 벽 한 개짜리 58가지와 벽 두 개짜리 1,647가지를 전수로 돌리고, 이어서 꺼낸 칸을 f 값별로 나눠 세어 왜 그런지까지 봅니다. 빈칸은 코드 상자 ①과 똑같은 답이 들어갑니다.

4차시의 BFS 코드와 오늘의 A* 코드를 나란히 놓으면, 실제로 달라진 곳은 이렇습니다.

오늘 얻은 것을 한 줄로 줄이면 이렇습니다. 알고리즘의 이름은 그릇과 우선순위가 정한다. 큐면 BFS, 스택이면 DFS, 우선순위 큐에 g를 넣으면 다익스트라, g + h를 넣으면 A*, g + 5h를 넣으면 부풀린 A*입니다. 다섯 가지가 다섯 개의 프로그램이 아니라 한 프로그램의 다섯 가지 설정이었어요.

그리고 숫자로 확인한 것이 둘입니다. 첫째, 좋은 어림은 공짜로 이득을 준다 — 65칸이 52칸으로 줄었는데 경로는 17걸음 그대로였습니다. 둘째, 문턱은 하나가 아니었다 — 빨라지는 문턱 1.1과 최단이 깨지는 문턱 3.1 사이에 2.0만큼의 안전한 구간이 있었습니다. 첫째만 알면 A*를 쓸 수 있고, 둘째까지 알아야 A*를 얼마나 부풀려도 되는지 판단할 수 있습니다.

✍️ 문제마다 답을 쓰고 제출하기를 누르세요. 제출하면 모범 답안이 열리고, 제출한 답은 선생님께 전달됩니다.