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