무슨 실험인가요?
칸으로 나뉜 지도에서 출발 칸에서 도착 칸까지 가장 빨리 가는 길을 컴퓨터가 어떻게 찾는지 눈으로 봅니다. 풀 한 칸을 지나는 데는 1분, 늪 한 칸은 기본 3분이 걸리고 벽은 지나갈 수 없습니다. 바로 앞에 늪이 있으면 돌아가는 편이 빠를 수 있어서, 눈으로 보기엔 먼 길이 더 빠른 길이 됩니다. 내비게이션이 가끔 먼 길로 안내하는 것도 같은 이유입니다.
두 가지 방법을 겨뤄 봅니다. 다익스트라는 지금까지 걸린 시간이 가장 짧은 칸부터 차례로 방문해, 출발 칸에서 둥글게 번지듯 퍼집니다. A*는 여기에 "도착까지 남은 가로·세로 칸 수"라는 어림값을 더해서, 도착 쪽으로 치우쳐 방문합니다. 둘 다 같은 최단 길을 찾지만, 얼마나 많은 칸을 뒤져 봤는지가 다릅니다.
조건을 바꾸면
- 늪 한 칸 시간을 1분으로 하면 늪이 풀과 같아서 곧장 가는 길이 가장 빠르고, A*는 13칸만 보고 끝납니다(다익스트라는 73칸). 3분(영상)이면 늪을 돌아가는 18분 길이 늪을 가로지르는 22분 길보다 빨라지고, 100분이면 늪은 사실상 벽처럼 되어 길 비용은 18분으로 같아집니다. 값은 0분부터 9999분까지, 소수도 넣을 수 있습니다.
- 벽과 늪을 직접 그려 보세요. 도착 칸을 벽으로 막으면 "길이 없다"는 답이 나오고, 이때 두 방법은 갈 수 있는 모든 칸을 다 방문합니다.
- 둘 다 비교는 같은 지도에서 두 방법을 같은 속도로 나란히 돌립니다. 끝나면 A*가 몇 % 덜 봤는지 보여 줍니다.
- 곧장 걷기는 늪을 모르고 도착 쪽으로만 가는 길입니다. 최단 길과 시간을 비교하는 용도입니다.
- 지도 크기를 키워도 이 늪 지도(3분)에서는 A*가 다익스트라보다 대략 절반(49~54%) 덜 봅니다. 칸이 작아지면 화면에서 읽을 수 없는 숫자와 비트는 생략되고 점으로만 표시됩니다.
계산 규칙과 한계
영상 계산(sim.py)과 같은 규칙입니다. 상하좌우 네 방향으로만 움직이고, 어떤 칸에 들어갈 때 그 칸의 시간(풀 1분, 늪 N분)이 듭니다. 같은 값일 때 먼저 볼 칸을 고르는 순서(동점 규칙)도 영상과 같아서, 영상 지도(15×9)에서는 숫자가 그대로 나옵니다. 늪 1·2·3·5·10·100분일 때 다익스트라가 방문한 칸은 73·89·91·85·75·70칸, A*는 13·35·43·37·34·34칸이고 길 비용은 12·17·18·18·18·18분입니다. 난수가 없어서 같은 조건이면 언제나 같은 결과입니다.
A*의 어림값은 영상과 달리 남은 칸 수 × min(1, 늪 시간)으로 일반화했습니다. 늪이 풀보다 빠른 값(0.5분 등)에서도 최단 길이 보장되게 하기 위해서입니다. 늪이 1분 이상이면 영상과 완전히 같습니다. "방문한 칸 수"는 도착 칸을 꺼내는 순간까지 센 수입니다.
대각선 이동, 칸마다 다른 도로 종류, 막히는 시간대는 넣지 않은 아주 단순한 모형이라 실제 내비게이션의 계산을 그대로 보여 주지는 않습니다. 영상의 3D 지도 장면과 효과음도 옮기지 않았습니다. 지도는 최대 41×23칸까지 고를 수 있고, 재현 링크로는 더 큰 지도도 열 수 있습니다.
