UIUC CS598CSC 组合优化讲义.pdf
需积分: 5 194 浏览量
2024-02-03
12:14:26
上传
评论
收藏 6.02MB PDF 举报
CS 598CSC: 组合优化 讲座日期：01/19/2010
讲师：Chandra Chekuri 记录员：Alina Ene
1 引言和动机
粗略地说，一个优化问题的概述如下：给定一个问题的实例，找到给定实例的所有解中的“最佳”
解。 我们主要关注离散优化问题，其中每个实例和解集都来自一个离散集合。这与连续优化不同
，连续优化的输入实例和解集可以来自连续域。 其中一些区别并不像线性规划那样明确。
我们假设对计算复杂性类 P , NP , coNP有所了解。 在这门课程中，我们主要关注多项式时
间可解的“组合”优化问题。
组合优化问题是离散优化问题的一个子集，尽管没有对它们的正式定义。 组合优化中的典型问题
具有一个对象的基本集合E，解对应于
E
的某些子集（ E的幂集）并且典型目标是找到给定 E上的
一组权重的最大或最小权重解。 例如，在生成树问题中，基本集合 E是图 G= (V, E)的边集，解
是 E的子集，对应于 G中的生成树。
我们将对 NP优化问题感兴趣 - 简称为 NPO问题。 形式上，问题 Q是Σ
∗
的一个子集，其中Σ
是一个有限字母表，比如二进制。 问题 Q中的每个字符串 I都是 Q的一个实例。 对于一个字符串
x，我们用 |x|表示它的长度。 如果满足以下条件，我们称问题 Q为 NPO问题：
（i）对于每个字符串 x ∈ Σ
∗
，存在一个多项式时间算法可以检查 x是否属于 Q，即 x是否是 Q
的一个有效实例。
（ii）对于每个实例 I，存在一个集合 sol(I) ⊂ Σ
∗
，使得
（a）对于集合s ∈ sol(I)， |s| = poly(|I|)
(b) 存在一个多项式时间算法，对于输入I, s，能够正确地输出是否 ∈解(I)。
(iii) 存在一个函数 val: Σ
∗
× Σ
∗
→ Z，使得对于每个实例 I和
s ∈解(I) ， val(I, s) 能够分配一个整数，并且val可以通过多项式时间算法计算。
给定一个 NPO问题，如果目标是计算给定的 I ∈ Q，
arg min
s∈
解
(I )
val(I, s) ，则称其为最小化问题。 如果目标是计算 arg max
s∈
解
(I )
val(I, s)，则称其为最大化问题。
与一个 NPO问题（比如最大化）相关的一个自然决策问题是：给定 I和一个整数 k，是否存在一
个解S(I) 使得 val(S, I) ≥ k。
我们遇到的许多问题都是 NPO问题。 其中一些问题可以在多项式时间内解决。 广泛认为并
猜测 P = NP，这意味着存在一些NPO问题（特别是那些决策版本是 NP-完全的问题）没有多
项式时间算法。 假设 P = NP，一些重要且有用的问题是：哪些问题属于 P？ 什么特征定义了
P中的问题？
剩余189页未读，继续阅读
资源评论
