问题求解（三） Open Topic 12 笔记
OT：除MAX-SAT和TSP外，分支定界和局部搜索算法还可用于解决其它问题，请为每种算法调研至少1种可以解决的问题，结合例子介绍算法的设计与分析。
分支定界和局部搜索算法
分支定界算法的应用
问题引出——小木棍
有一些同样长的小木棍，他把这些木棍随意砍成几段。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。 给出每段小木棍的长度，求原始木棍的最小可能长度。
问题分析——形式化描述
- 输入：\(\langle n, a_1, a_2, \cdots, a_n\rangle\)。
- 约束 \(\mathcal M(x)=\) \[ \left\lbrace \langle m,\lbrace S_1, S_2, \cdots, S_m\rbrace \rangle: \sum_{S_1}=\sum_{S_2}=\cdots=\sum_{S_m} \text{且 $\lbrace S_i\rbrace$ 构成 $\lbrace a_1, a_2, \cdots, a_n\rbrace$ 的一个划分}\right\rbrace. \]
- 代价：\(m\)。
- 目标：最大化。（即最小化 \(sum/m\)）
问题分析——性质
- 显然 \(m\mid \sum a_i\)。
- 可知 \(m\le n\)，可以多项式时间枚举 \(m\)，故 \(A=\sum a_i/m\) 每组的和得以确定。则只需解决一个判定问题
问题分析——回溯算法
可以分组确定：先确定第一组的组成，再是第二组的组成。使用回溯算法，用 \(S(S_1, S_2, \cdots, S_{i-1}, \lbrace b_1, b_2, \cdots, b_t\rbrace)\)，表示已经确定了前 \(i-1\) 组，第 \(i\) 组已经选定了 \(\lbrace b_1, b_2, \cdots, b_{t}\rbrace\subseteq S_i\) 这些元素。则状态转移可以决定下一个 \(b_{t+1}\in S_i\) 使得总和 \(\le A\)。
问题分析——分支定界
观察，可以 pre-compute 进行对搜索树的裁剪：
- 对于 \(b_1\)，一定选择第一个当前未取过的，因为它一定要包含在某组内（该步不进行分支）。且在替代时从前往后尝试。
- 将 \(a_i\) 从大到小排序，在某次失败时跳过之后连续几个相同的 \(a_i\)。
局部搜索算法——最大团问题
最大团问题：求图中的最大团的阶。
是很经典的 NP Complete。考虑使用局部搜索尝试获得 Local Optima
Neibourhood
每个可行解是一个团 \(V\subseteq G\)。考虑在 \(V\) 中加入一个顶点 \(x\) 作为其非平凡邻居。
- 但是 \(V\cup\lbrace x\rbrace\) 不一定是团：\(x\) 不一定和 \(V\) 中所有点都有边。
- 设 \(x\) 的邻点是 \(N(x)\)，则 \(V'=(V\cap N(x))\cup\lbrace x\rbrace\) 是团。定义为 \(V\) 的邻居。
证明 Neibourhood
- 自反性：定义为平凡邻居
- 对称性：容易发现该定义是不对称的，但若将其视作有向图，则它是强连通的。
- 可达性：每次加入目标团的一个顶点，显然可达。