算法设计与分析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交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
【词汇变形总汇】2025高考词汇变形总汇 - 教师版VIP免费
2024-12-06 4 -
【超简37页】新课标高考英语考纲3500词汇VIP免费
2024-12-06 11 -
《高考英语3500词详解》（WORD版）VIP免费
2024-12-06 29 -
《高考英语3500词详解》VIP免费
2024-12-06 26 -
高中英语-[教师版]80天通关高考3500词汇VIP免费
2024-12-06 29 -
高中人教选修7课文逐句翻译VIP免费
2024-12-06 11 -
高中人教选修7课文原文及翻译VIP免费
2024-12-06 35 -
高中人教必修4课文逐句翻译VIP免费
2024-12-06 12 -
高中人教必修4课文原文及翻译VIP免费
2024-12-06 39 -
高考英语核心高频688词汇VIP免费
2024-12-06 27
分类：计算机
价格：5.9玖币
属性：155 页
大小：2.82MB
格式：PDF
时间：2025-01-13
作者详情
相关内容
-
安徽省部分地市2024-2025学年高一下学期开学考试生物学试题（含答案）
分类：中学教育
时间：2025-12-03
标签：无
格式：DOCX
价格：10 玖币
-
安徽省部分地市2024-2025学年高一下学期开学考试地理试题（含答案）
分类：中学教育
时间：2025-12-03
标签：无
格式：DOCX
价格：10 玖币
-
安徽省部分名校2025届高三12月联考化学试题
分类：中学教育
时间：2025-12-03
标签：无
格式：PDF
价格：10 玖币
-
安徽省部分地市2024-2025学年高一下学期开学考试 化学 PDF版含解析
分类：中学教育
时间：2025-12-03
标签：无
格式：PDF
价格：10 玖币
-
安徽省部分地市2024-2025学年高一下学期开学考试 化学 PDF版含解析
分类：中学教育
时间：2025-12-03
标签：无
格式：PDF
价格：10 玖币
渝公网安备50010702506394
