一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1080|回复: 6
收起左侧

[算法题] 关于A*算法和dijskra算法

[复制链接] |试试Instant~ |关注本帖
anikin0617 发表于 2014-3-28 06:17:47 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
关于dijskra算法和A*算法,小弟有一个疑问,希望各位大牛不惜赐教。
我知道A*算法效率要更高,可是不太明白二者在应用上有什么区别,就是什么场合应该用A*,什么场合应该用dijskra? 对于带权图来说,怎么确定H(n)比较好呢?是不是带权图用dijskra更方便呢?还有就是不知道哪位大神有A*算法的实际应用讲解和Java实现啊,小弟**一枚,这两天看图这块有点晕。
readman 发表于 2014-3-28 09:26:19 | 显示全部楼层
不是有公开课 算法II 是普林斯顿的 刚开, 你快去跟
回复 支持 反对

使用道具 举报

chopper 发表于 2014-3-28 09:45:25 | 显示全部楼层
dijskra算法和A*算法本身感觉没直接的可比性吧
A*因为有估价,所以更经常被用于可行解,比如8数码
h(n)记得没错,应该是中间结点到终点的估价吧,这个只能靠经验,一般设计时复杂度不要过高
dij也有堆的实现方法,复实度O(nlgn),类似于A*的h(n)取0
回复 支持 反对

使用道具 举报

狂暴CNM地 发表于 2014-3-28 10:17:24 | 显示全部楼层
如果你只是为了以后面试的话感觉A*可以不用搞太明白。。 h的选择是一个很靠经验的问题.. 毕竟任何小于实际值的估计都能得出正确答案
A*利用heuristic避免了对一些明显差的空间的搜索 其实不仅是最短路径上 还有很多问题上A*都可以被运用
回复 支持 反对

使用道具 举报

 楼主| anikin0617 发表于 2014-3-28 10:40:11 | 显示全部楼层
回复 支持 反对

使用道具 举报

readman 发表于 2014-3-28 11:00:55 | 显示全部楼层
chopper 发表于 2014-3-28 09:45
dijskra算法和A*算法本身感觉没直接的可比性吧
A*因为有估价,所以更经常被用于可行解,比如8数码
h(n)记 ...

d算法除了堆 还有实现方法?
回复 支持 反对

使用道具 举报

chopper 发表于 2014-3-28 11:17:39 | 显示全部楼层
readman 发表于 2014-3-28 11:00
d算法除了堆 还有实现方法?

有啊,只是实现上,而非算法上。
直接用double loop,O(n^2)。因为用堆的话,“每个点扩展的第一次必定最优”可能不是那么好理解,所以如果时间要求不高,就直接for for了。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 11:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表