《数学建模：组合优化问题和计算复杂性》由会员分享，可在线阅读，更多相关《数学建模：组合优化问题和计算复杂性（57页珍藏版）》请在金锄头文库上搜索。
1、第一章 组合优化问题和计算复杂性,1.1 组合优化问题与算法1.2 计算复杂性问题1.3 启发式算法,1.1 组合优化问题与算法,共有3!=6种可能,得到分配矩阵：,如何嫁娶， 使获得的礼品最多？,Example 1 婚姻问题(matching problem),3,27,1,5,10,4,26,28,7,1.1 组合优化问题与算法,婚姻问题的数学模型：,设 ：,1.1 组合优化问题与算法,贪婪（Greedy) 解一般不会产生最差解；,在某些模型中, 贪婪算法能得到最优解；,3. 可以使用穷举法，但是以时间为代价,贪婪解的结果： 28+5+1=34,最优解的结果：27+4+26=57,Note
2、：,1.1 组合优化问题与算法,Example 2 背包问题（KP，Knapsack Problem）,假设有人要出发旅行,他考虑要带7种物品（每件物品的重量与价值如 表）现在假设他最多带35 kg 物品， 问：该带哪几件物品总价值最大？,设：,共有27种可能,1.1 组合优化问题与算法,Example 3 旅行商问题（TSP,Travelling Salesman Problem),一个商人要到n 座城市去做生意， 设两个城市i 和j 之 间的距离为dij.如何 选择一条道路使得 商人每个城市走一 遍后回到起点且所 走路程最短,TSP可分为：对称（dij=dji) 和非对称(dij dji)
3、距离两种,共有（n-1)!种可能,1.1 组合优化问题与算法,设：,TSP问题的数学模型：,为了减少变量个数,作用是什么,共有多少变量？,n(n-1),1.1 组合优化问题与算法,若 |s|=n 则由n个点构成的一个回路是可行方案。,因为 由前面两个约束条件的限制，不可能 由 n-1个点构成回路而留一个点在外面。,Note：条件(1)，(2)表示每个城市经过一 次，但不能保证它可行，要求局部不构成 圈，条件(3)就是为了约束这一点。,为什么？,1.1 组合优化问题与算法,共同特点：可行方案是有限的组合优化问题,Definition 1 组合优化问题是一个极小化（或极大化） 的问题，它是由以下三
4、部分组成：,（1）实例集合 ；,（2）对每个实例 I，有一个有穷的可行解集合 S（I）,(3) 目标函数 f，它对于每个实例I和每个可行解 S（I），赋以一个有理数 f (I, ). 则实例I的最优解为这样一个可行解* S(I) ,它使得对于所有S（I），都有f (I, *) f (I, ) （f (I, *) f( I, )）。,1.1 组合优化问题与算法,组合优化的数学模型：,Min f(x) s.t. g(x) 0xD,其中x为决策变量,f(x)为目标函数,g(x)为约束函数,D为决策变量的定义域， D为有限集合。,F=x|x D, g(x) 0可行域,所以，可由（D，F，f ） 定义一
5、个组合优化问题。,组合优化的描述方法：,1数学模型（规划模型）,2文字语言叙述,1.1 组合优化问题与算法,一类实际问题的数学模型的总称，如TSP、LP etc.,（一个问题中总包含了若干个参数）对问题给定一组参数所得到的例子。,一个科学的计算过程，指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述。,算法是相对问题而言的，不单单是针对问题的某个实例。,如果算法从前一步到后一步的运行是由 当时状 态唯一确定的 如：单纯形法，表上作业法。,遗传算法是随机性算法。,问题：,实例：,算法：,Note：,确定性算法：,1.1 组合优化问题与算法,对于一个极小化（极大化）优化问题， 如果给
6、定任意一个实例I，算法A总能找到一个可 行解* S(I)。 使得 f(I, *) f(I, )（f(I, *) f(I, )）,启发式算法（近似算法，在1. 3节中介绍）,组合优化总存在最优算法，但它以时间为代价,最优算法：,返回,1.2 计算复杂性问题,在广泛的意义下，执行算法的效率是用执行算法所 用的全部计算资源的多少来衡量(时间、空间),但通常 用时间作为衡量标准，这就是计算(时间)复杂性问题.,设有n个城市(有向图)则有(n-1)！种可能方案。以计 算机1秒可以完成24个城市所有路径枚举为单位，则,讨论TSP问题,1s,24s,10min,4. 3h,4.9d,136.5d,10.8y
7、,325y,1.2 计算复杂性问题,一、如何计算时间,1 与实例的输入规模有关，是输入规模 的函数（输入规模指的是：一个问题的实例所有参数 的二进制表示的长度的总和。可简化为决策变量的个 数n，或者顶点的个数m .）f(n) , g(m) etc.,用初等运算算术运算、比较、转移等指令的次 数，来表示一个算法在假设的计算机上执行时所需的 时间。,相关因素:,1.2 计算复杂性问题,2 与实例的参数有关 ， 如LP 问题： max z=cxs.t. Axbx0, c 0 , b 0,算法的时间复杂性是关于实例输入长度 的函数，用来表示算法的时间需求。对于每一个可能 的输入长度，它是该算法解此输入
8、长度的最坏可能的 实例所需的时间（基本运算步骤）。,相关因素:,Definition 2,1.2 计算复杂性问题,研究计算复杂性问题主要是针对n很大的情形,1 9n2 与 2n2 O(n2),2 f(n) = 12n4 - 8n3 + 5n2 + 2n - 80,f(n) = O(n4),当n无限增大时，,Ln n , n( 0) , an （a 1）,趋向于无穷大的速度如何？,Note：,问：,1.2 计算复杂性问题,二、如何评价算法的好坏（从计算复杂性角度）,复杂性分析的一个研究方向：对算法进行评价,给定n个整数x1，x2，xn，要 求将他们从小到大重新排列,取出x1，x2，xn中的最小者
9、（需比较 n-1次）令其为b1（需n赋值次），从x1，x2，xn中去 掉b1，在余下的n-1个数中选出最小者，令其为b2， 直到得到b1,b2,bn，易知其算法共做了n(n-1)/2次比 较，至多n(n+1)/2次赋值，计算复杂性为，O(n2).,Example 4 整序问题：,比较交换法：,1.2 计算复杂性问题,先 将两个单调不减的数列u1，u2um与v1，v2vm 合并为一个单调不减的数列w1，w2w2m方法为u1与v1 比较,若u1 v1，w1 :=v1。再对u1与v2进行比较， 依次对 w2，w3w2m赋值，计算量为O(m)。,快速算法：,将 x1，x2，xn从小到大重新排列（设：n
10、=2p+1 如果n 不是2的幂次可补充若干个很大的数字使之成为2 的幂次）。,确定一个wj需要一次比较一次赋值，共需要（2m-1）次比较，2m次赋值。,1.2 计算复杂性问题,将2p+1个数分成2p个单调不减的2元组,计算量为O(2p),O(2p)= 2p-1 O(2),计算量为O（2p）,综上，算法总工作量为： (p+1) *O(2p)=O(n logn),8 1 9 6 7 5 3 2,(8 1)(9 6)(7 5)(3 2),1 8 6 9 5 7 2 3,(1 8 6 9) (5 7 2 3),1 6 8 9 2 3 5 7,1 2 3 5 6 7 8 9,将2元组两两合并成2p-1个
11、单调不减的4元组，计算量 为O(2p),依次类推，最后将两个2p元组合并成为一个单调不减 的2p+1元组,2 p+1= n,1.2 计算复杂性问题,设 机器速度100万次/秒,快速算法 O(n logn) 需20秒,设 计算机速度为 M 次/秒,问题 D,算法A计算复杂性 n2,算法B计算复杂性2n,给定1秒的机器时间,算法A可解规模,算法B可解规模,n = 100万,比较交换法O(n2) 需5.8天,M = n2,1.2 计算复杂性问题,设 机器速度100万次/秒,给定1秒的机器时间,算法A可解规模n =,算法B可解规模n =,给定1秒的 机器时间,算法A可解规模 n=1000,算法B可解规
12、模 n=20,设 机器速度提高100倍 为1亿次/秒,给定1秒的 机器时间,算法A可解规模n=100010,算法B可解规模 n=20+log2100,Log2100 7,提供好的算法比提高机器效率更重要,1.2 计算复杂性问题,Definition 3,设 A 是解某一问题 D的算法，对 D 的任一规模为 n 的实例，可在 n 的多项式时间内求解（即计算复杂性为 O（n）,则称算法 A 为一个解问题 D 的多项式时间算法。（简称多项式算法）,不能这样限制时间复杂性函数的算法称为指数时间算法。,若存在一个常数 C ，使得对所有 n 1, 都有f(n) C g(n),则称函数 f(n) 是 O(g
13、(n)。,多项式时间算法:,指数时间算法:,O(n logn)、O(n 2.8)、O(n 2),O(n!)、O(3n),1.2 计算复杂性问题,多项式时间算法,好算法 有效算法,指数时间算法,坏算法 恶劣算法,Note:,A 算法的计算复杂性为 O(n80)，A 是 好算法吗？,与O(2n) 比较,问题 D 是否有多项式时间算法是问题的固有性质.,1.2 计算复杂性问题,三、P类、NP类、NP完全问题、NP难问题,复杂性分析的另一个研究方向：对组合优化问题归类,对组合优化问题，如果存在一个求解该问题的 多项式时间算法，则称是多项式时间可解问题。所 有多项式时间可解问题构成的集合，称为 P 类问
14、题 记为 P。 P,P 类问题:,（Polynomial）,1.2 计算复杂性问题,如果一个问题的输出（即答案）为 Yesor No，则称问题为判定问题。,判定问题：,Example 5 适定性问题（SATisfiability）,已知一组逻辑变量的一个布尔表达式，其中每个逻 辑变量的取值为 1 （真）或 0 （假）。问是否存在该 组逻辑变量的取值，使得布尔表达式取值为真？,1.2 计算复杂性问题,Example 6 （TSP）已知完全图 G 上每一条边（vi,vj） 的权wij，及常数 h 。问是否存在一个 H-圈 C，使得,Example 7 （LP）给定常数 z ，是否有,显然，判定问题
15、不比原优化问题更难。可以 证明两个问题在计算复杂性意义下是等价的。,1.2 计算复杂性问题,NP 类问题 ：（Nondeterministic Polynomial）,给定一个判定问题 D ，如果存在一个算法，对 D 的任何一个答案为“是”的实例，它给出的回答均可经 多项式时间界的运算加以检验，则称 D 为一个 NP 问题。,由全体 NP 问题构成的集合，称为 NP 类问题。 记为 NP,SAT、,TSP、,LP, NP,1.2 计算复杂性问题,P,但是，多项式时间可验证性不能保证多项式时间可解性,TSP,NP,P,世界难题,问：,P = NP,?,可以这样说吗？,显然,不行！,1.2 计算复杂性问题,在对P = NP 的研究中，,?,1972年 加拿大数学家 Cook 提供了一个漂亮的理论，把前人的失败归 结为一个深刻的数学猜想，提出了存在一类称之 为 NP complete 类的问题。,Definition 4,设 D1，D2 为两个判定问题，若求 解 D2 的算法 A2 可多项式次地调用求解 D1的算法A1 而实现，则称问题 D2可以多项式时间归约为 D1。,
