作者aknow (嘎嘎)
看板NTUGIEE_EDA
标题Re: [转录][３９] 嗯
时间Sun Jan 11 15:14:26 2009
※ 引述《yellowfishie (喵喵喵喵~~~)》之铭言：
: : 作者: ric2k1 (Ric) 看板: NTUGIEE_ric
: : 时间: Sat Oct 18 00:00:35 2008
: : 我知道你们之中一定有人做研究做得很无力, 也许会怀疑自己的人生要何去何从?
: : 你们不用说, 我大概也感受得到, 而且, 我常常在想, 要怎麽让大家过得更开心,
: : 对未来更有热情呢?
: 这个分享一下最近的想法，
: 我觉得研究热情需要的是 BFS 和 DFS,
: 如果 BFS 广度了解功夫作的不够，一直 DFS 深入研究後就会迷罔，不知为何而战?
: 但如果持续不断 BFS 但没有深入 DFS，就会心定不下来，没有明确目标而容易一事无成。
: 在 routing 的术语中，BFS = maze routing，DFS = line-search routing，
: 而我觉得不错的折衷方法是 A*-search (在 DFS 同时并作小部份的 BFS)，
: 它对找寻目标通常会有不错的效果。
: 大家可以想想参考一下 :)
我其实很讨厌大家一直炒作 A*
好像 A* 是什麽神呼奇技似的
大概八年前是我第一次学到 A*
然後这两年 A* 开始热烈的出现在 EDA 领域中
=> 很弱
以我们熟知的 DFS, Breadth-FS, Best-FS
实做方式只是换个 container 而已
depth-first (stack)
breadth-first (queue)
best-first (priority queue)
如果加上 bound (real cost + cost estimation) 的概念
depth-first + bound = 通常 B&B 的实做方式
best-first + bound = A*
不过严格来说 A* 也只是 B&B 的一个特例
然後如果我们仔细看
1977 hadlock's 其实就是 A*
在 maze 上的 A*
所以什麽是用 A* 做研究呢
大概像这样
用这个方法, 大概三个月就可以搞定
另一个方法, 估计要一个月
=> 傻子才选三个月
然後用一个月的方法做了一段时间後
吃屎, 卡住了, 现在大概还要五个月才弄得好
=> 赶快换回去要三个月的那个方法试试看
...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 59.115.163.231
※ 编辑: aknow 来自: 59.115.163.231 (01/11 15:17)
1F：推 yellowfishie:我想说的无关A*的"好坏", 而是它的"概念" 01/11 15:56
2F：推 yellowfishie:The objective of A*-search is not finding the 01/11 15:56
3F：推 yellowfishie:"perfect" path, but the "better" path. 01/11 15:56
4F：推 yellowfishie:乱试的应该比较像是 trial and error :) 01/11 15:58
5F：推 yellowfishie:而且, A*并不是换个 container 而已, 若只换成 01/11 16:14
6F：推 yellowfishie:priority queue, 还是会慢的跟 maze 一样... 01/11 16:14
7F：推 gwliao:A*-search所找到的解跟最佳解之间的差距必须 01/11 19:59
8F：→ gwliao:在一个bound之内. 01/11 20:00
9F：→ gwliao:这是A*的特性之一, 不能保证的话, 就不是A* 01/11 20:00
10F：→ gwliao:degree很大的search tree, 用BFS会让memory暴掉, 01/11 20:03
11F：→ gwliao:所以A*才被发明出来. 01/11 20:04
12F：推 gwliao:A*这种来至AI领域的东西, 其实都有很多严格的定义和 01/11 20:09
13F：→ gwliao:特性的推导. 01/11 20:10