1

我正在尝试使用邻域算法来实现子集和问题。这是伪代码： 1. Generate a random solution for the problem and call it S 2. Compute the neighborhood of S and choose S' as the best solution in the neighborhood 3. If S' is better than S then go to step 4, else go to step 6 4. S = S' 5. Go to step 2 6. Return S as the best solution encountered 给定一个包含 10 个元素（+ve 和 -ve）的集合 X，我必须找到 X 的一个子集，使得总和尽可能接近 0。

按照伪代码，我生成了一个随机解 S，但在构建邻域 S 时遇到了一些困难。

如何计算 S 的邻域？S附近是什么地方？

例如

X = [x0, x1, x2, x3, x4, x5, x6, x7, x8, x9]

S = [x1, x7, x2, x3]

S附近是什么地方？

4

2 回答 2

0

邻里没有唯一的定义，这取决于问题。在您的情况下，一个好的定义可能是all the tuples that have (at most) n different elements from the current solutionn 可能在哪里1, 2 , size - 1（如果您认为n = size您正在考虑整个解决方案空间并且谈论邻域没有更多意义）。

在您的示例中，采用与当前步骤不同的所有解决方案在以下一组解决方案中结束：

D = [ [x0, x7, x2, x3], [x4, x7, x2, x3], [x5, x7, x2, x3], [x6, x7, x2, x3], [x8, x7, x2, x3], [x9, x7, x2, x3], [x1, x0, x2, x3], [x1, x4, x2, x3], ... ]

于 2016-06-20T13:13:53.263 回答
0

让我们使用这个例子：

S 是一种解决方案，让我们看看如何从中生成另一种解决方案：

  • 我们可以向它添加另一个 x_i，例如 [x1, x2, x3, x7, x8]
  • 或者我们可以从中删除一个 x_i，例如 [x2, x3, x7]

使用上述操作之一从 S 获得的每个此类解决方案都是 S 的邻居。所有此类解决方案都形成邻域。

请记住， [x1, x3, x2] 和 [x1, x2, x3] 是相同的解决方案，因为元素的顺序无关紧要。

形式上，每个解都是长度为 10 的二进制向量 v，由 0 和 1 组成，例如 v[i] == 1，如果相应的解包含 x_i。

与示例中的 S 对应的向量如下所示： S = [0, 1, 1, 1, 0, 0, 0, 1, 0, 0]

每个这样的向量都是解图中的一个顶点。如果可以使用某种简单的操作（例如上述那些）将一个顶点转换为另一个顶点，则存在两个这样的顶点之间的边。

我希望这有帮助。

于 2016-06-20T13:33:47.853 回答