关于寻径算法

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)