我有一个最佳路径问题要解决。给定一个填充有可步行瓷砖和不可步行瓷砖的 nxn 网格，我必须通过最短路径从 A 点到达 B 点。诀窍是一些可步行的瓷砖包含点。当我达到目标时，要成为一个有效的解决方案，我必须有一定数量的积分。瓷砖上有可变数量的点（或没有），我需要最短的路径才能到达目标，但在途中也至少收集了 M 个点。
我尝试的是 A* 算法，它找到 2 个点之间的最短路径，并尝试对其进行自定义，使其不仅在达到目标时具有停止条件，而且还具有必要的点。它不像我做的那样工作，因为我挡住了路径。
如果您对如何解决此问题或其他更适合的算法有任何建议，我将不胜感激。谢谢。
当您处于深度层时，您可以将层添加到图表中X-> 您至少收集了X点。在图形上从上层添加适当的边，到当前图块的点数+N所在的层。N
您的图形是无限的，但是您可以在遍历某些边时动态地将层数添加到顶点句柄。由于它是无限的，您无法判断完成是否可达，但您可以检查基础图上的路径是否存在以及是否至少存在一个点。
您应该将完成放置在级别上>M。
如果您需要一些说明，请询问=）
编辑
正如@Pyrce 所说，如果您打算使用 A* http://en.wikipedia.org/wiki/Consistent_heuristic ，您还应该提供一致的启发式
如果您仍然遇到这个问题，因为其他答案/评论只能给您一个部分答案 - 这是问题空间的一个裂缝。
您实际上可以使用 A* 进行一些修改来捕获（大部分）无序的 M 点路径。您唯一需要更改的是启发式和终止标准。
首先，您需要更改启发式方法以考虑通过 M 点的路径。启发式必须是可接受且一致的，因此它必须等于小于或等于真实路径成本的值，并且它只能随着您接近目标而减少（必须是单调递增的）。
您可以将您现在采用的路径视为您必须完成的 M 个子路径，每个子路径都充当正常路径。因此，对于单点图（只有一个终止空间），您可以使用标准启发式方法，如欧几里得距离。这是一个贪婪的估计，表明直线路径是最佳的，并且在理想情况下您无法做得更好（这是可以接受的）。
对于不止一条路径，贪婪方法同样表示，点之间的畅通直线路径是您可以走的最快路径。它仍然是一个一致的启发式方法，因为你不能走得更远，仍然有更好的分数。困难的部分是选择 M 点的哪个排序是最快的，没有障碍，以保持可接受的启发式。您可以在图中找到 M 点的最佳选择，其中所有图块都可以通过宽度首先搜索从当前图块到每个 M 个点、到每个 M-1 个剩余点的欧几里得距离，...，到终止方。此操作的成本很高，因为您需要为到达的每个正方形执行此操作 - 但您可以使用动态编程或搜索缓存将所需的摊销计算降低到每步 O(M)。
现在，一旦您拥有 M 点路径，这将是最快的无障碍物，您可以使用该路径中每个点与您当前位置之间的欧几里得距离作为启发式方法。这是一个贪婪的运动估计，所以它总是可以接受的（你不能超过估计的成本）并且它是一致的，因为你不能离开下一个贪婪的最佳点并降低你的成本，因为从当前图块中选择一个不同的贪婪点将不予受理。
最后，您的终止标准需要更改为达到 M 个点，其中最后一个点是终止图块。这模仿了行走的 M 个图，而无需构造 M！可能的图表走。所提供的启发式将让 A* 在不改变底层算法的情况下发挥它的魔力，并且应该尽可能有效，同时保持对通用网格的启发式所需的约束。