关于寻径算法
问题获得了专业而深入的解答在上面的图片中，人只能移动到方格的上下左右四个位置，不能沿对角线移动。
人与箱子之间存在一些无规则的障碍（墙），
只求：人与箱子之间是否能联通。不必求出路径。
请问最快速的是什么算法？ 如果求路径，我知道有个A*算法。但我这里不求路径。我觉得这时A*就不快了。而且A*是求最短路径。我也不需要最短路径。 改动一下算法呗，不用判断是否还有更短路径了
应该和连连看或是迷宫用到的算法类似 根据楼主给出的图，我们假设障碍的数量远远小于空地的数量。
所以楼主的意图大概是不允许我们在空地上寻找路径，不然寻径时间或存储空间的开销可能大得无法承受。
比如10000*10000的地图，只有10000个格子是障碍，其余99990000个格子都是空地。
所以我们要尝试一下仅仅只在障碍上遍历，完全不考虑空地，看看能否解决问题。
按照这个思路，我们很容易想到：
如果起点或终点被障碍包围，则无路，否则有路。
如下图所示：
但下面的情况例外：
所以我们需要一个更严格的判断规则：
如果在障碍上存在一条八连通（即斜对角也算相连）的环路，这个环路对一个点的角位移为$2\pi$，对另一个点的角位移为$0$，则无路；否则有路。
根据这个判断规则，我们只要把所有的障碍遍历一遍即可。
边走边算角位移，逆时针转就用加的，顺时针转就用减的。
其他细节就不多说了，有什么问题或改进方案尽管提。
如果能避免实数运算，那就太棒了！ 最快的方法是岛屿寻径法(我自创的)
其实就是地图预编译法,方式很多,大致上就是把能连通的点标记为同一个编号,按这样的规则形成一个二维数组,就像倒墨水一样,墨水能渗透的区域都是连通的,让图上每个点都充满墨水,用不同颜色的墨水区分出不同的连通区域,最后就能形成不同的类似岛屿状的图,任意取出两点,判断它的的"岛屿"编号就知道是否在同一个连通区域里,而不需要做复杂的a*寻路了,这是最高效的方法 按我说的方法,无论图有多大,图里有多少个岛屿,形状多么的复杂,只要编译一次即可,对每个点标记它所在的岛屿编号,成为一张二位数组连通信息表,那么每次寻路判断任意两点是否连通,所需要的时间都是0
我以前曾经研究过,像星际争霸,帝国时代,这些即时战略游戏应该都会用到类似技术,通过预编译地图减少运算量,如果全部都用a*算是不现实的 如果没有学过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个障碍的信息存得下，那么只能采用障碍遍历法，即使要处理大量查询。 4楼的方法很有意思，不知道是否可以通过射线法来辅助一下。
只有障碍是封闭图形，并且起点或终点在封闭图形里面，才存在不可达的情况。
那么只要判断起点或终点是否在同一个封闭图形里。这样的话可以用射线法试试，判断交点的奇偶性，应该可以 如何知道射线会跟哪个障碍相交呢？
为了回答上面的问题，只好把所有的障碍都判断一遍了，时间复杂度仍然是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)
可见环绕障碍法在各方面性能都表现优异，是目前看来最好的方法，但实现难度是最大的。 KeyTo9_Fans一定是个写论文的好手，做图做表都弄得很漂亮呀。
可以预处理的话，应该先把所有不封闭的障碍都去掉（不过并不好弄），因为这些障碍都不影响最后处理的结果。比如LZ所给的图，其实跟没有障碍是一样的。
然后把剩下的障碍标上数字，这样用射线法处理时，如果某个点在封闭区域内，那么肯定会与该障碍有交点，所以应该不用遍历所有的障碍，只用判断与射线相交的障碍就行了。利用对障碍编号进行Xor的话复杂度应该不会超过n。
当然对于射线所碰到的障碍，我想能出现的情况有限，估计依靠前几个障碍的情况，就能直接判断其位置，构造状态机的话，效率还能再好一些！不过暂时不能达到KeyTo9_Fans同志的O(1)
页:
[1]
2