作者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