algorithm - 从一组有限的图 block 中找到最大的平方(近似值)

Question

我有最后一组图 block ，其中每条边都可以有四种颜色。
任务是从这个瓷砖的给定集合(有限)中找到最大可能的正方形构建。瓷砖可以旋转。
我需要设计 3 种算法来为这个任务找到解决方案。一个完全和两个近似。
显然，这是我在算法课上的任务，所以我不是在询问完整的解决方案(因为这不公平)，而是在询问一些方向。
我已经设计了一种完整的算法(使用回溯 - 搜索大小为 sqrt(n) 的正方形 - 如果找不到，请尝试找到更小的等等)但我不知道如何创建近似算法。
我认为只有在特定情况下才能找到好的答案的人会有点愚蠢，只是为了证明这不是一个好的方法，但我仍然需要一个比回溯快得多的方法，而且非常好。
这个问题也是NP难的吗？我的回溯算法是指数算法，但这并不意味着没有更好的算法......

编辑:我有完整的指数时间算法，有人能给我一些提示，如何用多项式时间或比指数时间更好的东西为这个问题建立某种近似吗？

EDIT2:我的想法是可以将此问题更改为将图形简化为方形网格图 (http://mathworld.wolfram.com/GridGraph.html) 的问题。如果瓷砖可以以这种方式排列以构建网格，仍然存在问题，但这可能是一个很好的起点。是否有任何例如贪婪算法或任何其他近似算法可将图形简化为方形网格图形？

Answer 1

假设您的回溯算法构建 k×k 正方形以增加 k 值。您可以使用启发式方法扩展回溯算法。因此，不要随机选择下一个瓷砖，而是选择并粘贴一 block 瓷砖，使空闲瓷砖的颜色与正方形上的颜色“一致”。最大的问题是找到“协议(protocol)”启发式方法。一种可能的启发式方法是在空闲图 block 上找到最不常见的颜色并使用它。