网格中的最佳路径

Question

我有一个最好的路径问题需要解决.给定一个nxn网格,其中填充了可步行的瓷砖和不可步行的瓷砖,我必须从A点到达最短路径的B点.诀窍是一些可行走的瓷砖包含点.当我达到目标时成为有效的解决方案我必须有一定数量的积分.瓷砖上有不同数量的点(或没有),我需要最短的路径才能达到目标,但在途中也至少聚集了M个点.

我所尝试的是A*算法,它找到了2个点之间的最短路径,并尝试将其定制为具有停止条件,不仅仅是当它到达目标而且还具有必要的点.它不像我做的那样工作,因为我阻挡了路径.

如果您有任何建议如何处理此问题或其他更适合的算法,我将不胜感激.谢谢.

Answer 1

如果您仍然陷入这个问题，因为其他答案/评论只给您部分答案 - 这是问题空间的一个裂缝。

实际上，您可以使用 A* 进行一些修改来捕获（大部分）无序的 M 点路径。您唯一需要更改的是启发式和终止标准。

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

您可以将您现在采取的路径视为必须完成的 M 条子路径，其中每条都充当正常路径。因此，对于单点图（仅具有终止空间），您可以使用标准启发式，例如欧几里德距离。这是一个贪婪的估计，表明直线路径是最佳的，并且在理想情况下你无法做得更好（这是可以接受的）。

对于不止一条路径，贪婪方法同样表示点之间畅通无阻的直线路径是您可以走的最快路径。这仍然是一个一致的启发式方法，因为你不可能走得更远，但仍然可以获得更好的分数。困难的部分是选择 M 点的排序是最快且没有障碍的，以保持可接受的启发式。您可以通过广度优先搜索从当前图块到每个 M 点、到每个 M-1 剩余点、...、到的欧几里得距离，找到图中所有图块均可步行的 M 点的最佳选择。终止方块。此操作的成本很高，因为您需要对到达的每个方格执行此操作 - 但您可以使用动态编程或搜索缓存将每步所需的摊销计算降低到 O(M)。

现在，一旦您有了 M 条没有障碍物最快的点路径，您就可以使用该路径中每个点与您当前位置之间的欧几里得距离作为启发式。这是一个贪婪的运动估计，所以它总是可接受的（你无法击败估计的成本）并且它是一致的，因为你不能离开下一个贪婪的最佳点并减少你的成本，因为从当前的图块中选择不同的贪婪点不会被受理。

最后，您的终止标准需要更改为达到 M 点，其中最后一个点是终止图块。这模仿了行走 M 图，而不需要构造 M！可能的行走图。所提供的启发式方法将让 A* 在不改变底层算法的情况下发挥其魔力，并且应该尽可能有效，同时保持通用网格上的启发式方法所需的约束。