算法设计与分析W9-NP完全理论
VIP免费
2025-01-13
1
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交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
Michael Moorcock - Elric 6 - StormbringerVIP免费
2024-12-08 6 -
Michael Crichton - PreyVIP免费
2024-12-08 11 -
Mercedes Lackey - WintermoonVIP免费
2024-12-08 8 -
Mercedes Lackey - SE 1- Born To RunVIP免费
2024-12-08 9 -
Mercedes Lackey - Heralds of Valdemar 1 - Arrows Of The QueeVIP免费
2024-12-08 10 -
Melville, Herman - TypeeVIP免费
2024-12-08 15 -
MaryJanice Davidson - [Betsy 5] - Undead and Unpopular (v1.0)VIP免费
2024-12-08 25 -
Marion Zimmer Bradley - Darkover - The Heirs of HammerfellVIP免费
2024-12-08 21 -
MacDonnell, J E - 096 - Execute!VIP免费
2024-12-08 15 -
Lovecraft, H P - The Dream Quest Of Unknown KadadthVIP免费
2024-12-08 24
分类：计算机
价格：5.9玖币
属性：155 页
大小：2.82MB
格式：PDF
时间：2025-01-13
作者详情
-
VP-STO Via-point-based Stochastic Trajectory Optimization for Reactive Robot Behavior Julius Jankowski12 Lara Bruderm uller3 Nick Hawes3and Sylvain Calinon125.9 玖币0人下载
-
WA VEFIT AN ITERATIVE AND NON-AUTOREGRESSIVE NEURAL VOCODER BASED ON FIXED-POINT ITERATION Yuma Koizumi1 Kohei Yatabe2 Heiga Zen1 Michiel Bacchiani15.9 玖币0人下载
相关内容
-
2015年6月英语四级真题答案及解析（卷二）
分类：外语学习
时间：2025-05-02
标签：无
格式：PDF
价格：5.8 玖币
-
2015年6月英语四级真题答案及解析（卷三）
分类：外语学习
时间：2025-05-02
标签：无
格式：PDF
价格：5.8 玖币
-
2016年12月六级（第二套）真题
分类：外语学习
时间：2025-05-02
标签：无
格式：PDF
价格：5.8 玖币
-
2016年12月六级（第三套）真题
分类：外语学习
时间：2025-05-02
标签：无
格式：PDF
价格：5.8 玖币
-
2016年12月六级（第一套）真题
分类：外语学习
时间：2025-05-02
标签：无
格式：PDF
价格：5.8 玖币
渝公网安备50010702506394
