当前位置：文档之家 › 算法设计与分析P-NP(2014)

算法设计与分析P-NP(2014)

  • 格式：ppt
  • 大小：252.50 KB
  • 文档页数：50

下载文档原格式

  / 50

合集下载

算法设计与分析实验指导2014版

算法设计与分析实验指导2014版

算法分析设计与实验王 源二0一四年十月实验一：分治算法及其应用实验要求：掌握分治算法的原理.掌握递归算法及递归程序的设计.能用程序设计语言设计求解典型问题的算法实验题：1、棋盘覆盖问题：在一个2k ×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。

用图示的4种不同形态的L 型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L 型骨牌不得重叠覆盖。

2、最近对问题：设p 1=(x 1,y 1), p 2=(x 2,y 2), …, p n =(x 1,y 1)，是平面上n 个点构成的集合S ，最近对问题就是找出集合S 中距离最近的点对。

3、（选作）最大子段和问题：给定由n 个整数（可能有负整数）组成的序列(a 1, a 2, …, a n )，最大子段和问题要求该序列形如 的最大值（1≤i ≤j ≤n ），当序列中所有整数均为负整数时，其最大子段和为0。

例如，序列(-20, 11, -4, 13, -5, -2)的最大子段和为 。

∑=ji k k a ∑==4220k k a实验要求：基本动态规划法的原理方法；能用程序设计语言实现求解背包问题的算法实验题：1、最长公共子序列问题：对给定序列X=(x1, x2,…, xm)和序列Z=(z1, z2,…, zk)，Z是X的子序列当且仅当存在一个递增下标序列(i1, i2,…, ik)，使得对于所有j=1, 2, …, k，有（1≤ij ≤m）。

给定两个序列X和Y，当序列Z既是X的子序列又是Y的子序列时，称Z是序列X 和Y的公共子序列最长公共子序列问题就是在序列X和Y中查找最长的公共子序列。

2、（选作）多段图的最短路径问题：设图G=(V, E)是一个带权有向图，如果把顶点集合V 划分成k个互不相交的子集Vi (2≤k≤n, 1≤i≤k)，使得E中的任何一条边(u, v)，必有u∈Vi，v∈Vi+m (1≤i≤k, 1＜i+m≤k)，则称图G为多段图，称s∈V1为源点，t∈Vk为终点。

算法设计与分析课件

算法设计与分析课件
2
ACM国际大学生程序设计竞赛
ACM国际大学生程序设计竞赛（英文 全称：ACM International Collegiate Programming Contest（ACM-ICPC或 ICPC）是由美国计算机协会（ACM）主办 的，一项旨在展示大学生创新能力、团队 精神和在压力下编写程序、分析和解决问 题能力的年度竞赛。经过30多年的发展， ACM国际大学生程序设计竞赛已经发展成 为最具影响力的大学生计算机竞赛。赛事 目前由IBM公司赞助。
主要内容介绍（续）
• • • • 第 7章 第 8章 第 9章 第10章 概率算法 NP完全性理论 近似算法 算法优化策略
1
相关先导基础课程和算法概述
专业基础课程： 数据结构、计算机语言(C++)、操作系统 如何编写计算机程序： • 数据结构+算法 = 程序 • 算法：计算机软件的“灵魂” 算法是计算机科学和计算机应用的核心
1.2 算法复杂性分析
Ω的定义：如果存在正的常数C和自然数N0，使得当NN0时 有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N)是它 的一个下界，记为f(N)=Ω (g(N))。即f(N)的阶不低于g(N)的阶。 θ的定义：定义f(N)= θ (g(N))当且仅当f(N)=O(g(N))且 f(N)= Ω (g(N))。此时称f(N)与g(N)同阶。 o的定义：对于任意给定的ε＞0，都存在正整数N0，使得 当NN0时有f(N)/Cg(N)ε,则称函数f(N)当N充分大时的阶比 g(N)低，记为f(N)=o(g(N))。 例如，4NlogN+7=o(3N2+4NlogN+7)。
调试：“调试只能指出有错误，而不能指出它们不存在 错误” 9 作时空分布图：验证分析结论，优化算法设计

算法设计与分析：第1章 算法分析基础

算法设计与分析：第1章 算法分析基础

