Dijkstra 알고리즘을 사용하여 최단 도로를 찾는 방법

Question

시뮬레이션을 코딩해야하며 위치에서 다른 도로까지 최단 도로를 찾는 방법이 필요합니다. 이 메서드는 시작 위치와 최종 위치 만 가져 와서 위치 사이의 가장 짧은 길을 나타내는 위치 목록을 반환합니다. 이 같은 뭔가 :

public List<Tuple<int, int> ShortestRoad(Tuple<int,int> start, Tuple<int,int> end, int[,] park) 
{//Code} 

나는이 방법이 다 익스트라 알고리즘 구현을 할 수 있습니까?

Answer 1

더 빠르게 만들 수있는이라는 인공 지능을 가진 너비 우선 검색 알고리즘 인 A* search algorithm을 찾아야합니다. 는 A * 알고리즘은 다 익스트라의 알고리즘과 같은 폭 첫 번째 검색는하지만 (힌트, 당신이 (가) 말, 말할 수 추론, 또는 가장 짧은 경로가 무엇인지에 대한 추측을 사용하는 것 기본적으로

* 알고리즘을 사용하여 노드를 관찰하는 것이 좋습니다). 추론을 사용하면 Dijkstra 's Algorithm보다 A * 알고리즘을 훨씬 빠르게 만들 수 있습니다. 왜냐하면 종종 Dijkstra 's Algorithm만큼 많은 노드를 보지 않기 때문입니다.

그러나, 조심하는 한 것은 당신의 휴리스틱 기능 (두 노드 사이의 비용/거리의 추측) 지정된 노드 사이의 실제 비용보다 작을 수 없으며해야한다는 것입니다. 경험적 함수가 더 작은 결과를 산출하는 경우 A * 알고리즘이 반드시 가장/최단/최소 비용 경로를 찾지는 않습니다.

멋진 애니메이션 (특히 A *와 Dijkstra의 알고리즘 사이의 차이점)을 원한다면 Wikipedia에서 양쪽 모두를 검색하십시오. 여기에는 각각의 알고리즘에 대한 애니메이션이 있고 둘 사이의 동일한 환경에서 수행됩니다 애니메이션. 그 (것)들에게서, A * 산법이 더 낫다는 것을 말하는 것은 쉽다. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm이

Answer 2

는 다 익스트라의 최단 경로 알고리즘을 살펴보십시오. 어떤 도로 데이터가 있습니까? 너 뭐 해봤 니? 암호? a * 알고리즘을 살펴 보았습니까?