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