问具有邻域搜索的子集和- java

EN

邻里关系没有一个独特的定义，它取决于问题。在您的例子中，一个好的定义可能是all the tuples that have (at most) n different elements from the current solution，其中n可能是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，，... ]

让我们使用下面的例子：

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

• 我们可以向其中添加另一个x_i，例如创建x1、x2、x3、x7、x8
• ，也可以从其中删除一个x_i创建例如x2、x3、x7

使用上述操作之一从S获得的每一个这样的解都是S的邻域。所有这些解都来自邻域。

请记住，x1、x3、x2和x1、x2、x3是相同的解决方案，因为元素的顺序并不重要。

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

与示例中的S对应的向量将如下所示:S= 0，1，1，1，0，0，0，0，1，0，0

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

我希望这能帮到你。