避免在此搜索任务中生成重复项的约束
我必须解决以下优化问题： 给定一组元素（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
我尝试使用 A* 和一些启发式方法来解决此问题的更大版本（元素多于 6 个，而不是 1000 个）。从零序列开始，逐步将元素添加到现有序列或作为新序列，直到获得包含所有元素的序列集。 我遇到的问题是，在生成可能的解决方案时，我最终会得到重复项，例如在上面的示例中，生成了所有以下组合：
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 应该始终位于 j<=i 的 seqj 中来限制生成的“重复项”数量，因此，如果您有两个元素 E1，则
seq1:E1
seq2:E2
只会生成 E2，而不是
seq1:E2
seq2:E1
我想知道是否存在这样的元素约束将完全阻止生成重复项，而不会无法生成集合的所有组合。
I have to solve the following optimization problem:
Given a set of elements (E1,E2,E3,E4,E5,E6) create an arbitrary set of sequences e.g.
seq1:E1,E4,E3
seq2:E2
seq3:E6,E5
and given a function f that gives a value for every pair of elements e.g.
f(E1,E4) = 5
f(E4,E3) = 2
f(E6,E5) = 3
...
in addition it also gives a value for the pair of an element combined with some special element T, e.g.
f(T,E2) = 10
f(E2,T) = 3
f(E5,T) = 1
f(T,E6) = 2
f(T,E1) = 4
f(E3,T) = 2
...
The utility function that must be optimized is the following:
The utility of a sequence set is the sum of the utility of all sequences.
The utility of a sequence A1,A2,A3,...,AN is equal to
f(T,A1)+f(A1,A2)+f(A2,A3)+...+f(AN,T)
for our example set of sequences above this leads to
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
I try to solve a larger version (more elements than 6, rather 1000) of this problem using A* and some heuristic. Starting from zero sequences and stepwise adding elements either to existing sequences or as a new sequence, until we obtain a set of sequences containing all elements.
The problem I run into is the fact that while generating possible solutions I end up with duplicates, for example in above example all the following combinations are generated:
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
which all have equal utility, since the order of the sequences does not matter.
These are all permutations of the 3 sequences, since the number of sequences is arbitrairy there can be as much sequences as elements and a faculty(!) amount of duplicates generated...
One way to solve such a problem is keeping already visited states and don't revisit them. However since storing all visited states requires a huge amount of memory and the fact that comparing two states can be a quite expensive operation, I was wondering whether there wasn't a way I could avoid generating these in the first place.
THE QUESTION:
Is there a way to stepwise construct all these sequence constraining the adding of elements in a way that only combinations of sequences are generated rather than all variations of sequences.(or limit the number of duplicates)
As an example, I only found a way to limit the amount of 'duplicates' generated by stating that an element Ei should always be in a seqj with j<=i, therefore if you had two elements E1,E2 only
seq1:E1
seq2:E2
would be generated, and not
seq1:E2
seq2:E1
I was wondering whether there was any such constraint that would prevent duplicates from being generated at all, without failing to generate all combinations of sets.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
嗯，这很简单。只允许生成根据第一个成员排序的序列，也就是说，从上面的示例来看，只有这样
才是正确的。您可以非常轻松地保护这一点：绝不允许其第一个成员小于其前任的第一个成员的其他序列。
Well, it is simple. Allow generation of only such sequences that are sorted according to first member, that is, from the above example, only
would be correct. And this you can guard very easily: never allow additional sequence that has its first member less than the first member of its predecessor.