4
23:14 지점에서 "확장 목록"으로 묶인 & 지점이 Dijkstra의 알고리즘과 매우 비슷하다고 느꼈을 때 http://youtu.be/gGQ-vAmdAOI?t=23m14s을 통해 작업하고있었습니다. 나중에 강의가 허용 가능한 휴리스틱으로 확장 될 때 A *를 얻습니다.그래프의 분기 및 바운드 (+ 확장 목록)와 Dijkstra의 알고리즘 간의 차이
그것은 Dijkstra의 알고리즘이 분기점 &의 매우 하위 클래스라고 생각하게했습니다. 그게 맞습니까?
검색 알고리즘을 살펴 봅니다 :
는 강의를 요약합니다. 특히, 간단한 분기에서부터 시작합니다.
대상 노드를 방문 (확장) 할 때까지 소스에서 가장 가까운 노드를 방문하고 후속 노드를 방문 할 노드의 우선 순위 큐에 추가합니다 최소 거리로 정렬). 아직 사이클을 감지하지 못하고 (예 : 노드를 두 번 이상 방문 함) 조합 적 폭발로 인해 다소 비효율적입니다.
단순한 확장은 알고리즘이 훨씬 더 잘 수행되도록합니다. 이미 방문한 노드를 기억합니다 (확장, 따라서 확장 목록). 어떤 노드도 두 번 방문하지 않고 알고리즘이 훨씬 더 잘 수행됩니다.
마지막 부분에서 A *를 얻기 위해 허용 가능한 휴리스틱이 혼합에 추가됩니다.
이 정보가 충분하고 강의에서 예제를 복사 할 필요가 없기를 바랍니다. 그렇지 않다면 알려주세요.
나는 최근에이 강의들을보고 똑같은 생각을했습니다. 이 질문에 대한 답을 찾았습니까? – trianta2
슬프게도, 아니, 나는하지 않았다. 하지만 나는 내가 옳았다는 것을 확신한다. 저는 더 이상 강의에 참여하지는 않지만 Dijkstra의 경우 노드가 이미 대기열에 들어간 노드를 완화 할 수 있다고 생각합니다. 분기와 바운드 방식은 노드에 대한 복제를 대기열에 넣는 것처럼 들릴 수 있습니다. 그것은 구현 세부 사항입니다. –
다른 하나가 완료되지 않은 동안 완료라고 하시겠습니까? –