[RMXP发布] 【算法】Dijkstra寻路算法在RM地图上的应用

遠航の猫咪

1楼

发表于 2014-12-20 17:36:52 | 显示全部楼层

理论上从起点和终点同时BFS（直到两者边界相交）会大大减少遍历的次数
就是把o(n^2)变成了o(2(n/2)^2)，也就是1/2n^2，相当于原来的2倍效率

如果找到“中点”，然后将寻路过程不断拆分为起点到中点、中点到终点这样两个过程（有点像分治法），时间复杂度就会变成O(nlogn)？发表于 2014-12-20 19:42

SailCat (小猫子·要开心一点) 共上站 24 次，发表过 11 篇文章上次在: [2006年01月28日11:41:18 星期六] 从 [162.105.120.91] 到本站一游。

回复支持反对

帐号		自动登录	找回密码
密码			注册会员