Представьте себе небольшой сад, разделенный на 8 равных частей, каждая квадратного фута. Сад 4 фута х 2 фута, поэтому «мусорные баки» расположены в два ряда. Давайте обозначим их как:
0 1 2 3
4 5 6 7
Мы хотим расположить разные растения на каждом. У каждого растения есть приятели, с которыми им нравится быть рядом. Например, базилик любит быть рядом с помидорами. Я хочу найти договоренность для сада, которая максимизирует количество положительных отношений.
Используя python, легко объединить различные культуры в списке. Также легко сделать функцию подсчета очков, чтобы найти общий счет для конкретной договоренности. Моя проблема заключается в уменьшении размера проблемы. В этой настройке их 8! (40 320) возможные перестановки, различные расположения растений в саду. В настоящем, который я пытаюсь решить, я использую сад с 16 корзинами, в два раза больше. Это 16! возможные перестановки до go через, более 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
РЕДАКТИРОВАТЬ: Чтобы уточнить, это симметрия и ротации, которые я пытаюсь пропустить. Для ясности я буду использовать числа вместо строк с названиями растений.
0 1 2 3 is same when mirrored 3 2 1 0
4 5 6 7 7 6 5 4
0 1 2 3 is same when mirrored 4 5 6 7
4 5 6 7 0 1 2 3
0 1 2 3 is same when rotated 7 6 5 4
4 5 6 7 3 2 1 0