irnd04   5년 전

힙에 인접한 노드를 넣고

힙에서 꺼내지않은상태에서 인접한 노드의 코스트가 변경이 될때 어떻게 처리를 해야하나요?

ex ) 

힙     :    B    C    D

cost  :  10   20   30

이라고 할때

현재노드는 E고 시작점으로 부터의 거리는 5다

E -> C로 가는 비용이 10이여서 총 15의 거리이므로 갱신이 필요한 상황입니다.

제 생각엔 두가지의 선택이 있는것 같습니다.

1. 이상태에서 힙에 있는것을 갱신을 하고 힙을 업데이트를 하느냐

2. 힙에다가 그냥 넣고 한번더 돌린다.

이것 보다 좋은 선택지가 있는지 궁금합니다. 

아무리 찾아봐도 없네요.. ^^!;

atomzeno   5년 전

"힙에서 꺼내지않은상태에서 인접한 노드의 코스트가 변경이 될때 어떻게 처리를 해야하나요?"

인접한 노드의 코스트가 왜 변하는지 모르겠...습니다만

djm03178   5년 전

1번으로 하는 것이 일반적으로는 아무래도 좀 더 효율적이긴 하고, 그보다 나은 방법은 특별히 없어 보입니다.

하지만 내장 라이브러리들이 대부분 힙에서의 update 기능을 지원하지 않기 때문에 보통은 그대로 힙에 하나 더 넣고 기존에 들어있던 건 무시하는 편이죠.

irnd04   5년 전

감사합니다.

힙에 하나 더 넣고

i f(distance[x] < cur.cost) continue

하는 방법이 제일 좋은것 같습니다.

댓글을 작성하려면 로그인해야 합니다.