建议用于解决游戏Globs的算法和数据结构(http://www.deadwhale.com/play.php?game=131).以一种令人讨厌的方式非常有趣.
根据N(网格的大小)(N> = 14)来说明方法的时空复杂度(big-O).具有低复杂度的足够有效的算法是优选的.
(MatrixFrog正确地指出这个游戏也被称为FloodIt,Smashery在3个月之前在他引用的链接中给出了一个解决方案.你所有的人都建议修剪/贪婪,只有1个前瞻,这给出了不理想的解决方案.)
游戏生成nxn节点的随机方格,其中每个节点着色为六种颜色之一(Grn = 1,Ylw = 2,红色= 3,蓝色= 4,Pur = 5,Orn = 6).1级有9x9网格,然后n增加每个级别,最多14级.每个级别你最多可以占用25级,否则你输了.在每个回合中,您选择将左上方节点更改为例如Grn-> Red的颜色,以便将新颜色的任何连接的相邻(水平/垂直)节点同化为形状,并将每个节点同化的1 pt添加到你的分数.评分目标是尽可能少地完成每个网格,例如,如果你在16转中完成,那么你的9个未使用的移动=> 2*9倍数乘以你的总累积分数.
显然有很多方法可以解析这个问题,而使用14x14网格的递归回溯的默认选择是一个可行的竞争者; 这适用于哪些其他类型的数据结构？一个*？不要挂在最优,我想知道是否有一个"足够好"的算法.
(我认为这可能是一个有趣的项目,可以编写一个机器人并获得愚蠢的高分.虽然我的肉体自我得到了3.5E + 12.)
这个游戏真的吸引了我的兴趣,所以我花了几天时间研究它.
我注意到的第一件事是,很容易证明在第一块板之后(在某些情况下可能是2块),提高分数的最快方法是使用乘数.因此,我建立了一个系统,其目标是以最少的步骤解决每个板.我开始想要使用A*,因为它通常只针对这些类型的搜索问题而构建......但是,这个问题仍然是一个doozie.
在谈论A*时,它的有效性实际上归结了您对启发式估计的选择.越接近猜测实际距离,为了达到目标就必须扩展的节点越少.对于这个问题,我经历了一些估算的想法,但是大多数都打破了A*规则,即你不能过度估计实际距离,否则就会打破A*的最优性.
然而,有一些工作.这个帖子中的其他人发布了关于只剩下剩余颜色的数量作为估计,这是可以接受的,因为它不能过度估计(你必须为每个剩余颜色至少改变一次颜色,而不是主要"泛滥"区域的一部分.这种启发式的问题在于它很难估计实际距离.例如,第一步,通常估计颜色的数量,6.它通常扩展为2个移动,每个移动通常估计为7如此深度为5级,对于10x10的板大小,大多数叶子的估计值为11.这种启发式基本上是广度优先搜索的实现,直到你从你的4或5个移动到达目标.这不是很有效,在我自己的测试中,指数大约在9号板上运行,这通常需要在解决方案中进行大约14次移动.应该指出的是,我的解决方案是非常高的水平,并没有太多的注意力来加快速度.
问题在于,当每个步骤对整个解决方案的实际距离进行重大改进时,A*才真正有用.直接看问题,你可能不会找到一个比这更好的启发式,而不会过度估算成本.但是,如果您将问题转换为另一个问题,那么更好的启发式方法会突然出现.启发式"剩余颜色数"正在回答问题,剩下的可能移动的最小数量是多少.对于这个问题的答案,我问自己"董事会中哪个位置需要最多步骤才能到达"？对于我的启发式,我最终解决了"右下角有多少步骤"的答案.通过运行另一个更像是查找地图方向然后计算解决方案中的步骤数的A*搜索,这很容易实现.我意识到这是选择板上的一个任意点,但是它在测试中运行良好并且在每个剩余点上运行A*在我的单处理器测试机器上花费了相当多的时间.
然而,这个启发式单独在右下角成为洪水区域的一部分之后有崩溃的倾向,因此最终结果是MAX(右下角最小步骤,颜色的数量不是主要洪水的一部分).最终,我的高级实现能够在不到一秒的时间内实现一些非常大的电路板尺寸.
我会把记录设置留给你.
京公网安备 11010802040832号 | 京ICP备19059560号-6 