算法设计与分析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交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
公司日常考勤制度VIP免费
2024-11-29 4 -
公司人事考勤制度VIP免费
2024-11-29 8 -
公司规章制度汇编VIP免费
2024-11-29 9 -
岗位绩效工资制度VIP免费
2024-11-29 10 -
保密制度汇编VIP免费
2024-11-29 10 -
《绩效管理制度》VIP免费
2024-11-29 11 -
《施工企业安全生产评价标准》JGJ／T-77—2010VIP免费
2024-12-14 173 -
《潮起：中国创新型企业的诞生》导读VIP免费
2024-12-14 59 -
岗位面试题库合集-通用面试题库-世界五百强面试题目及应答评点（全套50题）VIP免费
2024-12-15 67 -
(试行)建设项目工程总承包合同示范文本GF-2011-0216VIP免费
2025-01-13 123
分类：计算机
价格：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人下载
相关内容
-
49_2019年离职面谈技巧大全
分类：人力资源/企业管理
时间：2025-08-23
标签：无
格式：DOC
价格：10 玖币
-
48_员工离职交接单
分类：人力资源/企业管理
时间：2025-08-23
标签：无
格式：XLS
价格：10 玖币
-
47_员工离职交接表-模板
分类：人力资源/企业管理
时间：2025-08-23
标签：无
格式：DOC
价格：10 玖币
-
46_员工离职工作交接表
分类：人力资源/企业管理
时间：2025-08-23
标签：无
格式：DOC
价格：10 玖币
-
45_员工离职〈调动〉工作交接表
分类：人力资源/企业管理
时间：2025-08-23
标签：无
格式：DOC
价格：10 玖币
渝公网安备50010702506394
