要实现的爬山算法如下：

1. 该算法应该有四个输入：和往常一样，会有一个多重集 S 和整数 k，它们是子集和问题的 和Subset；Sum此外，将有两个整数 q 和 r，其作用定义如下。
2. 执行以下 q 次：

(a) 选择一个随机子集（multiset）$S_0$的 S 作为current子集。

(b) 执行以下 ( hill climbing) r 次：

一世。找到当前子集的随机邻居 T（参见下面的邻居定义）。

ii. 如果邻居 T 的残差较小，则使 T 成为当前子集。

(c) 从子集开始时跟踪最终当前子集的残差 $S_0$.

3. 返回算法测试的 q 个子集的最小残差。

定义：子集（多重集）B ⊆ S 是 S 的子集 A 的邻居，如果你可以通过将一个或两个整数从 A 移动到 B，或者通过将一个或两个整数从 B 移动到 A，或者通过将 A 中的一个整数与 B 中的一个整数交换。生成 S 的子集 A 的随机邻居 B 的简单方法如下：

1. 将 S 的元素排序为$x_1, x_2, ..., x_n$.
2. 将 B 初始化为 A 的克隆。
3. 选择两个不同的随机索引 i 和 j，其中$1 ≤ i; j ≤ n$.
4. 如果$x_i$在 A 中，将其从 B 中删除。否则，将 xi 添加到 B。
5. 如果$x_j$在 A 中，则以 0.5 的概率将其从 B 中移除。如果$x_j$不在 A 中，则以 0.5 的概率添加$x_j$给 B。

状态空间本身似乎还可以，但您的方法有一些缺点。首先，您需要选择大小的初始状态$n$. 如果最优解是大小怎么办$\frac{n}{4}$或者$10n$? 然后使用这种方法进行搜索可能需要很长时间，因为您开始的距离很远。如果有多个解决方案，您是否关心您找到哪一个或首选最小的零子集？我将假设空集$X'=\{\}$不是解决方案，并且首选具有较小基数的解决方案。

我建议使用生成启发式来构建初始状态，然后从该状态运行您的爬山程序。例如，生成启发式可能是这样的：“选择一对元素 ($x_1$,$x_2$） 从$X$这样$x_1 + x_2$尽可能接近零，并设置$X' =\{x_1, x_2\}$作为初始状态”。要应用此启发式方法，您需要首先检查$n(n-1)$对的子集。如果这不是一个解决方案，那么它有望非常接近状态空间中的解决方案，因此是一个很好的起点。

另一个问题是爬山不记得以前访问过的状态，当您允许移动以添加和删除元素时，您最终可能会无限循环$X'$. 例如，假设$X'=\{1\},X=\{-3,-50,-50,100\}$. 显然最优解是$X''=\{-50,-50,100\}$但是您的方法将添加元素$-3$到$X'$首先，然后删除$-3$，然后选择$-3$再次等等，因为这些状态的客观价值低于任何具有以下条件之一的状态$-50$或者$100$在里面。所以我认为你需要使用更复杂的方法来防止两次访问同一个状态。