정보 이용 탐색 (Greedy & A*) 시뮬레이터

환경 설정

최대 깊이

최대 자식

가지 위의 숫자는 그 간선(Edge)을 지나는 비용이고, g(n)은 여기까지 든 비용의 합입니다. 트리는 어느 노드(Node)로 가는 길이 하나뿐이라 네 방법이 모두 같은 길을 찾습니다 — 다른 것은 거기까지 몇 개를 확장했는가입니다.
h(n)은 목표까지 남은 칸 수입니다. 노드를 클릭하면 목표가 바뀌고 h(n)도 다시 계산됩니다.

알고리즘 선택

탐색 속도

실행 제어

대기 중

현재 선택

Open Set

Closed Set

최종 경로

맵 편집 (클릭/드래그)

알고리즘 선택

자동 실행 속도

실행 제어

2차원 격자 환경 (15x15)

Open Closed Current Path

칸 안의 숫자는 g(시작점에서 그 칸까지 실제로 온 걸음 수), h(그 칸에서 목표까지 남은 거리의 추정값), f(둘을 합쳐 판단에 쓰는 값)입니다. 여기서 h는 가로 걸음 수와 세로 걸음 수를 더한 맨해튼 거리로, 장애물을 무시하고 셉니다. A*는 f = g + h로, 최상 우선 탐색은 f = h로 다음 칸을 고릅니다.

대기 중

지도 설정

방향 그래프 화살표가 가리키는 쪽으로만 갈 수 있습니다. 간선 비용 길마다 드는 비용이 다릅니다. 꺼 두면 모두 1입니다. 사이클 빙 돌아 제자리로 오는 길이 있습니다. 끄면 트리가 됩니다.

간선 끊기 켜면 간선을 눌러 길을 막을 수 있습니다.

h(n)은 지도에서 목표까지 자로 측정한 직선거리이고, 가지 위의 숫자는 그 길을 지나는 비용입니다. 길이 여럿이라 어느 길을 찾았는가가 방법마다 달라집니다.
설정을 바꾸면 같은 지도를 그 설정으로 다시 그립니다. 노드를 클릭하면 목표가 바뀝니다.

알고리즘 선택

탐색 속도

실행 제어

대기 중

시작점

목표

현재 선택

Open Set

Closed Set

최종 경로

방법	찾은 길	든 비용	확장한 노드

h(n)만 볼 때와 g(n)만 볼 때

이 지도에서 h(n)은 목표까지 자로 측정한 직선거리입니다. 실제로 가야 하는 길은 굽어 있으니, h(n)은 실제로 남은 비용보다 크지 않습니다. h(n)이 이렇게 실제보다 작거나 같으면 A*는 가장 싼 길을 놓치지 않습니다.

최상 우선 탐색은 h(n)만 봅니다. 목표 쪽으로 곧장 달리지만 여기까지 오는 데 든 비용은 고려하지 않습니다. 목표에 가까워 보이는 골목으로 들어섰다가 크게 돌아 나오는 일이 그래서 생깁니다.

반대쪽 극단이 다익스트라 알고리즘입니다. 노드마다 h(n)이 적혀 있어도 쳐다보지 않고 여기까지 든 비용 g(n)이 가장 적은 것부터 확장합니다. 목표가 어느 쪽인지 모르니 시작점에서 사방으로 고르게 번져 나갑니다. 가장 싼 길은 반드시 찾지만, 그 대신 목표와 반대쪽에 있는 노드도 비용이 작으면 먼저 확장합니다.

다익스트라는 h(n)을 0으로 둔 A*와 같은 것입니다. f = g + h에서 h를 0으로 두면 f = g가 되어, 「비용이 가장 적은 것부터」가 그대로 나옵니다. 이 시뮬레이터도 두 방법을 같은 코드로 실행하고 h를 셈에 넣는지만 다르게 합니다. 맹목적 탐색 시뮬레이터의 「균일 비용 탐색」이 바로 이것입니다 — 다익스트라를 목표에 닿는 순간 멈추게 한 것이라 하는 일이 같습니다. 이름이 둘일 뿐 방법은 하나입니다.

트리 탐색 탭에서는 이 차이가 보이지 않았습니다. 트리는 어느 노드로 가는 길이 하나뿐이라 어느 방법이든 모두 같은 길을 찾고, 다른 것은 「몇 개를 확장했는가」뿐이었습니다. 길이 여럿인 그래프에서야 어느 길을 찾았는가가 달라집니다.