算法设计与分析W9-NP完全理论

VIP免费

2025-01-13 3 0 2.82MB 155 页 5.9玖币

侵权投诉

NP 完全理论

目前掌握的算法设计技术

分而治之

动态规划

贪心算法

有些问题还未找到高效的算法，如

p0-1

背包问题

旅行商问题

集合覆盖问题

顶点覆盖问题

p… ..

需要证明不存在有效的算法

背景介绍

如何证明一个问题有高效算法？

设计一个高效算法

如何证明一个问题没有高效算法？

难以证明

背景

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!

如何证明一个问题有高效算法？

设计一个高效算法

如何证明一个问题没有高效算法？

难以证明

背景

I couldn’t find a polynomial-time algorithm,

but neither could these other smart people!

What do you actually do ?

nNP

完全问题

是一类问题的集合

被认为是一类难解（

Intractable

）问题

只要一个

完全问题有高效算法，则所有

完全

问题都有高效算法

nNP

问题是否有“高效”算法仍是一个

未解决的问题（

Open problem

）

如何证明一个问题没有高效算法？

证明该问题是

难问题（

NP-hard

）

背景：

完全理论

主要内容

判定问题

判定问题与最优化问题

问题与多项式时间算法

nNP

问题与多项式时间验证算法

nNP

完全问题与多项式时间归约

nNP

完全问题证明

•3-CNF

可满足性问题（

3SAT

）

•

团问题（

DCLIQUE

）

•

顶点覆盖问题（

DVC

）

•

独立集问题（

DIS

）

•

集合覆盖问题（

）

•

子集和问题（

）

•

带有开放时间和截止时间的调度问题

(SRD)

•

有向哈密顿回路问题（

DHC

）

•

哈密顿回路问题

(HC)

•

旅行商问题

(DTSP)

主要内容

判定问题与最优化问题

P问题与多项式时间算法

NP问题与多项式时间验证算法

NP完全问题与多项式时间归约

NP完全问题证明

判定问题：

仅有两种答案：“是”或“否”

（

yes or no, 1

或

）

判定问题（

Decision problems

）

例：判断一个连通无向图是否为一棵树。

输入：连通无向图

问题：

是否是一棵树？

实例

𝑮𝟏

是一棵树

实例

𝑮𝟐

不是一棵树

判定问题：

仅有两种答案：“是”或“否”

（

yes or no, 1

或

）

判定问题（

Decision problems

）

实例

𝑮𝟏

是一棵树

实例

𝑮𝟐

不是一棵树

例：判断一个连通无向图是否为一棵树。

输入：连通无向图

问题：

是否是一棵树？

判定问题：

仅有两种答案：“是”或“否”

（

yes or no, 1

或

）

判定问题（

Decision problems

）

实例

𝑮𝟏

是一棵树

实例

𝑮𝟐

不是一棵树

例：判断一个连通无向图是否为一棵树。

输入：连通无向图

问题：

是否是一棵树？

实例分为两类：

是树的所有连通无向图

不是树的所有连通无向图

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

5.9 玖币 0人已下载

立即下载 VIP免费下载

摘要：

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...

展开>> 收起<<

算法设计与分析W9-NP完全理论.pdf

共155页,预览31页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

算法设计与分析W9-NP完全理论

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: