关于寻径算法

ssikkiss

在上面的图片中，人只能移动到方格的上下左右四个位置，不能沿对角线移动。 人与箱子之间存在一些无规则的障碍（墙）， 只求：人与箱子之间是否能联通。不必求出路径。 请问最快速的是什么算法？

ssikkiss

如果求路径，我知道有个A*算法。但我这里不求路径。我觉得这时A*就不快了。而且A*是求最短路径。我也不需要最短路径。

kon3155

改动一下算法呗，不用判断是否还有更短路径了 应该和连连看或是迷宫用到的算法类似

KeyTo9_Fans

根据楼主给出的图，我们假设障碍的数量远远小于空地的数量。 所以楼主的意图大概是不允许我们在空地上寻找路径，不然寻径时间或存储空间的开销可能大得无法承受。 比如10000*10000的地图，只有10000个格子是障碍，其余99990000个格子都是空地。 所以我们要尝试一下仅仅只在障碍上遍历，完全不考虑空地，看看能否解决问题。 按照这个思路，我们很容易想到： 如果起点或终点被障碍包围，则无路，否则有路。 如下图所示： 但下面的情况例外： 所以我们需要一个更严格的判断规则： 如果在障碍上存在一条八连通（即斜对角也算相连）的环路，这个环路对一个点的角位移为$2\pi$，对另一个点的角位移为$0$，则无路；否则有路。 根据这个判断规则，我们只要把所有的障碍遍历一遍即可。 边走边算角位移，逆时针转就用加的，顺时针转就用减的。 其他细节就不多说了，有什么问题或改进方案尽管提。 如果能避免实数运算，那就太棒了！

arcol

最快的方法是岛屿寻径法(我自创的) 其实就是地图预编译法,方式很多,大致上就是把能连通的点标记为同一个编号,按这样的规则形成一个二维数组,就像倒墨水一样,墨水能渗透的区域都是连通的,让图上每个点都充满墨水,用不同颜色的墨水区分出不同的连通区域,最后就能形成不同的类似岛屿状的图,任意取出两点,判断它的的"岛屿"编号就知道是否在同一个连通区域里,而不需要做复杂的a*寻路了,这是最高效的方法

arcol

按我说的方法,无论图有多大,图里有多少个岛屿,形状多么的复杂,只要编译一次即可,对每个点标记它所在的岛屿编号,成为一张二位数组连通信息表,那么每次寻路判断任意两点是否连通,所需要的时间都是0 我以前曾经研究过,像星际争霸,帝国时代,这些即时战略游戏应该都会用到类似技术,通过预编译地图减少运算量,如果全部都用a*算是不现实的

KeyTo9_Fans

如果没有学过BFS算法或并查集，而是自己独立思考，想到了上述方法，确实很了不起。 不过上述算法是很基本的算法，我认为大家都已经掌握了，所以不屑于提它。 于是我绕开它不提，试图另寻僻径。 楼上说“无论图有多大”，这是不对的。 比如100万*100万的图，里面有100万个障碍，你是开不了这么大的二维数组的。 但4楼的方法仍然可行。 设地图为n*n，障碍数为m，两种方法的性能比较如下：

性能指标	预编译法	障碍遍历法
前期花费时间	O(n^2)	O(m)
前期花费空间	O(n^2)	O(m)
查询花费时间	O(1)	O(m)
查询花费空间	O(1)	O(m)
地图修改维护时间	O(n^2)	O(m)
地图修改维护空间	O(n^2)	O(m)

从上表可以看到，两种方法都有各自的优缺点。 所以哪种方法好，是要根据实际情况来决定的。 如果地图上几乎都是障碍，即m与n^2同阶，那么采用预编译法。 如果要处理大量的查询，即查询数量大于n^2/m，那么还是要采用预编译法。 如果m远小于n^2且查询数量小于n^2/m，那么采用障碍遍历法。 如果n太大以至于地图存不下，而m个障碍的信息存得下，那么只能采用障碍遍历法，即使要处理大量查询。

litaoye

