推 H45:感謝提示 m(_ _)m 01/08 19:25
推 H45:老兄，我想最重要的是如何達到admissible，這才是A*的精神 01/18 00:36
→ H45:我已經重新設計各種heuristic，光為了達到admissible heuristi 01/18 00:37
→ H45:c就費了不少工夫，但是似乎沒有有效的方法來估計子彈的成本， 01/18 00:38
→ H45:尤其是永遠不能高估它的cost...更是個難題 01/18 00:39
※ 引述《H45 (!H45)》之銘言：
: 消泡泡：
: 原出處：http://www.cartoonnetwork.com.tw/jsp/game/miguzi/splashback.jsp
: 已下載的：http://ab5215.myweb.hinet.net/splashback.swf
: 以Java實作解法的：http://ab5215.myweb.hinet.net/Splashback_Java.zip
:
: 我使用A* algorithm去解決消泡泡問題，但是有些困惑
:
: 先介紹一下有關A* algorithm：
: A* algorithm的精神是算出每個節點至少需要的成本，然後循最小成本優先展開
: 所以A* algorithm是Best first search stratege，也是Branch and bound的特例
: 而每個節點需要的成本 = 已花費的成本 + 未來最近一次花費最小的成本
:
: 令成本為：需要使用的黏液球數量
:
: 重點來了，這個消泡泡遊戲至少需要的成本，可能是「負值」！！
: 當我們連續消掉三個黏液團，會增加一顆黏液球，消掉六個黏液團，會再增加一顆!!
: 也就是說，如果有辦法連續消掉六個黏液團，未來最近一次花費的成本會是 1-2=-1
: 這樣的話，我們根本沒有辦法確知Best first search stratege是否正在展開成本最小者
: 誰知道未來是不是會有成本更小的呢。
:
: 又若我們以「未來可能消滅所有的黏液團」來當做未來最近一次花費最小的成本
: 即，(-黏液團數量 / 3)，這樣可以確保算出來的成本必定是最小成本
: 問題是，如果以這樣的方法來套入Best first search，又變得算不出結果來了
: 因為當展開到第三層時，節點數量大幅增加，各節點的成本卻幾乎一樣低
: 而且Best first search stratege每次都要找到最小的成本O(n)
: 當節點增加到將近十萬筆時，每次尋找最小的成本O(n)所浪費的時間將十分可觀
: 所以很難找出結果。
:
: 文章開頭的java實作連結，小弟是先以後者方法解到30000個節點
: 若解不出來，再用前者方法解到60000個節點；
: 如果都解不出來，就從已計算的節點中，找到層數最大者
: 遞迴原函式做相同的運算，直到算至所有的黏液團都被消掉為止。
:
: 後來沙盤演練的經驗，以前者方法解出來的答案，再做一次重新排序
: 把所有的引爆點都放到最後去觸發，成本會更小。
:
: 請問有人有更佳的計算辦法嗎??
:
: ---
:
: 獻醜了
heuristic algroithm 求解的效率跟你heuristic function寫的好不好有關；
Heuristic function的求法 wikipedia[1] 上有簡單的說明
如果是我來解這問題的話，我會先把祺盤上目前的狀況來評分，再把這邊的分
數加上剩餘的子彈數來當總分。
手先是定義分數，一個泡泡有五個階段( 最小->快爆 )，分數就是倒過來看，
5 -> 1，所以說若是棋盤上只剩一個小泡泡未爆，那麼分數就是 5分，只剩一
個大泡泡未爆，那麼分數就是 1分；分數越小越好。
至於手邊的子彈數，一個算 -100 分，也就是說留著越多沒用越好。
接下來的問題就是，相臨的泡泡該要怎麼計分的問題；兩個相臨的大泡泡，是
該算 2分還是 1分呢？三個相臨的又該怎麼算？是 2分, 1 分, 還是 -99分？
把這 heuristic function 寫出來，問題差不多就解完了。
[1] http://en.wikipedia.org/wiki/Heuristic_(computer_science)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 24.5.191.38