平铺排列算法 [英] tile arrangement algorithm

问题描述

我需要安排在一个空间正方形瓷砖大小相同的，可能是完全充满的瓷砖。某些砖可以被锁定在适当位置。瓷砖来自组，每个组应位于一起（如果可能的话，可能无法由于锁定）。也有一些其他的次要多个人（而不仅仅是组）preferences。

I need to arrange square tiles of the same size in a space that could be completely full of the tiles. Some tiles may be locked in place. Tiles come from groups, and each group should be located together (if possible, may not be due to locking). There are also some other secondary and more individual (not just by group) preferences.

什么算法将是有益的？我试图把它变成一个线性（以及MIP实际上）规划问题，但我不知道如果我能做到这一点。

What algorithms would be useful? I am trying to turn this into a linear (well MIP actually) programming problem, but I am not sure if I can accomplish that.

推荐答案

组合优化问题（如果你想最大限度的适合的辅助，更个人preferences）通常可以解决的分支定结合或者通过随机搜索，例如：模拟退火或禁忌搜索。

Combinatorial optimization problems (if you want to "maximize" the fit to the secondary and more individual preferences) can be typically solved by branch-and-bound or by stochastic search, e.g. simulated annealing or tabu search.

在分支定界，您可以通过部分的解决方案进行搜索，并跟踪迄今达成的最好的完整解决方案。每当你到达一个局部解决方案，你能证明它不能完成，以获得比迄今达成的最佳解决方案更好的解决方案，你马上原路返回。

In branch-and-bound, you search through partial solutions, and keep track of the best complete solution reached so far. Whenever you reach a partial solution where you can prove that it can't be completed to get a better solution than the best solution so far reached, you backtrack immediately.

随机搜索最有可能是一个更适合您的问题。它的工作原理是首先是一个随机瓷砖的位置，然后如交换到瓷砖随意，把preferring举动，带来更高的满意度（高preference得分），而你的情况将意味着更多的瓷砖，更适合二级preferences。细节有所不同。请参见

Stochastic search would most likely be a better fit to your problem. It works by starting with a random tile placement, and then e.g. swapping to tiles randomly, put preferring moves that lead to higher satisfaction (higher preference score), which in your case would mean more connected tiles and more fit to the secondary preferences. The details differ. See

• http://en.wikipedia.org/wiki/Branch_and_bound
• http://en.wikipedia.org/wiki/Simulated_annealing
• http://en.wikipedia.org/wiki/Tabu_search

• http://en.wikipedia.org/wiki/Branch_and_bound
• http://en.wikipedia.org/wiki/Simulated_annealing
• http://en.wikipedia.org/wiki/Tabu_search

这篇关于平铺排列算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！