A*의 지연 삭제로 오래된 힙 항목이 쌓입니다. 재구성 시점과 메모리 상한을 어떻게 정하나요?

꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →

잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?

답변과 점검 포인트 펼치기답변 접기

구두 답변

정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.

현재 최선 g와 다른 힙 항목은 pop할 때 버릴 수 있지만 오래된 항목이 많으면 메모리와 정리 지연이 늘어납니다. 활성 후보 수 대비 총 힙 크기·무효 pop 비율·남은 예산으로 재구성을 판단합니다.

재구성은 현재 유효한 open 상태에서 후보를 다시 만들며 closed 재오픈과 탐색 세대를 보존해야 합니다. 무조건 일부 후보를 삭제하면 최단성·도달성을 잃습니다. 재구성의 O(n) 작업도 틱 예산 안에서 처리할지 작업을 중단할지 명시합니다.

이해가 드러나는 지점을 확인해 보세요.

현재 최선 g와 다른 힙 항목은 pop할 때 버릴 수 있지만 오래된 항목이 많으면 메모리와 정리 지연이 늘어납니다. 활성 후보 수 대비 총 힙 크기·무효 pop 비율·남은 예산으로 재구성을 판단합니다.
재구성의 O(n) 작업도 틱 예산 안에서 처리할지 작업을 중단할지 명시합니다.

놓치기 쉬운 조건과 오해를 짚어 보세요.

다음 핵심 구분을 반대로 설명하거나 성립 조건을 생략한다: 현재 최선 g와 다른 힙 항목은 pop할 때 버릴 수 있지만 오래된 항목이 많으면 메모리와 정리 지연이 늘어납니다.

하나 더 질문하며 이해의 범위를 넓혀 보세요.

득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.