作者H45 (!H45)
看板CSSE
標題[請益] 解消泡泡遊戲 by A* algorithm (效果不佳?)
時間Sun Jan 8 17:44:41 2006
消泡泡:
原出處:
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個節點;
如果都解不出來,就從已計算的節點中,找到層數最大者
遞迴原函式做相同的運算,直到算至所有的黏液團都被消掉為止。
後來沙盤演練的經驗,以前者方法解出來的答案,再做一次重新排序
把所有的引爆點都放到最後去觸發,成本會更小。
請問有人有更佳的計算辦法嗎??
---
獻醜了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.207.15
推 lovewa:115的同學?資工系的嗎? 01/08 21:50
推 cplusplus:學弟 XD 哈~ 01/08 22:34
推 H45:樓上這兩隻是..學長嗎= =? 01/09 00:22
推 lovewa:我不是,我是路人,只是剛好有研究到A*...^^ 01/09 01:00