算法设计与分析 课件 1.4-NP完全理论_第1页
算法设计与分析 课件 1.4-NP完全理论_第2页
算法设计与分析 课件 1.4-NP完全理论_第3页
算法设计与分析 课件 1.4-NP完全理论_第4页
算法设计与分析 课件 1.4-NP完全理论_第5页
已阅读5页，还剩6页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析算法分析-NP完全理论信息工程大学国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版时间复杂度：O(nc)时间复杂度：O(2n)多项式指数易解问题：能在多项式时间内解决的问题难解问题：不存在多项式时间算法的问题问题分类：问题：都是判定问题判定问题是仅仅要求回答是或否的问题。计算问题：

给定一个整数集合，找到一个非空子集使得它的和为0（子集求和问题）。判定问题：

给定一个整数集合，是否存在一个非空子集使得它的和为0。计算问题：

找到一条从起点出发，经过图中每个顶点仅且一次又回到起点的回路，且该

回路上所花费的代价最小（TSP问题）。判定问题：是否存在一条回路，从起点出发，经过图中每个顶点仅且一次又回到起点，

且该回路上所花费的代价小于等于正整数k。P问题：

如果一个问题可以找到一个能在多项式的时间内解决它的算法，那么这个问题就属于P问题。

NP问题：NP问题不是非P类问题可以在多项式的时间里验证一个解的问题

可以在多项式的时间里猜出一个解的问题问题1：子集求和问题

集合s={-1,3,2,-5,6}，子集{3,2,-5}问题2：问某图中是否不存在Hamilton回路？问题1是NP问题问题2不是NP问题NP问题与P问题的关系：所有的P类问题都是NP问题：能多项式地解决一个问题，必然能多项式地验证一个问题的解。

是否所有的NP问题都是P类问题？究竟是否有P=NP？P=NP不成立：存在不可能有多项式级复杂度的算法的NP问题。NPC问题：NP-完全问题多项式时间归约：

考虑一个判定问题A，如果A的任意输入都可以在多项式时间内通过某个变换转化成判定问题B的输入，且问题B的计算结果与问题A的结果相同。一元一次方程一元二次方程Hamilton回路旅行售货员问题（TSP）1.如果问题B存在多项式时间可解的算法，那么问题A也存在多项式时间可解的算法。2.如果不存在求解A的多项式时间的算法，那么也不存在求解问题B的多项式时间算法。NPC问题：首先，它得是一个NP问题；其次，所有的NP问题都可以归约到它。证明：先证明它至少是一个NP问题；再证明其中一个已知的NPC问题能约化到它（由约化的传递性）。NP-Hard问题：它满足NPC问题定义的第二条但不一定要满足第一条。NPPNPCNP-Hard测试选择题：以下说法正确的有（）A：p问题属于NP问题

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论