问用X步找到一条从A点到B点的路径。(A* ish)

EN

我喜欢这个问题--它很有趣。

我不确定我该如何编码，但这些只是我脑海中的想法。

基本上，您在这里处理的是Manhattan distance，因为您没有使用对角线。因此，您需要知道可能的最短路径并从中派生。如果你的具体成本小于你的曼哈顿距离，那么这条路径是不可能的。如果相等，则理想路径是您可能的最短路径。

一旦你超越了这一点，事情就变得有点棘手，因为你有多种解决方案来解决你的问题。你也许可以用暴力破解一个答案，但我不知道是否有一种非天真的方法。(请注意，这些只是我脑海中的想法，所以……)

还要注意，对于某些情况，没有解决方案，因为您使用的是曼哈顿距离！例如，如果您有一个6x6栅格，起点在一个角，终点在另一个角，您可以在10个步骤中结束于终点，但不是11步(因为您必须返回到自己)。这是有规则的，我确定，但我必须推导出它。(__编辑：我意识到了这一点--这本身并不是一条规则，但你的具体成本不能落在最短路径距离和第二短路径距离之间。我认为，在曼哈顿网格中，第二短路径应该是n+2。)

所以基本上…我认为写这样的东西是可能的，但我不认为你可以在不检查很多可能性的情况下很容易地计算它。你可以通过规则来优化特定的情况，但是一旦你这样做了，我认为你就卡住了。

不过，还是试一试吧。这听起来很有趣！

第二次编辑：i just realized....your路径成本将始终增加两个(同样，由于曼哈顿距离)。这意味着，只要您知道最短距离，您就可以进一步优化；您的具体成本必须是2的倍数，再加上您的最短距离。在算法方面，你的具体成本= 2n +最短距离。

不过，在这一点之后，你将不得不暴力破解它。

希望这能有所帮助。

第三次编辑(希望是最后一次)：我在这里可能有点书呆子气(我可能正在弄清楚别人在我之前已经弄明白了什么)，但事情是这样的。如果你知道你的具体成本，你知道你的最短路径距离，你实际上可以取两者之间的差值并除以2来计算出在你的路径中需要多少循环。循环可以“堆叠”(我的意思是，您可以开始一个循环，并将其继续一段距离；这是“翻倍”)，因此您可以通过只检查具有特定数量的循环的路径来进一步优化。但是，到目前为止，您已经找到了通往末端节点的可能路径(假设障碍物不会阻塞您找到的所有可能路径)。因此，只有为了避免任何障碍，暴力才是必要的。我希望这是有意义的。

A*在设计上是无法做到这一点的。我会使用Dijkstra的算法，并通过所有可能的路径(从最短的路径开始)，直到您找到符合您的标准的路径。我真的想不出更简单的方法，因为可以有任意数量的路径满足该条件(包括0)。

首先，你需要明白这不是一个微不足道的问题，因此你不会在这里找到完美的答案，但你会找到一些好的想法。

这个问题固有的第一件事是，由于你不能通过对角线移动，一些成本价值将不可能实现。我假设网格有无法穿越的障碍块，如果不是这样，A*不是一个好的起点。

你的问题需要更多的澄清，但我将提供我发现的两种可能性的答案：

没有重复出现的点的路径

修改A*算法以保持运行，直到找到成本直接等于或高于所需成本的路径。只是使用它作为路径，因为没有其他方法来实现另一条路径。

具有重复出现的点的路径

用基本的A*找到最短路径，然后如果它小于期望的成本，则通过来回移动(通过往回移动将成本增加+2 )或通过将简单的步骤转换为循环(每次循环将成本增加+2 )来增加成本。