嗯,我正在考虑做一个Tetravex求解程序,以练习我的代码编写技能(语言可能是Visual Basic),我需要帮助找到一个求解它的算法。对于那些不知道什么是tetravex的人来说,可以看看这个http://en.wikipedia.org/wiki/TetraVex。我能想到的唯一算法是蛮力方式,将一个瓷砖随机放置在一个角落,然后尝试每一个可能的瓷砖旁边,继续相同的过程,如果它到达死胡同,恢复到以前的状态,并放置一个不同的瓷砖。那么有没有人能想出一个更好的算法呢?谢谢您抽时间见我。
发布于 2010-02-09 03:10:17
这里有一些想法。
一种简单的暴力算法会尝试以递归的方式填充网格,方法是以固定的顺序枚举网格位置(例如,行大小),并总是尝试将每一个可能的部分都放在当前位置,然后递归。这就是你提到的,它的效率非常低。
一个改进是始终计算每个自由位置的拟合件数,然后在拟合最少的位置上递归;如果有零个拟合件,立即回溯;如果有一个只有一件拟合,则填充该位置并继续(未创建分支);否则选择具有最少拟合件的位置(≥2)并从那里继续。
一旦你有了这个算法,下一个问题就是如何进一步削减搜索空间。比方说,如果A块的顶部位置为"1“,B块的底部位置为"1”,并且A> B,则您知道"1 at top position“块中至少有A-B必须实际放置在顶行,因此您可以从任何其他位置排除它们。这有助于减少分支因素,并更早地发现死胡同。
您还应该在每个递归步骤中检查每个块是否至少有一个适合它的点(在验证没有任何块只适合于一个位置以提高速度后进行此检查)。如果有一块不适合任何地方,你需要立即回溯。您可以将其扩展到检查每一对块是否适合可能更好的早期死锁检查功能。
还有一种策略叫做“非时间顺序回溯”或“回跳”,它起源于对SAT求解的研究。这有助于您在到达死胡同时一次回溯多个级别;如果您愿意,您可以在google中搜索这些术语以找到更多,但您需要做一些脑力工作来将概念映射到您的问题空间中。
发布于 2010-02-08 09:51:02
第一个改进是计算有多少对匹配的数字,如果在正方形的顶部有5个"1“,但底部只有4个,那么一定有一个”1“指向网格的顶部。
发布于 2010-02-08 10:04:41
在任何给定的部分解决的棋盘上,我都会
在伪代码中,它将是
top:
evaluate # of tiles that match at each empty square
if any square has 0 matches, unwind to <prev>
if any square has 1 match, lay tile, goto top
save current board as <prev>
play randomly at square with minimum number of matches, goto top作为优化,您可以忽略不接触任何具有平铺的正方形的评估方块,因为它们将始终允许所有剩余的平铺。
https://stackoverflow.com/questions/2219166
复制相似问题