algorithm - 访问某些节点的网格图的最短路径算法

Question

我有一张网格图，我需要找到两个节点之间的最短路径，但该路径必须包含一些节点。

我想过尝试所有排列，但 map 大小和必须节点的数量是可变的，所以我想使用最佳算法。

map 将类似于: 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)

我将使用 Java，我将使该映射成为具有它们之间连接的图形(例如 s10 与 s9、o10 和 s11 连接)。

非常感谢您的帮助，如果您有任何问题，请尽管提出。

Answer 1

据我了解，这是两个问题的结合；你有出发点、目的地节点和强制性中间节点。为了确定最短路径，您必须计算起始节点与所有中间节点之间的距离、所有中间节点对以及每个中间节点到目的地的距离。如果只涉及非负边权重，这可以通过 Dijkstra 算法完成。 .

一旦计算出所有距离，最佳的Hamiltonian path必须计算从起始节点到目标节点，其中使用所有中间节点。但是，由于这个问题是NP-hard ，它很可能无法使用有效的算法来解决；暴力破解所有排列可能是可行的。