算法设计与分析W9-NP完全理论
VIP免费
2025-01-13
3
0
2.82MB
155 页
5.9玖币
侵权投诉
NP 完全理论
n
目前掌握的算法设计技术
p
分而治之
p
动态规划
p
贪心算法
n
有些问题还未找到高效的算法，如
p0-1
背包问题
p
旅行商问题
p
集合覆盖问题
p
顶点覆盖问题
p… ..
n
需要证明不存在有效的算法
背景介绍
2
n
如何证明一个问题有高效算法？
p
设计一个高效算法
n
如何证明一个问题没有高效算法？
p
难以证明
背景
3
Blame youself
I couldn’t find a
polynomial-time algorithm;
I guess I‘m too dumb.
Show that no-efficient algorithm exists
I couldn’t find a polynomial-
time algorithm,
because no such algorithm
exists!
n
如何证明一个问题有高效算法？
p
设计一个高效算法
n
如何证明一个问题没有高效算法？
p
难以证明
背景
4
I couldn’t find a polynomial-time algorithm,
but neither could these other smart people!
What do you actually do ?
nNP
完全问题
p
是一类问题的集合
p
被认为是一类难解（
Intractable
）问题
n
只要一个
NP
完全问题有高效算法，则所有
NP
完全
问题都有高效算法
nNP
问题是否有“高效”算法仍是一个
未解决的问题（
Open problem
）
n
如何证明一个问题没有高效算法？
p
证明该问题是
NP
难问题（
NP-hard
）
背景：
NP
完全理论
5
主要内容
6
n
判定问题
n
判定问题与最优化问题
nP
问题与多项式时间算法
nNP
问题与多项式时间验证算法
nNP
完全问题与多项式时间归约
nNP
完全问题证明
•3-CNF
可满足性问题（
3SAT
）
•
团问题（
DCLIQUE
）
•
顶点覆盖问题（
DVC
）
•
独立集问题（
DIS
）
•
集合覆盖问题（
SC
）
•
子集和问题（
SS
）
•
带有开放时间和截止时间的调度问题
(SRD)
•
有向哈密顿回路问题（
DHC
）
•
哈密顿回路问题
(HC)
•
旅行商问题
(DTSP)
主要内容
7
n
判定问题与最优化问题
n
P问题与多项式时间算法
n
NP问题与多项式时间验证算法
n
NP完全问题与多项式时间归约
n
NP完全问题证明
n
判定问题：
仅有两种答案：“是”或“否”
（
yes or no, 1
或
0
）
判定问题（
Decision problems
）
8
例：判断一个连通无向图是否为一棵树。
l
输入：连通无向图
!
l
问题：
!
是否是一棵树？
实例
𝑮𝟏
是一棵树
实例
𝑮𝟐
不是一棵树
n
判定问题：
仅有两种答案：“是”或“否”
（
yes or no, 1
或
0
）
判定问题（
Decision problems
）
实例
𝑮𝟏
是一棵树
实例
𝑮𝟐
不是一棵树
9
例：判断一个连通无向图是否为一棵树。
l
输入：连通无向图
!
l
问题：
!
是否是一棵树？
n
判定问题：
仅有两种答案：“是”或“否”
（
yes or no, 1
或
0
）
判定问题（
Decision problems
）
实例
𝑮𝟏
是一棵树
实例
𝑮𝟐
不是一棵树
10
例：判断一个连通无向图是否为一棵树。
l
输入：连通无向图
!
l
问题：
!
是否是一棵树？
实例分为两类：
是树的所有连通无向图
不是树的所有连通无向图
摘要：
展开>>
收起<<
NP完全理论n目前掌握的算法设计技术p分而治之p动态规划p贪心算法n有些问题还未找到高效的算法，如p0-1背包问题p旅行商问题p集合覆盖问题p顶点覆盖问题p…..n需要证明不存在有效的算法背景介绍2n如何证明一个问题有高效算法？p设计一个高效算法n如何证明一个问题没有高效算法？p难以证明背景3BlameyouselfIcouldn’tfindapolynomial-timealgorithm;IguessI‘mtoodumb.Showthatno-efficientalgorithmexistsIcouldn’tfindapolynomial-timealgorithm,becausenosu...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
安2-安3,26-21灌浆施工组织设计VIP免费
2024-11-22 10 -
XX水电站导流洞施工组织措施VIP免费
2024-11-22 11 -
xx公路施工组织设计VIP免费
2024-11-22 12 -
xx电站施工组织设计（投标阶段）VIP免费
2024-11-22 12 -
XXX土地开发整理项目投标文件 施工组织设计VIP免费
2024-11-22 17 -
pccp管穿河施工组织设计VIP免费
2024-11-22 12 -
110kv水利变电站施工组织设计VIP免费
2024-11-22 13 -
7套水电安装精选施工组织设计VIP免费
2024-11-22 14 -
×××供水工程施工组织设计VIP免费
2024-11-22 18 -
XX县城防堤施工组织设计1VIP免费
2024-11-22 15
分类：计算机
价格：5.9玖币
属性：155 页
大小：2.82MB
格式：PDF
时间：2025-01-13
作者详情
相关内容
-
电力工程资料：（一）目录
分类：建筑/施工
时间：2025-06-07
标签：无
格式：PDF
价格：10 玖币
-
电力工程资料：（四）基本测量
分类：建筑/施工
时间：2025-06-07
标签：无
格式：PDF
价格：10 玖币
-
电力工程资料：（六）数据记录
分类：建筑/施工
时间：2025-06-07
标签：无
格式：PDF
价格：10 玖币
-
电力工程资料：（九）其他
分类：建筑/施工
时间：2025-06-07
标签：无
格式：PDF
价格：10 玖币
-
电力工程资料：(完整word版)电力安全技术交底
分类：建筑/施工
时间：2025-06-07
标签：无
格式：DOCX
价格：10 玖币
渝公网安备50010702506394
