网格中的最佳路径

Question

我有一个最佳路径问题需要解决。 给定一个由可行走的和不可行走的瓦片组成的nxn网格，我必须通过最短路径从起点A到达终点B。 关键是，一些可行走的瓦片包含着得分点。为了在达到目标时得到有效解决方案，我必须获得一定数量的得分点。 这些瓦片上有不同数量的得分点（或没有），我需要最短路径到达目标，并在路上收集至少M个得分点。

我尝试过使用A*算法找到两点之间的最短路径，并尝试对其进行自定义，使其停止条件不仅当它到达目标，还必须具备必要的得分点。但我因此阻塞了路径，所以它不能正常工作。

如果您有任何建议如何解决这个问题或者有其他更适合的算法，我会感激您的帮助。 谢谢。

- Adrian

---

你看过Dijkstra算法了吗？ - Caesar

我可以从同一个方块多次获得分数吗？换句话说，如果网格中有一个包含一些带有分数的方块的循环，那么有效路径是否可以包含这样的循环，在到达最终目的地之前获得所需数量的分数？ - Sergey Kalinichenko

"Caesar，'简单版'的Dijkstra算法（或Floyd-Warshall算法）不能解决这个问题，因为优化任务有第二个维度。" - Sergey Kalinichenko

@dasblinkenlight 不，这些点只能被选取一次。 - Adrian

是的，你可以重新访问方格，如果你已经收集到了必要的点数，并且最短路径需要通过一些已经访问过的方格，那么就需要穿过它们。 - Adrian

Answer 1

当你处于深度为X的层时，你可以向图中添加图层 -> 你已经收集了至少X个点。从上一层到当前瓦片的+N层（其中N是当前瓦片的点数）添加适当的边缘。

您的图是无限的，但是在遍历某条边缘时，您可以动态地将层数添加到顶点句柄中。由于它是无限的，因此您无法确定是否可以到达终点，但是您可以检查是否存在基本图上的路径以及是否至少有一个点。

您应该将终点放置在水平线>M上。

如果您需要一些澄清，请问=）

正如@Pyrce所说，如果您计划使用A *，您还应该提供一致的启发式http://en.wikipedia.org/wiki/Consistent_heuristic。

- kassak

---

虽然他的图表可能不是无限的，只是非常非常大，因为您只能以排列（M）的方式捕获M个点。您可能还想添加启发式需要更改A *的内容 - 即距离现在不再是2D。 - Pyrce

@Pyrce 一般来说，图是无限的，因为 M 是输入参数，就像起点和终点一样。对于A*情况，启发式算法一直都不是那么简单的任务=)但我认为正常的启发式算法(曼哈顿距离到终点)加上加权相加，如abs(cur_level - M)，可以做得很好 - kassak

是的，但M在算法开始时固定，并且不会改变。一个4点的M将提供24个可能的排列来解决问题，因此图形大小将为NxNx(M！) = 24N ^2；很大但比无限小得多。当然，有无限的可能选择N和M来开始解决问题。您建议的启发式方法是可接受的，但不是一致的，因为您可能会在到达所有M点之前就掉进解决方案点的陷阱中，而远离移动会使启发式方法非单调。请参见http://en.wikipedia.org/wiki/Consistent_heuristic。只是想让您将其添加到您的答案中。 - Pyrce

@Pyrce 是的，我知道启发式算法，但就像我之前说的，找到正确的方法很棘手。我会将你提供的链接添加到答案中。至于大小，我试图将搜索空间与搜索问题分开。这是算法的任务，不要走得太远 =) - kassak

Answer 2

如果你仍然卡在这个问题上，因为其他答案/评论只给出了部分答案 - 这里是解决问题的尝试。

您实际上可以使用A*算法并进行一些修改，以捕获（大多数）无序的M点路径。唯一需要改变的是启发式函数和终止条件。

首先，您需要更改启发式函数以考虑通过M点的路径。启发式函数必须是可行且连续的，因此它必须等于小于或等于真实路径成本的值，并且随着接近目标而仅能减少（必须是单调递增的）。

您现在采取的路径可以看作是您必须完成的M个子路径，每个子路径都像普通路径一样运作。因此，对于仅具有终止空间的单点图形，您可以使用像欧几里得距离之类的标准启发式函数。这是一种贪婪估计，表明直线路径是最佳的，而在理想情况下您不能更好地做到（它是可行的）。

对于多个路径，贪心方法同样表明，点之间没有阻挡的直线路径是您可以走的最快路径。它仍然是一个连续的启发式函数，因为您不能朝更远的方向跨越一步并获得更好的得分。难点在于选择哪个M点的顺序最快而没有阻碍，以保持一个可行的启发式函数。您可以通过广度优先搜索从当前格到每个M点，到每个剩余的M-1点，...到终止方块，在所有可行走的瓷砖上找到M个点的最佳选择。这个操作很昂贵，因为您需要对到达的每个格子都执行此操作 - 但是您可以使用动态规划或搜索缓存将所需的平摊计算降至每步O（M）。

现在，一旦您有了在没有障碍物的情况下最快的M点路径，您可以使用该路径中每个点与您当前位置之间的欧几里得距离作为启发式函数。这是一种贪心移动估计，因此它始终是可行的（您无法击败估计成本），并且它是连续的，因为您不能从下一个贪心最优点走开并减少成本，因为从当前瓷砖选择不同的贪婪点将不是可行的。

最后，您的终止条件需要更改为达到M个点，其中最后一个点是终止瓷砖。这模仿了步行M个图形而无需构造M个可能的图形来行走。提供的启发式函数将让A*算法发挥其魔力，而不改变基础算法，并且应该是在满足泛型网格上所需的启发式函数约束条件的情况下可以得到的最有效的方法。

- Pyrce

---

我已经自己解决了这个问题，但是你的答案是最接近我所做的。 - Adrian