约束，以避免在此搜索任务中生成重复

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 

会是正确的。而这一点你可以非常轻松地保护：决不允许其第一个成员少于其前任第一个成员的附加顺序。