Мне нужно решить следующую задачу оптимизации: учитывая набор элементов (E1, E2, E3, E4, E5, E6), создать произвольный набор последовательностей, например,
seq1:E1,E4,E3
seq2:E2
seq3:E6,E5
и получить функциюf, который дает значение для каждой пары элементов, например,
f(E1,E4) = 5
f(E4,E3) = 2
f(E6,E5) = 3
...
, кроме того, он также дает значение для пары элемента, объединенной с некоторым специальным элементом T, например,
f(T,E2) = 10
f(E2,T) = 3
f(E5,T) = 1
f(T,E6) = 2
f(T,E1) = 4
f(E3,T) = 2
...
Функция полезности, которая должна быть оптимизирована, является следующей: полезность набора последовательностей является суммой полезности всех последовательностей.Полезность последовательности A1, A2, A3, ..., AN равна f (T, A1) + f (A1, A2) + f (A2, A3) + ... + f (AN, T)для нашего примера набора последовательностей выше это приводит к
seq1: f(T,E1)+f(E1,E4)+f(E4,E3)+f(E3,T) = 4+5+2+2=13
seq2: f(T,E2)+f(E2,T) =10+3=13
seq3: f(T,E6)+f(E6,E5)+f(E5,T) =2+3+1=6
Utility(set) = 13+13+6=32
Я пытаюсь решить более крупную версию (больше элементов, а не 1000) этой проблемы, используя A * и некоторую эвристику.Начиная с нуля последовательностей и поэтапно добавляя элементы либо в существующие последовательности, либо в виде новой последовательности, пока мы не получим набор последовательностей, содержащий все элементы.Проблема, с которой я сталкиваюсь, заключается в том, что при создании возможных решений я получаю дубликаты, например, в приведенном выше примере генерируются все следующие комбинации:
seq1:E1,E4,E3
seq2:E2
seq3:E6,E5
+
seq1:E1,E4,E3
seq2:E6,E5
seq3:E2
+
seq1:E2
seq2:E1,E4,E3
seq3:E6,E5
+
seq1:E2
seq2:E6,E5
seq3:E1,E4,E3
+
seq1:E6,E5
seq2:E2
seq3:E1,E4,E3
+
seq1:E6,E5
seq2:E1,E4,E3
seq3:E2
, которые имеют одинаковую полезность, начиная с порядкапоследовательности не имеют значения.Это все перестановки трех последовательностей, так как число последовательностей произвольно, может быть столько же последовательностей, сколько элементов и количество сгенерированных дубликатов (!) Факультета ... Одним из способов решения такой проблемы является сохранение уже посещенных состояний ине возвращайтесь к ним.Однако, поскольку хранение всех посещенных состояний требует огромного объема памяти и того факта, что сравнение двух состояний может быть довольно дорогой операцией, мне было интересно, не было ли способа, которым я мог бы избежать их генерации.
ВОПРОС: Есть ли способ пошагового построения всех этих последовательностей, ограничивающий добавление элементов таким образом, что генерируются только комбинации последовательностей, а не все вариации последовательностей. (Или ограничивают количество дубликатов?)
В качестве примера я нашел способ ограничить количество «дубликатов», генерируемых путем указания, что элемент Ei всегда должен быть в последовательности с j <= i, поэтому, если у вас есть два элемента E1, Только E2 </p>
seq1:E1
seq2:E2
будет сгенерировано, а не
seq1:E2
seq2:E1
Мне было интересно, существует ли какое-либо такое ограничение, которое вообще предотвратило бы создание дубликатов, без сбоев генерациивсе комбинации комплектов.