利用判定问题求解优化问题时的一种方法
2016-06-01
tags: 判定问题, 优化问题, 复杂度
利用判定问题求解优化问题的一般思路是不停迭代调用判定问题求解器，直到找到最优的数值条件。比如，求解一张图的最小着色数问题，可以利用判定问题“某图是否可以k着色”的求解器，不断更换k取值找到最优。
这样的思路一般是线性的，比如使得k从0开始逐次加一。而当k在某种假设下可以有一个范围时，这种思路可以使用二分搜索进行，使得调用次数从线性（\(O(k)\)）降到对数（\(O(logk)\)）。但是，当这个范围的上界不存在时，这种简单的二分不可行。
此时，可以采用如下方法：
- 在每次迭代时，取\(k=0, 2^0, 2^1, 2^2, ...\)
- 找到一个区间\([2^i, 2^{i+1}]\)使得区间两端判定问题结果相反（最优值在此区间内）
- 在此区间内进行二分搜索，确定最优值
这种情况下，搜索次数也是对数的。令\(n=\lceil logk^* \rceil\)，其中\(k^*\)是k的最优值，则：
\[总搜索次数 \le n + log(2^n - 2^{n-1}) = 2n - 1 = O(logk)\]