作者aknow (嘎嘎)
看板NTUGIEE_EDA
标题Re: [转录][39] 嗯
时间Mon Jan 12 00:06:47 2009
: 推 yellowfishie:我想说的无关A*的"好坏", 而是它的"概念" 01/11 15:56
: 推 yellowfishie:The objective of A*-search is not finding the 01/11 15:56
: 推 yellowfishie:"perfect" path, but the "better" path. 01/11 15:56
: 推 yellowfishie:乱试的应该比较像是 trial and error :) 01/11 15:58
: 推 yellowfishie:而且, A*并不是换个 container 而已, 若只换成 01/11 16:14
: 推 yellowfishie:priority queue, 还是会慢的跟 maze 一样... 01/11 16:14
A* 就是 optimal
连一个 bound 内的保证都不需要
做不到表示你的 cost estimation 无法保证 lower bound 的性质
另外 A* 不只是换 container 而已
我想我在前面的文章应该有说清楚
A* = best-first + bound (lower bound estimation)
container 影响的是 search 的 order
bound 做的是 "剪枝" (大陆用语) 会让你的 search tree 变小
container: stack queue priority queue
method: depth-first breadth-first best-first
w/ bound: branch & bound (通常这样写很蠢) A*
本来还写了一些比较跟正题有关的
不过还是算了
等我会做研究再说......
: 推 gwliao:A*-search所找到的解跟最佳解之间的差距必须 01/11 19:59
: → gwliao:在一个bound之内. 01/11 20:00
: → gwliao:这是A*的特性之一, 不能保证的话, 就不是A* 01/11 20:00
: → gwliao:degree很大的search tree, 用BFS会让memory暴掉, 01/11 20:03
: → gwliao:所以A*才被发明出来. 01/11 20:04
: 推 gwliao:A*这种来至AI领域的东西, 其实都有很多严格的定义和 01/11 20:09
: → gwliao:特性的推导. 01/11 20:10
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.48.60