Re: [轉錄][３９] 嗯

[aknow (嘎嘎)]

※ 引述《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)
推 yellowfishie:我想說的無關A*的"好壞", 而是它的"概念"
推 yellowfishie:The objective of A*-search is not finding the
推 yellowfishie:"perfect" path, but the "better" path.
推 yellowfishie:亂試的應該比較像是 trial and error :)
推 yellowfishie:而且, A*並不是換個 container 而已, 若只換成
推 yellowfishie:priority queue, 還是會慢的跟 maze 一樣...
推 gwliao:A*-search所找到的解跟最佳解之間的差距必須
→ gwliao:在一個bound之內.
→ gwliao:這是A*的特性之一, 不能保證的話, 就不是A*
→ gwliao:degree很大的search tree, 用BFS會讓memory暴掉,
→ gwliao:所以A*才被發明出來.
推 gwliao:A*這種來至AI領域的東西, 其實都有很多嚴格的定義和
→ gwliao:特性的推導.