※ 引述《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個節點;
: 如果都解不出來,就從已計算的節點中,找到層數最大者
: 遞迴原函式做相同的運算,直到算至所有的黏液團都被消掉為止。
:
: 後來沙盤演練的經驗,以前者方法解出來的答案,再做一次重新排序
: 把所有的引爆點都放到最後去觸發,成本會更小。
:
: 請問有人有更佳的計算辦法嗎??
由於一直設計不出好的admissible heuristic function去估計成本
我只好大膽提出另一個假設:
存在一種演算法,能夠讓電腦自動找到永遠不會高估 成本(花費的子彈) 的算法
換言之,讓電腦自己去調整計算成本的方法
藉由電腦不斷地對自己的程式進行測試,分析關鍵的運算,並且找到需要修改的部分
自己修改自己本身函式後,再繼續對自己進行測試、分析、修改……
在某種threshold的控制下,電腦最終output新產生的admissible heuristic function
供使用者套回原A* algorithm以解決泡泡問題。
如此,便能確保A* algorithm永遠會算出最佳的路徑 (最佳的發射子彈順序)
heuristic function永遠不可能高估成本
而且它的估計品質,也已經由方才的演算法調整過
希望它能比永遠估算最低成本的函式還來得好一點......
好吧...這種神奇的演算法該如何設計?? 我想這可能需要一個好的函式模型???
也許這種想法天馬行空,而且我只預計讓它以Pentium4 2.0G花個24小時來跑
有可能實現嗎?
---
我想一個6×6的問題不難找到一個演算法
總是能在平均情況下以polynomial時間複雜度找到最佳解吧???
或許是我想得太美了!?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.184.38.148