))}
CLOSED = {(0,0)(8,NULL), (1,0)(8,(0,0)), (2,0)(8,(1,0))}
4단계
OPEN에서 평가함수가 최소인 노드 (2,1)를 꺼내 확장하고 이를 CLOSED에 넣는다.
새롭게 생성된 노드 (2,2)와 (3,1)의 평가함수를 계산한다.
생성된 노드를 OPEN에 넣는다.
OPEN = {(0,1)(8,(O,O)), (2,2)(8,(2,1)), (3,1)(8,(2,1))}
CLOSED = {(0,0)(8,NULL), (1,0)(8,(0,0)), (2,0)(8,(1,0)), (2,1)(8,(2,0)}
5단계
OPEN에서 평가함수가 최소인 노드 (3,1)를 꺼내 확장하고 이를 CLOSED에 넣는다.
새롭게 생성된 노드 (3,2)와 (4,1)의 평가함수를 계산한다.
생성된 노드를 OPEN에 넣는다.
OPEN = {(0,1)(8,(O,O)), (2,2)(8,(2,1)), (3,2)(8, (3,1)), (4,1)(8,(3,1))}
CLOSED = {(0,0)(8,NULL), (1,0)(8,(0,0)), (2,0)(8,(1,0)), (2,1)(8,(2,0), (3,1)(8,(2,1))}
6단계
OPEN에서 평가함수가 최소인 노드 (4,1)를 꺼내 확장하고 이를 CLOSED에 넣는다.
노드 (4,1)에서는 장애물로 노드를 확장할 수 없다.
OPEN = {(0,1)(8,(O,O)), (2,2)(8,(2,1)), (3,2)(8, (3,1))}
CLOSED = {(0,0)(8,NULL), (1,0)(8,(0,0)), (2,0)(8,(1,0)), (2,1)(8,(2,0),
(3,1)(8,(2,1)), (4,1)(8,(3,1))}
7단계
OPEN에서 평가함수가 최소인 노드 (3,2)를 꺼내 확장하고 이를 CLOSED에 넣는다.
새롭게 생성된 노드 (3,3)와 (4,2)의 평가함수를 계산한다.
생성된 노드를 OPEN에 넣는다.
OPEN = {(0,1)(8,(O,O)), (2,2)(8,(2,1)), (3,3)(8,(3,2)), (4,2)(8,(3,2))}
CLOSED = {(0,0)(8,NULL), (1,0)(8,(0,0)), (2,0)(8,(1,0)), (2,1)(8,(2,0),
(3,1)(8,(2,1)), (4,1)(8,(3,1)), (3,2)(8, (3,1))}
8단계
OPEN에서 평가함수가 최소인 노드 (3,3)를 꺼내 확장하고 이를 CLOSED에 넣는다.
새롭게 생성된 노드 (2,3)의 평가함수를 계산한다.
생성된 노드를 OPEN에 넣는다.
OPEN = {(0,1)(8,(O,O)), (2,2)(8,(2,1)), (4,2)(8,(3,2)), (2,3)(10,(3,3))}
CLOSED = {(0,0)(8,NULL), (1,0)(8,(0,0)), (2,0)(8,(1,0)), (2,1)(8,(2,0),
(3,1)(8,(2,1)), (4,1)(8,(3,1)), (3,2)(8, (3,1)), (3,3)(8,(3,2))}
9단계
OPEN에서 평가함수가 최소인 노드 (4,2)를 꺼내 확장하고 이를 CLOSED에 넣는다.
새롭게 생성된 노드 (4,3)의 평가함수를 계산한다.
생성된 노드를 OPEN에 넣는다.
OPEN = {(0,1)(8,(O,O)), (2,2)(8,(2,1)), (2,3)(10,(3,3)), (4,3)(8,(4,2))}
CLOSED = {(0,0)(8,NULL), (1,0)(8,(0,0)), (2,0)(8,(1,0)), (2,1)(8,(2,0),
(3,1)(8,(2,1)), (4,1)(8,(3,1)), (3,2)(8, (3,1)), (3,3)(8,(3,2)),
(4,2)(8,(3,2))}
10단계
OPEN에서 평가함수가 최소인 노드 (4,3)를 꺼내 확장하고 이를 CLOSED에 넣는다.
새롭게 생성된 노드 (4,3)의 평가함수를 계산한다.
생성된 노드를 OPEN에 넣는다.
OPEN = {(0,1)(8,(O,O)), (2,2)(8,(2,1)), (2,3)(10,(3,3)), (4,4)(8,(4,3))}
CLOSED = {(0,0)(8,NULL), (1,0)(8,(0,0)), (2,0)(8,(1,0)), (2,1)(8,(2,0),
(3,1)(8,(2,1)), (4,1)(8,(3,1)), (3,2)(8, (3,1)), (3,3)(8,(3,2)),
(4,2)(8,(3,2)), (4,3)(8,(4,2))}
11단계
OPEN에서 평가함수가 최소인 노드 (4,4)를 꺼내 확장하고 이를 CLOSED에 넣는다.
(4,4)가 목표노드이므로 그 후계노드로부터 포인터를 역으로 추적하여 풀이경로를 구성한다.
OPEN = {(0,1)(8,(O,O)), (2,2)(8,(2,1)), (2,3)(10,(3,3))}
CLOSED = {(0,0)(8,NULL), (1,0)(8,(0,0)), (2,0)(8,(1,0)), (2,1)(8,(2,0),
(3,1)(8,(2,1)), (4,1)(8,(3,1)), (3,2)(8, (3,1)), (3,3)(8,(3,2)),
(4,2)(8,(3,2)), (4,3)(8,(4,2)), (4,4)(8,(4,3))}
이상의 과정을 통해 탐색트리를 작성하면 아래 그림과 같다. 그림에서 원 내부의 좌표는 노드를 의미한다. 원의 우측 숫자는 해당 노드의 평가함수값이다. ①~⑪은 OPEN에서 꺼내어 목표노드인가를 검사하는 순서이다. 화살표 옆의 파란색 수는 즉, 시작노드에서 출발하여 해당 노드에 도달할 때까지의 경로비용이다. 탐색결과 최단길이 경로는 (0,0)→(1,0)→(2,0)→ (2,1)→(3,1)→(3,2)→(4,2)→(4,3)→(4,4)이다.
탐색결과를 최단길이 경로로 판단할 수 있는 이유는 다음과 같다. 언제나 을 보다 큰 값으로 예측하지 않는다면 A* 알고리즘은 최소 비용 경로를 반환하는 것을 보장한다(교재 p76). 그런데 상하좌우로만 이동할 수 있는 미로에서, 장애물을 고려하지 않는다면 두 노드 사이의 최단거리는 맨해튼 거리다. 그러나 미로에는 장애물이 있으므로 은 실제 최단거리보다 작거나 같게 된다. 따라서 탐색결과는 최단길이 경로가 되는 것이다.
.
(3)참고문헌
이광형, 이병래(2018), 인공지능, 한국방송통신대학교출판문화원.