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