※ 引述《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