나는 이 적어도 인 경로를 찾기 위해 길 찾기를 수행해야하는 프로젝트에서 작업 중입니다. 나는 그것이 가능한 가장 짧은 루트인지 정말로 신경 쓰지 않는다. 지금까지는 A *가 문제가되지 않았고 솔직히 Prim의 알고리즘을 이해하지 못합니다.가중 경로로 길 찾기
경로를 찾는 데 필요한 종류의지도를 설명하겠습니다. 다음은 예시지도입니다.
+------|-*----
+------|----|-
+--|--------|-
[email protected]|----------
"*"은 시작 위치이고 "@"는 대상입니다. 한 줄의 "+"기호는 a) 한 단계와 동일한 비용을 지불하고 b) 전체 경로의 비용을 반으로 줄이는 직접 경로를 나타냅니다.
이것은 시작 위치에서부터 목적지까지 "+"경로를 통해 10 단계가 있다는 것을 의미하며, 비용은 5가됩니다. 가장 왼쪽의 "|" route "("| "는"- "보다 비용이 적지 만"+ "보다 나쁨)입니다. 비용은 15로 끝납니다. 비용이 5 인 경로는 사용하는 경로입니다.
이제 C#에서 구현하는 데 문제가 있습니다. 나는 현재 방법이 막혔거나 단계의 비용과 새로운 위치로 이동하고 리턴하는 "단계"기능을 가지고있다. 이것은 잘 작동하지만, 현재는 "|" "+"앞에 하나를 발견하면 (즉, 더 빠른 경로를 찾지 못했기 때문에 전체 여행 비용이 훨씬 더 높습니다.)
저는 각 위치를 "방문한"것으로 표시하려고했지만, 가장 저렴한 경로가 다시 루프백 될 가능성이 완전히 있습니다. 또한 각기 고유 한 여러 경로가 있으며 각 경로는 다른 경로 세그먼트 (이전 실행에서 이미 방문했을 수 있음)를 사용할 수 있습니다. 물론 가장 저렴한 경로를 찾으려면 각 경로를 횡단해야하지만 동일한 경로를 반복해서 검색하지 않고이를 수행하는 방법을 알아낼 수는 없습니다.
간단하게 만들면 대상으로 이동할 때만 이동을 제한 할 수 있습니다 (예 : 이동 후 다시 올라갈 수 없음).
누구나 통찰력을 제공 할 수 있다면 좋을 것입니다.
숙제 냄새? –
왜 A *가 문제가되지 않습니까? –
왜 A *가 문제가되지 않습니까? –