关于寻径算法

KeyTo9_Fans

没写过论文，那张表也不知道是谁帮我画的，比原来好看多了。

9#的做法有个地方需要修正一下：

在查询的时候才合并标记是来不及的，如下图所示：



即使合并了，s和t的颜色还是不一样，于是错误地回答“无路”了。

所以合并标记的工作必须在前期完成：



这样查询的时候就保证不会有某个点两边的标记不一样的情况了。

于是前期工作包括：

把m个障碍排序、环绕障碍并标记、把标记排序、合并标记。

这些操作的时间复杂度均为O(m*log(m))，所以前期花费仍然是O(m*log(m))的。

另外，想到一个比较好玩的东西：

1个障碍似乎可以写成4个箭头。

多个障碍可以表示成多箭头相加。

当正反向箭头重合的时候，两个箭头就互相抵消了。

如下图所示：



而加法满足交换律，所以前期就用不着把障碍排序了，直接把箭头相加就可以了。

计算结果就是我想要的环路，从而省去了把m个障碍排序的工作。

但箭头还是要排序的，所以前期工作的时间复杂度并没有变化。

想到这里，发现4楼的障碍遍历法我忽略了一道重要的工序：

必须先把障碍排序！

这样才可以从一个障碍出发然后往相邻的障碍走。

不然的话寸步难行。

例如：我站在障碍(5,8)，怎么知道(4,7)、(4,8)、(4,9)等地是不是障碍？

不排序的话，我得在整个障碍列表中检查一遍有没有(4,7)、(4,8)、(4,9)这些障碍。

排序了就可以二分查找了。

所以性能指标需要修正。

现修正如下：

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

因为我一直以来都只用预编译法，后面的方法是看了此贴之后临时想出来的，还没有实现过。

所以难免会有疏漏之处。请大家原谅。

如果还有疏忽之处，请指正。

谢谢各位的热心帮助。

###############################

这是我的第100张贴子，做个记号，留作纪念。

wayne

呵呵，那个Smiley很吸引眼球~~

ssikkiss

谢谢以上各位帮忙！因为我的地图比较小，障碍较多，而且是实时变化的，我还是选了A*。

Dolphin_001

4楼的方法适合动态的障碍，而5楼的方法，对于静态的障碍，只需要建立一个2维数组，初始化一次就行了。都非常好

yschenwei

呵呵，不懂，顶下。

〇〇

很好的题目