4楼的方法很有意思，不知道是否可以通过射线法来辅助一下。 只有障碍是封闭图形，并且起点或终点在封闭图形里面，才存在不可达的情况。 那么只要判断起点或终点是否在同一个封闭图形里。这样的话可以用射线法试试，判断交点的奇偶性，应该可以

KeyTo9_Fans

如何知道射线会跟哪个障碍相交呢？ 为了回答上面的问题，只好把所有的障碍都判断一遍了，时间复杂度仍然是O(m)的。 但也许有改进的方法。 我们把障碍的坐标(x,y)按照y从小到大排序，y一样的话，x小的排前面。 例如： (4,2)<(5,2)<(12,2)<(5,3)<(12,3)<(4,4)<(12,4)<(4,5)<(12,5)<(13,5)<(12,6)<(11,7)…… 至于空地，完全不去管它。 如果要询问某个格子是不是空地，那么在障碍列表中采用二分查找的方法即可。时间复杂度为O(log(m))。 对于每个障碍，从旁边的空地出发，根据右手贴墙法则可以绕障碍一圈回到起点，走过的路标上同样的标记。 对于不同的环路，则标不同的标记。 如下图所示： 显然地，标记的数量不会超过4m，即标记数量与m同阶。 把所有的标记按y坐标排序，y一样的话，x小的排前面。 好了，现在对于每个询问(sx,sy)->(tx,ty)，首先判断它们是不是空地，不是的话询问无意义。 好了，现在每个询问(sx,sy)->(tx,ty)都是两个空地。 我们在标记列表中二分查找(sx,sy)和(tx,ty)，看看它们的标记是否相同。 当然，很多情况下在标记列表中是找不到(sx,sy)和(tx,ty)的，只能得到如下查找结果： (x1,y1)<(sx,sy)<(x2,y2)，(x3,y3)<(tx,ty)<(x4,y4)。 没关系，我们就取(x1,y1)或(x2,y2)的标记作为(sx,sy)所在的区域好了。 （大家想一想，如果(x1,y1)和(x2,y2)的标记不一样怎么办？） 同样地，取(x3,y3)或(x4,y4)的标记作为(tx,ty)所在的区域。 （同样地，标记不一样怎么办？） 标记相同则区域相同，回答“有路”。标记不同则区域不同，回答“无路”。 好了，现在要解决标记不一样的问题。 如下图所示： s和t两边的标记都不一样。 对于这种情况，标记不一样我们也要让它们一样。 要做到这一点，对标记使用并查集即可。（参考《算法导论》并查集那章） 要使得两个标记一样，把它们的父节点合并即可。 要判断两个不同的标记是否合并过，则判断它们的父节点是否一样即可。 好了，其它细节不多说了。有什么问题尽管问。 下面是三种方法的比较：

性能指标	预编译法	障碍遍历法	环绕障碍法
前期花费时间	O(n^2)	O(m)	O(m*log(m))
前期花费空间	O(n^2)	O(m)	O(m)
查询花费时间	O(1)	O(m)	O(log(m))
查询花费空间	O(1)	O(m)	O(1)
地图修改维护时间	O(n^2)	O(m)	O(log(m))
地图修改维护空间	O(n^2)	O(m)	O(m)

可见环绕障碍法在各方面性能都表现优异，是目前看来最好的方法，但实现难度是最大的。

litaoye

KeyTo9_Fans一定是个写论文的好手，做图做表都弄得很漂亮呀。 可以预处理的话，应该先把所有不封闭的障碍都去掉（不过并不好弄），因为这些障碍都不影响最后处理的结果。比如LZ所给的图，其实跟没有障碍是一样的。 然后把剩下的障碍标上数字，这样用射线法处理时，如果某个点在封闭区域内，那么肯定会与该障碍有交点，所以应该不用遍历所有的障碍，只用判断与射线相交的障碍就行了。利用对障碍编号进行Xor的话复杂度应该不会超过n。 当然对于射线所碰到的障碍，我想能出现的情况有限，估计依靠前几个障碍的情况，就能直接判断其位置，构造状态机的话，效率还能再好一些！不过暂时不能达到KeyTo9_Fans同志的O(1)