算法测试
B 291Dprogram testingE
– ( ; – 2984&29F<*-/#
5D7 1?Ftest caseEF>, 29 < F 293;F@29: %0.'!
C +$DdebugE
– (A6=; –
) ;F
9)+*[,1'-FD!V6: 9)+*= #(!)
– =O!S UN#Q [ " 66Q 59
B59[MI!)59X6 Q596
!3[489+*
!3[ >G(
!3X
算法的执行时间绝大部分花在循环 和递归上
• B61( ,*=
#!7 @H
• 42 7&1
– -3%9 !#."; ,
– )
< +:!#;42>$7 &1>* +:7 &1
• ')(/
– % 0=')8(/ 6(/
1.3.3 算法复杂度
时间复杂度（ time complexity ）
• • #
课程介绍
n )*
– #/) –
!.3(- 31:
n )*$,
6&"%9 – 57"%20(+ – 57"9'
n4
— 8
主要内容
1. 算法的基本概念和常见符号 2. 算法设计的常用技术
• 递归法、蛮力法、分治法、减治法 • 贪心法、动态规划、回溯法、分支限界法 • 概率算法、近似算法、计算复杂性理论 3. 算法的评价：复杂度分析
引言
1.1 算法概述

《算法设计与分析》课件

《算法设计与分析》课件

常见的贪心算法包括最小生成树算法 、Prim算法、Dijkstra算法和拓扑排 序等。
贪心算法的时间复杂度和空间复杂度 通常都比较优秀，但在某些情况下可 能需要额外的空间来保存状态。
动态规划
常见的动态规划算法包括斐波那契数列、背包 问题、最长公共子序列和矩阵链乘法等。
动态规划的时间复杂度和空间复杂度通常较高，但通 过优化状态转移方程和状态空间可以显著提高效率。
动态规划算法的时间和空间复杂度分析
动态规划算法的时间复杂度通常为O(n^2)，空间复杂度为O(n)。
04 经典问题与算法实现
排序问题
冒泡排序
通过重复地遍历待排序序列，比较相邻元素的大小，交换 位置，使得较大的元素逐渐往后移动，最终达到排序的目 的。
快速排序
采用分治策略，选取一个基准元素，将比基准元素小的元 素移到其左边，比基准元素大的元素移到其右边，然后对 左右两边的子序列递归进行此操作。
动态规划是一种通过将原问题分解为若干个子 问题，并从子问题的最优解推导出原问题的最 优解的算法设计方法。
动态规划的关键在于状态转移方程的建立和状态 空间的优化，以减少不必要的重复计算。
回溯算法
01
回溯算法是一种通过穷举所有可能情况来求解问题的算法设计方法。
02
常见的回溯算法包括排列组合、八皇后问题和图的着色问题等。
空间换时间 分治策略 贪心算法 动态规划
通过增加存储空间来减少计算时间，例如使用哈希表解决查找 问题。
将问题分解为若干个子问题，递归地解决子问题，最终合并子 问题的解以得到原问题的解。
在每一步选择中都采取当前状态下最好或最优（即最有利）的 选择，从而希望导致结果是最好或最优的。
通过将问题分解为相互重叠的子问题，并保存子问题的解，避 免重复计算，提高算法效率。

《算法设计与分析》(全)

《算法设计与分析》(全)
巢湖学院计算机科学与技术系
1.1、算法与程序
程序：是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)。 例如操作系统，是一个在无限循环中执行的程序， 因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个 问题由操作系统中的一个子程序通过特定的算法来实 现。该子程序得到输出结果后便终止。
渐近分析记号的若干性质
（1）传递性： ➢ f(n)= (g(n))， g(n)= (h(n)) f(n)= (h(n))； ➢ f(n)= O(g(n))， g(n)= O (h(n)) f(n)= O (h(n))； ➢ f(n)= (g(n))， g(n)= (h(n)) f(n)= (h(n))； ➢ f(n)= o(g(n))， g(n)= o(h(n)) f(n)= o(h(n))； ➢ f(n)= (g(n))， g(n)= (h(n)) f(n)= (h(n))； （2）反身性： ➢ f(n)= (f(n))；f(n)= O(f(n))；f(n)= (f(n)). （3）对称性： ➢ f(n)= (g(n)) g(n)= (f(n)) . （4）互对称性： ➢ f(n)= O(g(n)) g(n)= (f(n)) ； ➢ f(n)= o(g(n)) g(n)= (f(n)) ；
巢湖学院计算机科学与技术系
渐近分析记号的若干性质
规则O(f(n))+O(g(n)) = O(max{f(n),g(n)}) 的证明： ➢ 对于任意f1(n) O(f(n)) ，存在正常数c1和自然数n1，使得对
所有n n1，有f1(n) c1f(n) 。 ➢ 类似地，对于任意g1(n) O(g(n)) ，存在正常数c2和自然数
巢湖学院计算机科学与技术系
第1章 算法引论

算法分析与设计-第10章

算法分析与设计-第10章
南京邮电大学计算机学院 2015-6-25
易处理问题和难处理问题(续) 一般认为，只有得到了一个多项式时间算 法，才被视为“很好地解决了”该问题。 如果一个问题困难到不可能在多项式时间 内求解，那么就认为该问题是“难解的”。 令人遗憾的是，对于这类难解问题，一直 未找到它们的多项式时间算法。
南京邮电大学计算机学院 2015-6-25
1 2 4 5 3
S={1,2}，k=S=2 S={3,4,5}，k=S=3 S={1,2,3,4}，k=S=4 是最大集团
南京邮电大学计算机学院 2015-6-25
最大集团及其判定问题
例10-3 无向图G=(V,E)的一个完全子图称为 该图的一个集团(clique)。集团的规模用集团 的顶点数衡量。 最大集团问题是确定图 G 的最大集团规模 的问题。 最大集团判定问题(G,k)是对给定正整数k， 判定图G是否存在一个规模至少为k的集团。
南京邮电大学计算机学院 2015-6-25
【程序10-3】最大集团判定问题不确定算法 void Clique(int g[][mSize],int n,int k) { S=; for(int i=0; i< k; i++) //选择k个顶点 { int t=Choice(0,n-1); //任选一个顶点t if (tS) Failure(); //若t已在S中，则失败终止 S=S∪{t}; } //验证此k个顶点是否形成完全子图 for(对所有(i,j), iS, jS且ij) if((i,j)E) Failure(); //若(i,j)E, 则表明S不是 Success(); //图G的集团 } O(n2)
算法设计与分析
Design Analysis and of Algorithms In C++

算法设计与分析课件--NP完全性理论-P类和NP类问题

➢ 若用邻接矩阵C表示图G，使用二进制串表示C和k，则
团问题的一个实例可以用长度为n2 + log k + 1 的二
进位串表示。
➢ 无向图的团问题可表示为语言：
• CLIQUE = {w#v|w,v∈{0,1}*，以w为邻接矩阵的图G有一个k 顶点的团。其中，w是C的二进制表示，v是k的二进制表示。}
• STEP3：确定性地检查V’的团性质。若V’是一个团则接受输入，
否则拒绝输入。时间复杂度为O(n 4 ) 。 • 因此，整个算法的时间复杂性为：O(n 4 ) 。
❖非确定性算法在多项式时间内接受语言CLIQUE，故CLIQUE∈NP。
16
8.2 P类问题和NP类问题
◼ P类问题和NP类问题的关系：
算法设计与分析
1
第八章 NP完全性理论
目录
8.1 易解问题和难解问题
8.2 P类问题和NP类问题
8.3
NP完全问题
8.4 NP完全问题的近似算法
2
8.1 易解问题和难解问题
◼ 常见的几类算法复杂性：
➢ O(1)：常数阶； ➢ O(log2n), O(nlog2n)：对数阶； ➢ O(n), O(n2), O(n3), …, O(nk): 多项式阶。多项式时间算法； ➢ O(2n), O(n!), O(nn)：指数阶。指数时间算法。
12
8.2 P类问题和NP类问题
◼ NP(Non-deterministic Polynomial)类问题：
➢ 如对于某个判定问题，存在一个非负整数k，对于输入规模为n的实 例，能以O(nk)的时间运行一个非确定性算法得到是或否的答案。 • 能用非确定算法在多项式时间内求解的判定问题。如哈密尔顿回 路问题。 • NP类问题是难解问题的一个子类。 • NP类问题并不要求给出一个算法来求解问题本身，而只要求给 出一个确定性算法在多项式时间验证它。

算法设计与分析王红梅NP完全理论PPT课件

❖ 关键——存在一个确定性算法，能够以多项式时间来检 查和验证猜测阶段所产生的答案。 例： NP类问题——Hamilton问题
汉诺塔问题不是NP类问题
第14页/共33页
P类问题和NP类问题的主要差别： ✓ P类问题可以用多项式时间的确定性算法来 进行判定或求解； ✓ NP类问题可以用多项式时间的非确定性算法 来进行判定或求解。
通常将存在多项式时间算法的问题看作是易解问题 （Easy Problem），将需要指数时间算法解决的问题 看作是难解问题（Hard Problem）。
例：易解问题——排序问题、查找问题、欧拉回路 难解问题——TSP问题、 Hanio问题、Hamilton回路
第7页/共33页
为什么把多项式时间复杂性作为易解问题和 难解问题的分界线？
第3页/共33页
例：对三个数进行排序的判定树
是
a1<a2
否
是
a2<a3
否
是
a1<a3
否
a1<a2<a3
a1<a
是
3
a2<a1<a3 否
a2<a
是
3
否
a1<a3<a2
a3<a1<2
a2<a3<a1
a3<a2<a1
第4页/共33页
2.1.3 最优算法
所谓最优算法（Optimality Algorithm）是 指在某一种度量标准下，优于该问题的所有 （可能的）算法。
第24页/共33页
定义2.7 令Π是一个判定问题，如果对于NP类 问题中的每一个问题Π'，都有Π'∝pΠ，则称判定 问题Π是一个NP难问题。

算法设计与分析课件--NP完全性理论-NP完全问题及近似算法

算法设计与分析
1
第八章 NP完全性理论
目录
8.1 异解问题和难解问题
8.2 P类问题和NP类问题
8.3
NP完全问题
8.4 NP完全问题的近似算法
2
8.3 NP完全问题
问题变换：
➢ NP类问题在最坏情况下的时间复杂性一般都是快速增长的指数函 数。希望能够在NP类问题内部找到一种方法，比较两个问题的计 算复杂性。
❖该近似算法的相对误差定义为=
cc* c*
。若对问题的输
入规模n，有一函数ε(n)使得 c c* ≤ε(n)，则称ε(n)
c*
为该近似算法的相对误差界。
13
8.4 NP完全问题的近似算法
NPC问题的近似算法示例 - TSP：
➢ 给定一个完全无向图G=(V,E)，其每一条边(u,v)∈E有一非 负整数费用c(u,v)。要找出G的最小费用哈密顿回路。如果 TSP满足三角不等式性质，即对于任意3个顶点u,v,w∈V有 ：c(u,w)≤c(u,v)+c(v,w)，则称该TSP为欧几里得TSP，否 则称为一般TSP。
12
8.4 NP完全问题的近似算法
NPC问题的近似算法的性能：
❖若一个最优化问题的最优值为c*，求解该问题的一个近 似算法求得近似最优解相应的目标函数值为c，则将该近 似近≤似算ρ比法(是n的)问。近题ρ似输(比n入)定为规义1模时为n，的求=一m得a个x的c函c*近, c数c*似 ρ。解(在为n)通最，常优即情解m况a。x 下cc* ,，cc*该
➢ 传递性：设P1、P2和P3是3个判定问题。若P1∝τ(n)P2，且P2∝τ(n)P3 ，则P1∝τ(n)P3。
4
8.3 NP完全问题
多项式时间变换示例：

算法设计与分析什么是P问题、NP问题和NPC问题最新


意的方案也不会来骗我去选它。这就是NP问题。
精心整理
9
NP问题
当然有不是NP问题的问题，即你猜到了解但 是没用，因为你不能在多项式的时间里去验 证它。
一个经典的例子，它指出了一个目前还没有 办法在多项式的时间里验证一个解的问题。
很显然，前面所说的Hamilton回路是NP问题， 因为验证一条路是否恰好经过了每一个顶点非常 容易。
一种是O(1),O(log(n)),O(n^a) 等，我们把它叫做 多项式级的复杂度，因为它的规模n出现在底数的位置；
另一种是O(a^n)和O(n!)型复杂度，它是非多项式级 的，其复杂度计算机往往不能承受。
当我们在解决一个问题时，我们选择的算法通常都 需要是多项式级的复杂度，非多项式级的复杂度需 要的时间太多，往往会超时，除非是数据规模非常 小。
逻辑电路问题
逻辑电路问题属于NPC问题。这是有严格 证明的。它显然属于NP问题，并且可以直 接证明所有的NP问题都可以约化到它。
证明过程相当复杂，其大概意思是说任意一 个NP问题的输入和输出都可以转换成逻辑 电路的输入和输出（想想计算机内部也不过 是一些 0和1的运算），因此对于一个NP问 题来说，问题转化为了求出满足结果为True 的一个输入（即一个可行解）。
目前为止这个问题还“啃不动”。但是，一 个总的趋势、一个大方向是有的。人们普遍 认为，P=NP不成立，也就是说，多数人相 信，存在至少一个不可能有多项式级复杂度 的算法的NP问题。
精心整理
12
NPC问题
人们如此坚信P≠NP是有原因的，就是在研 究NP问题的过程中找出了一类非常特殊的 NP问题叫做NP-完全问题，也即所谓的 NPC问题。C是英文单词“完全”的第一个 字母。正是NPC问题的存在，使人们相信 P≠NP。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
polynomial time algorithm does not exist for problem A or we are not smart.

Open problem: PNP? $1 million prize.
6
相关概念: P,NP,NPC,NP-hard
P: 能在多项式时间内解决的问题 NP: 不能在多项式时间内解决或不确定能不能在多项式 时间内解决，但能在多项式时间验证的问题 NPC: NP完全问题，所有NP问题在多项式时间内都能约 化(Reducibility)到它的NP问题，即解决了此NPC问题，所有 NP问题也都得到解决。 NP hard:NP难问题，所有NP问题在多项式时间内都能约 化(Reducibility)到它的问题(不一定是NP问题)。
NP-complete: A subset of NP that seems to be hardest to solve. The most-likely relationship of the three problem classes
5
Class P and Class NP
Based on definitions, PNP. If we can design a polynomial time algorithm for problem A, then problem A is in P. However, if we have not been able to design a polynomial time algorithm for problem A, then there are two possibilities:
Question: Do there exist polynomial time algorithms for those famous problems？
Answer: No body knows.
3
Story
Research topic: Prove that polynomial time algorithms do not exist for those famous problems, e.g., Hamilton circuit problem.
The first NPC problem is Satisfiability probelm
Proved by Cook in 1971 and obtains the Turing Award for this work
10
Boolean formula
A boolean formula f(x1, x2, …xn), where xi are boolean variables (either 0 or 1), contains boolean variables and boolean operations AND, OR and NOT .
Satisfiability problem
12
The First NP-complete Problem
Theorem: Satisfiability problem is NP-complete.
It is the first NP-complete problem. S. A. Cook in 1971 /wiki/Stephen_Cook Won Turing prize for his work.
To answer if PNP, a rich area, NP-completeness theory is developed.
4
Definitions (informally)


P: polynomial time solvable(( in O(nk) time)
NP:consists of those problem that are verifiable in
P and NP
1
NP-Co time vs exponential time（多项式时间和指数 时间)
Polynomial O(nk), where n is the input size (e.g., number of nodes in a graph, the length of strings , etc) of our problem and k is a constant (e.g., k=1, 2, 3, etc). Exponential time: 2n or nn. n= 2, 10, 20,
polynomial time.
What we mean here is that if we were somehow given a “solution”, then we can verify that the solution is correct in time polynomial in the input size to the problem. Example: Hamilton Circuit: given an order of the n distinct vertices (v1, v2, …, vn), we can test if (vi, v i+1) is an edge in G for i=1, 2, …, n-1 and (vn, v1) is an edge in G in time O(n) (polynomial in the input size).
Clause: variables and their negations are connected with OR operation, e.g., (x1 OR NOTx2 OR x5) Conjunctive normal form of boolean formula: contains m clauses connected with AND operation. Example: (x1 OR NOT x2) AND (x1 OR NOT x3 OR x6) AND (x2 OR x6) AND (NOT x3 OR x5). Here we have four clauses.
Significance:
If Satisfiability problem can be solved in polynomial time, then ALL problems in class NP can be solved in polynomial time. If you want to solve PNP, then you should work on NPC problems such as satisfiability problem. We can use the first NPC problem, Satisfiability problem, to show that other problems are also NPcomplete.
The formula is true for assignment x1=1, x2=0, x3=1.
Note: for n Boolean variables, there are 2n assignments. Testing if formula=1 can be done in polynomial time for any given assignment.Given an assignment that satisfies formula=1 is hard.


Can arbitrary instances of problem Y be solved using polynomial number of standard computational steps, plus a polynomial number of calls to a black box that solves problem X? If yes, then Y is polynomial-time reducible to X.
Story
All algorithms we have studied so far are polynomial time algorithms (unless specified).
Facts: people have not yet found any polynomial time algorithms for some famous problems, (e.g., Hamilton Circuit, longest simple path, Steiner trees).
You can get Turing award if you can give the proof.
In order to answer the above question, people define two classes of problems, P class and NP class.
Suppose we have a black box (an algorithm) that could solve instances of a problem X; If we give the input of an instance of X, then in a single step, the black box will return the correct answer. Question:
Y p X
9
NP-Complete(NPC)
A problem X is NP-complete if it is in NP and any problem Y in NP has a polynomial time reduction to X.
it is the hardest problem in NP If an NP-complete problem can be solved in polynomial time, then any problem in class NP can be solved in polynomial time.