algorithm - 按规则分配资源——模拟退火合适吗？

Question

我想设计一个可以按规则分配资源的应用程序。我相信模拟退火会起作用，但我不太熟悉它，我想知道是否有可能合适的替代算法。

例如，如果我有一个网格，并且我可以为网格中的每个单元格着色，我想设计一种算法来为规则集找到最佳或接近最佳的解决方案，如下所示:

• 1000x1000 网格
• 必须放置 500 个红细胞、500 个蓝细胞和 1000 个绿细胞
• 一个红细胞必须接触另一个红细胞
• 一个蓝色细胞不能接触另一个蓝色细胞
• 绿色单元格只能沿着边缘放置
• 可以根据彩色单元格距左上角的平均距离对排列进行评分

模拟退火是否适合解决此问题？我需要一种能够可靠地快速(几秒到几分钟)计算出解决方案的算法。

Answer 1

模拟退火会很快接近最优解。但是，正确实现模拟退火(不需要那么多代码)可能非常具有挑战性。许多人(包括过去的我自己)实现错误，认为他们做对了，并认为算法不是那么好。

替代算法是禁忌搜索、遗传算法、单纯形法、...

这是您的约束在 Drools Planner 中的样子(java、开源、美国手语):

rule "A red cell must be touching another red cell"
when
   // There is a cell assignment of color red
   $a1: CellAssignment(color = RED, $x1 : x, $y1 : y)
   // There is no other red cell a neighbor of it
   not CellAssignment(color = RED, eval(MyDistanceHelper.distance(x, y, $x1, $y1) == 1))
then
   insertLogical(new IntConstraintOccurrence(
            "A red cell must be touching another red cell", 
            ConstraintType.NEGATIVE_HARD, 1, // weight 1
            $a1));
end

rule "A blue cell must not be touching another blue cell"
when
   // There is a cell assignment of color blue
   $a1: CellAssignment(color = BLUE, $x1 : x, $y1 : y)
   // There is another blue cell a neighbor of it
   $a2: CellAssignment(color = BLUE, eval(MyDistanceHelper.distance(x, y, $x1, $y1) == 1))
then
   insertLogical(new IntConstraintOccurrence(
            "A blue cell must not be touching another blue cell", 
            ConstraintType.NEGATIVE_HARD, 1, // weight 1
            $a1, $a2));
end

...

现在有趣的部分是:一旦你对规则进行了评分，你就可以在其上使用多种算法(禁忌搜索、模拟退火等)(参见 Benchmarker 支持)并使用最好的一个在生产中。引用手册中有更多信息。