我有最后一套瓷砖,其中每一条边可以有四种颜色。
任务是从给定的一组(有限的)瓷砖中找到一个最大可能的正方形构建。瓷砖可以旋转。
我需要设计3个算法来找到这个任务的解决方案。一个完整的和两个近似的。
显然,这是我的算法课的任务,所以我不是在询问完整的解决方案(因为这将是不公平的),而是询问一些方向。
我已经设计了一种完整的算法(使用回溯-搜索一个大小为sqrt(n)的正方形-如果找不到它,试着找到更小的,等等),但我不知道如何创建近似算法。
我认为一个人会有点愚蠢,只有在特定的情况下才会找到一个好的答案,只是为了证明这不是一个好的方法,但我仍然需要一个比回溯快得多的方法,而且是一个相当好的方法。
这个问题也是NP难的吗?我的回溯算法是指数算法,但这并不意味着没有更好的算法了……
编辑:我有一个指数时间的完整算法,谁能给我一些提示,如何用多项式时间或比指数时间更好的东西来建立这个问题的某种近似?
EDIT2:我的想法是,这个问题可以转化为一个将图简化为正方形网格图( http://mathworld.wolfram.com/GridGraph.html )的问题。如果以这种方式排列瓦片来构建网格,仍然存在问题,但这可能是一个很好的起点。是否有任何,例如,贪婪或任何其他近似算法,用于将图缩减为正方形网格图?
发布于 2011-10-25 07:51:07
假设你的回溯算法构造k *k的正方形来增加k的值,你可以用启发式扩展回溯算法。因此,不要随意选择下一个瓷砖,而是选择并附加一个瓷砖,使空闲瓷砖的颜色与正方形上的颜色“一致”。最大的问题是找到“协议”启发式。一种可能的启发式方法是在免费的瓷砖上找到最不常见的颜色并使用它。
https://stackoverflow.com/questions/7882264
复制相似问题