6 asked

2

이미 방문한 상태라 closed가 true값이 되어 위에서 이미 continue 되는거라 생각되서,

openList에 들어갔다고 해서 반드시 방문을 한 상태는 아니고,
단지 '예약' 상태 정도로 보는 것이 맞습니다.
매 턴마다 '예약'된 애들 중 가장 우수한 애를 뽑아서 '방문'을 하는 것이죠.
일반적인 BFS와 다르게 간선에도 데이터(ex. 거리)가 등장할 경우
처음 '발견'한 경로보다 뒤늦게 '발견'한 경로가 더 좋은 경우도 종종 생기기 때문입니다.

사실 이 문제는 Dijikstra에서도 비슷한 상황이 발생합니다.
0번 정점에서 시작을 한 상황인데,
1) 2번과 1번 정점을 발견합니다.
2) 그러나 2번 정점이 가장 가까우니 먼저 방문을 하게 됩니다.
3) 2번 정점을 방문하면서 3번 정점을 발견합니다 (거리는 1+1000 = 1001)
4) 3번과 1번 정점을 발견했는데 이 중 더 가까운 1번 정점을 방문합니다.
5) 1번을 방문하면서 발견은 했지만, 아직 방문하지 않은 3번에 대한 더 좋은 경로를 알게 됩니다
(1+1000 보다는 10+10이 훨씬 더 가성비가 좋기 때문)
6) 3번을 최종적으로 방문하지만, 기록상 0->2->3이 아닌 0->1->3을 통해서 방문한 것으로 기록

다익스트라랑은 알고리즘이 조~금 다르지만
어쨌든 A*도 일종의 채점 시스템을 도입하는 것이기 때문에
드물지만 뒤늦게 발견한 경로가 알고보니 더 좋은 경우도 생깁니다.

1

강의의 미로만 놓고 보면, 생성된 알고리즘 특성상
같은 지점을 두 갈래의 길로 발견할 일이 없으니
사실 저 코드가 의미가 없긴 합니다.

0

잘 이해했습니다. 감사합니다

0

그럼 강의에서 적용한 미로같은 경우에선 교차로에서 저 코드가 적용되는건가요?