消泡泡： 原出处：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