約束，以避免在此搜索任務中生成重複

Question

我必須解決以下優化問題：給定一組元素（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 

我嘗試解決一個更大的版本（多個元素大於6，而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 

其中所有具有相等的效用，因爲的順序序列無關緊要。 這些都是3個序列的所有排列，因爲序列的數量是仲裁的，可以有多少序列作爲元素和教師（！）的副本數量生成... 解決此類問題的一種方法是保持已訪問並且不會重新審視它們。然而，由於存儲所有訪問狀態需要大量內存，並且比較兩個狀態的操作可能是一個相當昂貴的操作，所以我想知道是否沒有辦法避免產生這些狀態。

的問題是： 有一種方法，以逐步地構建所有這些序列約束元件的添加中，只有序列的組合產生，而不是序列的所有變體的方式（或限制副本的數目）。作爲一個例子，我只找到一種方法來限制通過聲明一個元素Ei應該總是在seqj中並且j < = i所產生的'重複項'的數量，因此如果你有兩個元素E1，E2

seq1:E1 
seq2:E2 

將被產生的，並且不

seq1:E2 
seq2:E1 

我想知道是否有任何這樣的約束，將防止產生在所有重複，而不失效，以產生集合所有組合。

Answer 1

好吧，很簡單。允許僅生成根據第一個成員排序的這樣的序列，也就是從上面的例子中，只有

seq1:E1,E4,E3 
seq2:E2 
seq3:E6,E5 

會是正確的。而這一點你可以非常輕鬆地保護：決不允許其第一個成員少於其前任第一個成員的附加順序。