最大化相邻作物的功能；园林优化问题

Question

想象一个小花园，分成8个相等的部分，每个部分为一个平方英尺。花园为4英尺x 2英尺，因此“垃圾箱”分为两排。让我们将它们编号为：

0 1 2 3
4 5 6 7

我们想在每个植物中布置不同的植物。每个植物都有一些喜欢的伙伴。例如，罗勒喜欢靠近西红柿。我想为花园找到一种安排，以使积极关系的数量最大化。

使用python，很容易将列表中的不同农作物推入。创建评分功能以查找特定安排的总分也很容易。我的问题是减少问题的大小。在此设置中，有8个！ （40320）可能的排列，花园中植物的不同排列。在我要解决的实际问题中，我使用的是16箱花园，面积是原来的两倍。那是16岁！可能进行的排列超过20万亿个。花费的时间太长了。 （为简化起见，我在这里用8个容器而不是16个容器描述了问题。）

我已经使用itertools.permutations对8个项目进行所有可能的排列。但是，仅跳过本质上是重复的安排还不够。如果我将花园布置旋转180度，那实际上是相同的解决方案。如果我从左到右或上下镜像，它们也是相同的解决方案。我该如何设置以减少总的问题集？

在其他问题中，我使用查找来检查已检查的解决方案列表。有了如此众多的解决方案，这将比仅仅通过所有解决方案花费更多的时间。请帮助我减少问题所在！

# maximize the number of good relationships in a garden
import itertools

# each crop has 2 items: the name of the crop and a list of all the good friends
crops = []
crops.append(['basil',['tomato','pepper','lettuce']]) # basil likes to be near tomato, pepper or lettuce
crops.append(['strawberry',['beans','lettuce']])
crops.append(['beans',['beet','marigold','cucumber','potato','strawberry','radish']])
crops.append(['beet',['beans']])
crops.append(['cucumber',['lettuce','radish','tomato','dill','marigold']])
crops.append(['marigold',['tomato','cucumber','potato','beans']])
crops.append(['tomato',['cucumber','chives','marigold','basil','dill']])
crops.append(['bok_choy',['dill']])

# 0 1 2 3 This is what the garden looks like, with 8 bins
# 4 5 6 7
mates = [ [0,1], [1,2], [2,3], [4,5], [5,6], [6,7], [0,4], [1,5], [2,6], [3,7] ] # these are the relationships that directly border one another

def score(c): # A scoring function that returns the number of good relationships
    s = 0
    for pair in mates:
        for j in c[pair[1]][1]:
            if c[pair[0]][0] == j:
                s = s + 1
        for j in c[pair[0]][1]: # and the revers, 1-0
            if c[pair[1]][0] == j:
                s = s + 1
    return s

scoremax = 0
for x in itertools.permutations(crops,8):
    s = score(x)
    if s >= scoremax: # show the arrangement
        for i in range(0,4):
            print( x[i][0] + ' ' * (12-len(x[i][0])) + x[i+4][0] + ' ' * (12-len(x[i+4][0])) ) # print to screen
        print(s)
        print('')
        if s > scoremax:
            scoremax = s

Answer 1

通常，对于此类问题，有效地打破对称通常非常困难。

在这种情况下，似乎只有两个对称：

• 从右到左与从左到右相同
• 从上到下与从上到下相同

如果添加两个条件，我们可以同时破坏它们：

0号地块的作物都应小于3号地块和4号地的作物

对于“较小的”，我们可以使用任何给出严格排序的度量。在这种情况下，我们可以简单地比较字符串。

然后，主循环如下所示。一旦达到最佳scoremax，将仅打印不对称的解决方案。同样，每种可能的解决方案都将直接打印或以规范形式打印（即水平和/或垂直镜像）。

scoremax = 0
for x in itertools.permutations(crops,8):
    if x[0][0] < x[3][0] and x[0][0] < x[4][0]:
        s = score(x)
        if s >= scoremax: # show the arrangement
            for i in range(0,4):
                print( x[i][0] + ' ' * (12-len(x[i][0])) + x[i+4][0] + ' ' * (12-len(x[i+4][0])) ) # print to screen
            print(s)
            print('')
            if s > scoremax:
                scoremax = s