数学建模组合优化问题和计算复杂性

第一章组合优化问题和计算复杂性§1.1组合优化问题与算法§1.2计算复杂性问题§1.3启发式算法§1.1组合优化问题与算法3271510426287ACBCDEF共有3!=6种可能得到分配矩阵：如何嫁娶，使获得的礼品最多？Example1婚姻问题(matchingproblem)女儿ABC追求者EDF3271510426287§1.1组合优化问题与算法婚姻问题的数学模型：3~1,01jijixij否个人个人嫁第如果第3131Maxijijijxcz3,2,11..31jxtsiij3,2,11.31ixjij设：§1.1组合优化问题与算法1.贪婪（Greedy)解一般不会产生最差解；2.在某些模型中,贪婪算法能得到最优解；3.可以使用穷举法，但是以时间为代价贪婪解的结果：28+5+1=34最优解的结果：27+4+26=57Note：最差解的结果：3+10+7=203271510426287EFGACBC§1.1组合优化问题与算法Example2背包问题（KP，KnapsackProblem）假设有人要出发旅行,他考虑要带7种物品（每件物品的重量与价值如表）现在假设他最多带35kg物品，问：该带哪几件物品总价值最大？物品重量)(kgaj价值jc1312241233943155159061326716112设：7~101jjxj否种物品如果带第jjjxczMax7135..71jjjxats共有27种可能§1.1组合优化问题与算法Example3旅行商问题（TSP,TravellingSalesmanProblem)一个商人要到n座城市去做生意，设两个城市i和j之间的距离为dij.如何选择一条道路使得商人每个城市走一遍后回到起点且所走路程最短TSP可分为：对称（dij=dji)和非对称(dij≠dji)距离两种共有（n-1)!种可能City1City2City5City4City3§1.1组合优化问题与算法jiijijxdmin设：TSP问题的数学模型：)1(~11..1nixtsnjij)2(~111njxniij)3(,2,1221,nsnssxsjiijjinjijixij~1,01否则个城市的边个城市到第表示回路通过第为了减少变量个数作用是什么共有多少变量？125n(n-1)§1.1组合优化问题与算法若|s|=n则由n个点构成的一个回路是可行方案。||1Sn因为由前面两个约束条件的限制，不可能由n-1个点构成回路而留一个点在外面。Note：条件(1)，(2)表示每个城市经过一次，但不能保证它可行，要求局部不构成圈，条件(3)就是为了约束这一点。为什么？nsnssxsjiij,2,1221,1SiSjijx§1.1组合优化问题与算法共同特点：可行方案是有限的——组合优化问题Definition1组合优化问题π是一个极小化（或极大化）的问题，它是由以下三部分组成：（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组合优化问题与算法组合优化的数学模型：Minf(x)s.t.g(x)≥0x∈D其中x为决策变量f(x)为目标函数g(x)为约束函数D为决策变量的定义域，D为有限集合。F={x|x∈D,g(x)≥0}——可行域所以，可由（D，F，f）定义一个组合优化问题。组合优化的描述方法：1°数学模型（规划模型）2°文字语言叙述§1.1组合优化问题与算法一类实际问题的数学模型的总称，如TSP、LPetc.（一个问题中总包含了若干个参数）对问题给定一组参数所得到的例子。一个科学的计算过程，指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述。算法是相对问题而言的，不单单是针对问题的某个实例。如果算法从前一步到后一步的运行是由当时状态唯一确定的如：单纯形法，表上作业法。遗传算法是随机性算法。问题：实例：算法：Note：确定性算法：§1.1组合优化问题与算法对于一个极小化（极大化）优化问题π，如果给定任意一个实例I，算法A总能找到一个可行解σ*∈S(I)。使得f(I,σ*)≤f(I,σ)（f(I,σ*)≥f(I,σ)）启发式算法（近似算法，在§1.3节中介绍）组合优化总存在最优算法，但它以时间为代价最优算法：返回§1.2计算复杂性问题在广泛的意义下，执行算法的效率是用执行算法所用的全部计算资源的多少来衡量(时间、空间),但通常用时间作为衡量标准，这就是计算(时间)复杂性问题.设有n个城市(有向图)则有(n-1)！种可能方案。以计算机1秒可以完成24个城市所有路径枚举为单位，则讨论TSP问题城市数2425262728293031计算时间1s24s10min4.3h4.9d136.5d10.8y325y§1.2计算复杂性问题一、如何计算时间1°与实例的输入规模有关，是输入规模的函数（输入规模指的是：一个问题的实例所有参数的二进制表示的长度的总和。可简化为决策变量的个数n，或者顶点的个数m.）f(n),g(m)etc.用初等运算——算术运算、比较、转移等指令的次数，来表示一个算法在假设的计算机上执行时所需的时间。相关因素:§1.2计算复杂性问题2°与实例的参数有关，如LP问题：maxz=c’xs.t.Ax≤bx≥0,c≤0,b≥0算法的时间复杂性是关于实例输入长度的函数，用来表示算法的时间需求。对于每一个可能的输入长度，它是该算法解此输入长度的最坏可能的实例所需的时间（基本运算步骤）。相关因素:Definition2§1.2计算复杂性问题研究计算复杂性问题主要是针对n很大的情形1°9n2与2n2——O(n2)2°f(n)=12n4-8n3+5n2+2n-80f(n)=O(n4)当n无限增大时，Lnn,nα(α0),an（a1）趋向于无穷大的速度如何？Note：问：§1.2计算复杂性问题二、如何评价算法的好坏（从计算复杂性角度）复杂性分析的一个研究方向：对算法进行评价给定n个整数x1，x2，……xn，要求将他们从小到大重新排列取出x1，x2，…xn中的最小者（需比较n-1次）令其为b1（需n赋值次），从x1，x2，…xn中去掉b1，在余下的n-1个数中选出最小者，令其为b2，…直到得到b1,b2,……bn，易知其算法共做了n(n-1)/2次比较，至多n(n+1)/2次赋值，计算复杂性为，O(n2).Example4整序问题：比较交换法：§1.2计算复杂性问题先将两个单调不减的数列{u1，u2…um}与{v1，v2…vm}合并为一个单调不减的数列{w1，w2…w2m}方法为u1与v1比较,若u1≥v1，w1:=v1。再对u1与v2进行比较，依次对w2，w3…w2m赋值，计算量为O(m)。快速算法：将{x1，x2，……xn}从小到大重新排列（设：n=2p+1如果n不是2的幂次可补充若干个很大的数字使之成为2的幂次）。确定一个wj需要一次比较一次赋值，共需要（2m-1）次比较，2m次赋值。§1.2计算复杂性问题将2p+1个数分成2p个单调不减的2元组,计算量为O(2p)O(2p)=2p-1O(2)计算量为O（2p）综上，算法总工作量为：(p+1)*O(2p)=O(nlogn)81967532(81)(96)(75)(32)18695723(1869)(5723)1689235712356789将2元组两两合并成2p-1个单调不减的4元组，计算量为O(2p)依次类推，最后将两个2p元组合并成为一个单调不减的2p+1元组2p+1=n§1.2计算复杂性问题设机器速度100万次/秒快速算法O(nlogn)……需20秒设计算机速度为M次/秒问题D算法A……计算复杂性n2算法B……计算复杂性2n给定1秒的机器时间算法A………可解规模算法B………可解规模MM2logn=100万比较交换法O(n2)……需5.8天M=n2§1.2计算复杂性问题设机器速度100万次/秒给定1秒的机器时间算法A…………可解规模n=算法B…………可解规模n=MM2log给定1秒的机器时间算法A…………可解规模n=1000算法B…………可解规模n=20设机器速度提高100倍为1亿次/秒给定1秒的机器时间算法A……可解规模n=1000×10算法B……可解规模n=20+log2100Log21007提供好的算法比提高机器效率更重要§1.2计算复杂性问题Definition3设A是解某一问题D的算法，对D的任一规模为n的实例，可在n的多项式时间内求解（即计算复杂性为O（nα））,则称算法A为一个解问题D的多项式时间算法。（简称多项式算法）不能这样限制时间复杂性函数的算法称为指数时间算法。若存在一个常数C，使得对所有n≥1,都有︱f(n)︱≤C︱g(n)︱,则称函数f(n)是O(g(n))。多项式时间算法:指数时间算法:O(nlogn)、O(n2.8)、O(n2)O(n!)、O(3n)§1.2计算复杂性问题多项式时间算法好算法有效算法指数时间算法坏算法恶劣算法Note:A算法的计算复杂性为O(n80)，A是好算法吗？与O(2n)比较问题D是否有多项式时间算法是问题的固有性质.§1.2计算复杂性问题三、P类、NP类、NP—完全问题、NP—难问题复杂性分析的另一个研究方向：对组合优化问题归类对组合优化问题π，如果存在一个求解该问题的多项式时间算法，则称π是多项式时间可解问题。所有多项式时间可解问题构成的集合，称为P类问题记为P。π∈PP类问题:（Polynomial）§1.2计算复杂性问题如果一个问题π的输出（即答案）为YesorNo，则称问题π为判定问题。判定问题：Example5适定性问题（SATisfiability）已知一组逻辑变量的一个布尔表达式，其中每个逻辑变量的取值为1（真）或0（假）。问是否存在该组逻辑变量的取值，使得布尔表达式取值为真？)()()(323221xxxxxx§1.2计算复杂性问题Example6（TSP）已知完全图G上每一条边（vi,vj）的权wij，及常数h。问是否存在一个H-圈C，使得Example7（LP）给定常数z，是否有}0,,{xbAxzxcxT显然，判定问题不比原优化问题更难。可以证明两个问题在计算复杂性意义下是等价的。hwCvvijji),(§1.2计算复杂性问题NP类问题：（NondeterministicPolynomial）给定一个判定问题D，如果存在一个算法，对D的任何一个答案为“是”的实例，它给出的回答均可经多项式时间界的运算加以检验，则称D为一个NP问题。由全体NP问题构成的集合，称为NP类问题。记为NPSAT、TSP、LP∈NP§1.2计算复杂性问题P但是，多项式时间可验证性不能保证多项式时间可解性TSPNPP世界难题问：P=NP?可以这样说吗？显然不行！§1.2计算复杂性问题在对P=NP的研究中，?1972年加拿大数学家Cook提供了一个漂亮的理论，把前人的失败归结为一个深刻的数学猜想，提出了存在一类称之为NP–complete类的问题。Definition4设D1，D2为两个判定问题，若求解D2的算法A2可多项式次地调用求解D1的算法A1而实现，则称问题D2可以多项式时间归约为D1。简记：D2D1§1.2计算复杂性问题Theorem1D1∈P，则D2∈P。多项式的四则运算及复合，仍是多项式定理1说明如果D2D1，则D1不会比D2易解（在计算复杂性意义下）。Definition5一个判定问题Q被称为是NP-c问题，如果1、Q∈NP2、任何NP问题均可多项式时间归约为Q。如果D2D1，§1.2计算复杂性问题SAT∈NP-c这是Coo