일부 노드를 방문하는 그리드 맵에 대한 최단 경로 알고리즘

Question

그리드 맵이 있는데 두 노드 사이의 최단 경로를 찾아야하지만 그 경로는 에 일부 노드을 포함해야합니다.

모든 순열을 시도해 보았지만 맵 크기와 필수 노드 수는 가변적이므로 최적의 알고리즘을 사용하고 싶습니다.

맵이 비슷한 것 : map

-Dark brown square at Y18 is the start point 
-Light brown squares from B20 to S20 are the end point (can make just one end point if needed) 
-White squares are walls (you cannot go through them) 
-Blue squares means that the point in front of it is a must-pass (for example, the blue square at q5-q6 means must pass zone of p5-p6) 

내가 자바를 사용하기 위하여려고하고있다, 나는 예를 들어, S10은 S9과 연결되어있는 동안 그가 (그들 사이의 연결이 그래프를지도 할 것이다, o10 및 s11).

도움을 주셔서 감사 드리며 궁금한 점이 있으시면 언제든지 문의하십시오.

Answer 1

제 생각에 이것은 두 가지 문제가 있습니다. 출발 지점과 목적지 노드 및 필수 중간 노드가 있습니다. 최단 경로를 결정하려면 시작 노드와 모든 중간 노드, 모든 중간 노드 쌍 및 각 중간 노드에서 대상까지의 거리를 계산해야합니다. 음이 아닌 가중치 만 포함 된 경우 알고리즘을 Dijkstra으로 수행 할 수 있습니다.

일단 모든 거리가 계산되면, 모든 중간 노드가 사용되는 시작 노드에서 대상 노드로의 최적 값 Hamiltonian path을 계산해야합니다. 그러나이 문제는 NP-hard이므로 효율적 알고리즘을 사용하여 해결할 수는 없습니다. 모든 순열을 무차별 적으로 강제 할 수있다.

Answer 2

해밀턴 경로를 해결해야하므로 점차적으로 도움이되지 않지만 모든 노드 간의 거리를 계산하려면 조금 더 빠르게하려면 Floyd-Warshall을 사용할 수 있습니다.