A* 탐색에서 같은 셀에 더 저렴하게 도착하는 경로를 뒤늦게 찾았습니다. 후보 큐와 경로 복원 정보를 어떻게 바꿔야 하나요?

A*에서 open set은 발견했지만 아직 확장하지 않은 후보이고, closed set은 해당 시점에 확장을 마친 노드의 표시입니다. 같은 셀에 비용 10으로 도착한 뒤 비용 7 경로를 발견했다면 현재 최선 비용 g=7과 부모 포인터를 함께 갱신하고, 우선순위 큐에도 새 후보를 반영해야 합니다. 처음 발견했다는 이유로 비용을 고정하면 경로 복원은 비싸고 잘못된 경로를 반환할 수 있습니다. 큐 우선순위는 g만이 아니라 g+h인 f를 사용하되, 비용 갱신 비교는 출발점부터의 g끼리 해야 합니다.

후보 큐의 갱신

구현은 두 가지가 일반적입니다. 힙이 decrease-key를 지원하면 기존 항목의 우선순위를 낮추고, 그렇지 않으면 비용 10짜리 오래된 항목을 남긴 채 비용 7짜리 새 항목을 추가할 수 있습니다. 후자의 지연 삭제(lazy deletion) 방식에서는 힙에서 항목을 꺼낼 때 항목에 저장된 비용이 현재 셀의 최선 비용과 다르면 버립니다. 같은 f라도 다른 g나 탐색 세대일 수 있으므로 셀 ID만 비교하지 않고 비용·세대까지 확인해야 합니다. 이 검사를 생략하면 오래된 항목이 이웃을 다시 확장해 처리량과 부모 상태를 흔듭니다. 일관성 있는 휴리스틱과 비음수 간선 비용이라면 노드를 닫은 뒤 최적 비용이 더 낮아지지 않으므로 재오픈이 필요 없습니다. 그러나 휴리스틱이 일관되지 않거나 구현이 특정 조건을 보장하지 않는다면 closed에 있던 노드에서 더 낮은 g를 발견했을 때 closed 표시를 풀고 다시 open에 넣어야 최적성을 유지할 수 있습니다. 맵이 동적으로 바뀌면 단순 재오픈과 별개로 비용 상태 자체가 새 맵에 대한 것인지 버전으로 확인해야 합니다.

경로 복원과 수명

비용을 갱신할 때 부모도 새 경로의 직전 셀로 동시에 바꿉니다. 목표를 꺼낸 순간 부모를 따라가면 현재 최선 경로가 복원돼야 하며, 부모 포인터와 비용을 따로 갱신하면 중간에 섞인 경로가 나옵니다. 여러 탐색이 같은 배열을 재사용한다면 방문 여부를 매번 지우거나 세대 번호를 저장해 이전 탐색과 분리해야 합니다. 비동기 탐색 결과의 부모가 임시 버퍼나 이미 해제된 맵 객체를 가리키지 않도록 결과를 값으로 소유하거나 참조 수명을 보장하겠습니다. 검증은 비싼 직선 경로가 먼저 발견되고 싼 우회 경로가 나중에 발견되는 맵, 같은 셀을 네 방향에서 만나는 맵, 휴리스틱 재오픈이 필요한 맵을 비교합니다. 기준 구현과 최종 비용·도달성·경로 복원을 맞추고, 오래된 큐 항목 수와 최대 open 크기도 측정하겠습니다.

핵심은 open과 closed를 자료구조 이름으로 외우는 것이 아니라, 비용·부모·확장 완료 상태가 하나의 탐색 상태 불변식(search-state invariant)을 지키게 하는 것입니다. f가 같은 후보의 우선순위를 임의로 바꾸는 것은 최단 비용 자체를 바꾸지 않을 수 있지만, 종료 시점과 경로 모양·캐시 효율에는 영향을 줍니다. 힙 항목에 nodeId, g, f, 탐색 세대를 함께 저장하고 팝 시점에 현재 기록과 일치하는지 검사하겠습니다. 부동소수점 비용을 무작정 epsilon으로 비교하지 말고 정수 단위 비용이나 고정된 비교 정책을 사용해야 오래된 항목과 새 항목을 혼동하지 않습니다. 경로 복원은 부모를 따라가는 단계처럼 보여도 부모 사이클과 복원 길이 상한을 방어해야 합니다. 비용이 낮아질 때 부모를 바꾼 뒤 이웃 갱신이 누락되면 힙에 새 비용이 있어도 후속 노드가 갱신되지 않습니다.

비용·부모·open 삽입을 하나의 논리적 갱신으로 묶고, 탐색 취소 시 결과를 외부에 공개하지 않는 계약까지 포함하겠습니다.