지도에서 최단 경로 찾기에 대한 경험적 배경

Question

지도에서 두 스테이션 간의 최단 경로를 찾기 위해 Dijkstra algorithm을 사용했습니다. 한 스테이션에서 다른 스테이션으로가는 비용은 모든 링크에서 동일합니다.

그러나 문제는 Dijkstra이 소스에서 모든 스테이션까지 최소 비용 경로를 찾으려고한다는 것입니다. 목적지까지의 최소 비용 경로가 발견되면 검색을 중지하고 싶습니다.

그래서 저는 A* algorithm을 사용하기로 결정했습니다. 그러나 나는이 경우에 좋은 발견 적 사고를 생각할 수 없다. 휴리스틱으로 무엇을 사용할 수 있습니까?

Answer 1

만

검색 대상 에 최소 비용 경로 일단 중지하려면이

발견 된, 다 익스트라의 알고리즘은 이미 효율적으로 그렇게 할 수 있습니다. 대상 노드의 상태가 "회색"에서 "최종"으로 변경되면 알고리즘을 반환 할 수 있습니다. u는 목표를 = 경우에 우리가 정점 소스 와 대상 사이의 최단 경로에만 관심이 있다면 wikipedia

를 인용, 우리는 라인 (13)에서 검색을 종료 할 수 있습니다.

1 function Dijkstra(Graph, source): 
2  dist[source] := 0      // Distance from source to source 
3  for each vertex v in Graph:   // Initializations 
4   if v ≠ source 
5    dist[v] := infinity   // Unknown distance function from source to v 
6    previous[v] := undefined  // Previous node in optimal path from source 
7   end if 
8   add v to Q       // All nodes initially in Q 
9  end for 
10  
11  while Q is not empty:     // The main loop 
12   u := vertex in Q with min dist[u] // Source node in first case 
13   remove u from Q 
14   
15   for each neighbor v of u:   // where v has not yet been removed from Q. 
16    alt := dist[u] + length(u, v) 
17    if alt < dist[v]:    // A shorter path to v has been found 
18     dist[v] := alt 
19     previous[v] := u 
20    end if 
21   end for 
22  end while 
23  return dist[], previous[] 
24 end function 

A * 다른 측면을 해결, 당신은 당신이 대상 노드에 얼마나 가까운 의미있는 발견 적 추정이있는 경우에만 유용합니다. 다른 하나 개의 역가는 비용 즉 모든 링크

에서 동일

경우에도

. 경로 길이가 출발지에서 목적지까지의 링크 수이면 최단 경로는 depth first search으로 줄어 듭니다. DFS 알고리즘을 사용하는 것이 더 효율적일 수 있습니다.

---

추가 참고 : 노드 라인 12의 우선 순위 큐의 상단 요소 u로부터 추출 익스트라 알고리즘

는 그 거리 라벨이 고정되고, 이것은 더 작은 거리를 찾는 것이 불가능 현재 u에 표시된 라벨보다 그래서 u를 줄 13에서 삭제할 수 있습니다. 수학적 유도와 유사한 기술을 통해이를 증명할 수 있습니다. 다시 말해 u이 Q에서 제거 된 경우 Dijkstra가 더 짧은 경로를 찾을 수 없습니다.