指定距离/节点数的寻路算法

Question

我需要一个算法，可以给我一个从开始节点到结束节点的路径，但路径必须有一个确切的节点数，否则路径查找应该失败。

为了扩展，我有一个网格的瓷砖。移动只能到紧邻的上、下、左或右瓷砖（意思是，没有对角线移动）。对于路径中可以使用和不可以使用的平铺有许多规则，但大多数情况下可以归结为一个简单的bool来判断平铺是否可以使用（甚至可以在开始算法之前计算）。然而，给我带来麻烦的是，我有一个指定的路径必须有的距离，意思是，从一块瓷砖到邻近的瓷砖的每一次移动都是一个距离，整个路径应该有一个指定的距离，不多也不少。此外，一旦踩到了一个瓷砖（但在算法开始时所有瓷砖都可用），就不能再踩了，有点像玩老蛇游戏，你必须小心不要吃自己。

我看过Dijkstra/A*，也搜索过寻路算法，但据我所知，所有算法都集中在最短路径上，这对我没有多大好处。我不在乎它是哪条路，只要它遵循前面提到的规则就行了。

这里有一个例子，我说它必须是精确的距离，不能两次使用同一个瓷砖。

假设距离必须是7。现在让我们用O标记路径中可以使用的瓷砖，用和X标记不能使用的瓷砖，用S标记起点，用E标记目标。

X X X X X X X
X O O E S O O
X O O O O O O

如果没有距离限制，一个人可以离开，问题就解决了。如果有距离的限制，但没有“不能踩同一块瓷砖”的限制，一个人可以下一次，然后左，然后右，然后左，然后右，然后左，然后向上，到达目标。由于两者都有限制，一个人需要向右，向下，向左，向左，向左，向上，然后向右才能到达目标。然而，如果情况是这样，就没有有效的路径。

X X X X X X X
X O O E S O O
X X O O O X O

Answer 1

由于它是NP完全的，正如Haile所指出的，这里有一个启发式，以防你的问题足够小：

• 查找不包含S或E的半岛（即图中仅由一个节点连接到其余部分的部分），并将其移除。
• 查找从S到E的最短路径P。如果n小于len(P)，则没有解决方案。
• 现在，从S到E进行深度优先搜索，使用下面的启发式来选择要首先挖掘的节点。让A成为深度优先搜索中的当前平铺。在欧几里得几何学中，将A的位置投影到(SE)线上，并将此点称为A'。尝试保持len（当前路径）/n与len([sa'])/len([SE])的比值。或者，在路径P上“项目”A以获得A''，并使len（当前路径）/N与len([sa'])沿着P)/len(P).
保持接近。

我们不太了解您将要处理的确切情况，当然还有更多的启发式可以添加，以丢弃深度优先搜索树的部分。