《高级算法设计》课件全套 林海 第1-7章 线性规划-启发式算法

高级算法设计与分析线性规划基本概念基本概念基本概念线性规划的形式：线性规划：定义标准型和松弛型标准型和松弛型非标准型目标函数不是最大化，而是最小化约束条件是大于等于约束约束条件是等式约束;存在一些变量没有非负约束标准型和松弛型非标准型例子标准型和松弛型标准型和松弛型标准型和松弛型标准型：标准型和松弛型松弛型：在松弛型中，等式左边的变量x4,x5,x6被称为基本变量，等式右边的变量x1,x2,x3被称为非基本变量矩阵形式：标准型和松弛型图解法将可行域为：ABCDEF的边界和内部，A,

B,

C,

D,

E,

F称为极点图解法单纯形法如果我们能够将上述目标函数的所有变量的系数全部转换为负数单纯形法步骤松弛基本解为(x1,x2,x3,x4,x5,x6)=(0,0,13,10,5,2)单纯形法步骤基本解为(x1,x2,x3,x4,x5,x6)=(0,0,13,10,5,2)在此基本解下，目标函数的值为0通过增大x1或x2来使目标函数变大单纯形法步骤目标函数中x1的系数大于x2，选择增大x1约束条件4的约束最紧凑单纯形法步骤约束条件4变为用这个表达式替换目标函数和其他约束条件中的x1

单纯形法步骤目标函数的值为16单纯形法步骤用这个表达式替换目标函数和其他约束条件中的x2

单纯形法步骤单纯形表注意表格中的值是变量系数的值（取负），目标函数变量的系数同样取负单纯形表1.从目标函数中选择一个需要变大的变量（系数最小）x12.找出最紧凑约束最紧凑约束是b/(x1系数)最小的约束（第4行约束）3.x1变量替入为基变量，而原来的基变量x6替出为非基变量单纯形表1.从目标函数中选择一个需要变大的变量（系数最小）x12.找出最紧凑约束最紧凑约束是b/(x1系数)最小的约束（第4行约束）3.x1变量替入为基变量，而原来的基变量x6替出为非基变量单纯形表4.用x1的表达式替换目标函数和其他约束条件中的x1

高斯消元单纯形表4.用x1的表达式替换目标函数和其他约束条件中的x1

高斯消元重复上述步骤单纯形表重复上述步骤最紧凑约束为第一行约束，对第一行进行替入和替出操作单纯形表重复上述步骤用第一行约束对所有其他约束行和目标函数行进行x2高斯消元对偶对偶性是线性规划最重要的内容之一每个线性规划（LP1）必然有与之相伴而生的另一个线性规划问题（LP2），即任何一个求maxz的LP1都有一个求minw的LP2对偶对偶矩阵形式对偶例子对偶对偶规则（标准型）原问题的目标函数是最大化，对偶问题的目标函数是最小化，原问题的约束条件是小于等于，对偶问题的约束条件是大于等于原问题约束条件的个数(m)决定对偶问题变量的个数，且第一个约束条件对应第一个变量，第二个约束条件对应第二个变量，以此类推对偶对偶规则（标准型）原问题变量的个数(n)决定对偶问题约束条件的个数，且第一个变量对应第一个约束条件，第二个变量对应第二个约束条件，以此类推对偶问题的目标函数中每个变量的系数由其对应原问题中约束条件b值决定对偶问题约束条件的c值是其对应变量(原问题)在目标函数的系数，约束条件中各变量的系数是其对应变量(原问题)在约束条件中的系数对偶对偶：例子对偶：例子对偶是怎么来的设线性规划的原始问题：转化为优化问题的标准形式对偶是怎么来的对偶是怎么来的对偶是怎么来的对偶问题可以化为对偶是怎么来的如果对原问题按照“原问题和对偶问题的转换”表可得：等价对偶例子：矩阵博弈矩阵博弈：猜硬币，两个参与者分别同时从两个硬币(一元和两元)中选取一个让对方猜，如果都猜错或都猜对，继续玩，如果只有一方猜对，则猜对一方赢得此次双方的所有硬币对偶例子：矩阵博弈矩阵博弈：猜硬币，收益矩阵如下：行和列表示（player1和player2）的策略（选取的硬币和猜对方的硬币），如（1，2）表示选取硬币1元，猜对方选取的是2元；矩阵的值表示列player2的收益

对偶例子：矩阵博弈对偶例子：矩阵博弈对偶例子：矩阵博弈对偶例子：矩阵博弈对偶例子：矩阵博弈对偶例子：矩阵博弈即player2

LP问题C的对偶问题即为player1的LP问题R对偶性质线性规划标准式对偶性质可得：即：对偶性质：弱对偶性对偶性质：强对偶性和互补松驰性对偶性质：互补松驰性如果原问题和对偶问题得出的解满足互补松弛性，则为最优解互补松驰性例子互补松驰性例子原问题的对偶问题为互补松驰性例子互补松驰性例子原问题的对偶问题为互补松弛性可得互补松驰性例子整数规划当变量的取值从实数变为整数后，这个问题到底是变难了，还是变容易了?整数规划松弛整数规划：分支限界分支限界：例子对线性规划问题求解，得最优解为x1=2.5,x2=2.25，目标函数为21.5分支限界：例子此时，可以对x1进行分支，也可对x2进行分支。对x1进行分支，则分为x1≤2和x1≥3两部分。

分支限界：例子对左边分支(x1≤2)求解得x1=2,x2=2.5，目标函数为20对右边分支(x1≥3)求解得x1=3,x2=1.5，目标函数为21分支限界：例子接着搜索节点3，对x2进行分支，则分为x2≤1和x2≥2两部分分支限界：例子对左边分支(x2≤1)求解得x1=3.3,x2=1，目标函数为20.7而右边分支(x2≥2)无可行解。分支限界：例子接着搜索节点4，对x1进行分支，则分为x1≤3和x1≥4两部分分支限界：例子对左边分支(x1≤3)求解得x1=3,x2=1，目标函数为19，找到整数解，结束搜索而右边分支(x1≥4)无可行解分支限界：例子因为节点2的上限大于目前找到的最优值19，需要继续搜索，对x2进行分支，则分为x2≤2和x2≥3两部分分支限界：例子对左边分支(x2≤2)求解得x1=2,x2=2，目标函数为18而右边分支(x2≥3)无可行解最终的最优解为x1=3,x2=1，最优值为190-1整数规划整数规划的一个特列是0-1整数规划，也就是参数的取值只能是0或1。很多算法问题都可以建模成0-1整数规划问题，如0-1背包问题、任务分配、集合覆盖等问题。0-1整数规划：建模0-1背包问题中，设背包的承重为C，共n个物品，每个物品的重量和价值分别为wi和vi，则问题建模为0-1整数规划：建模在应用中，有时会遇到变量可以取多个整数值的问题。如果用0-1变量来表示，也可以用一组0-1变量来取代。

如x取0－9之间的任意整数时。

x=20x0+

21x1+

22x2+

23x3£90-1整数规划：建模含有相互排斥的约束条件的问题（1）两个约束中，只有一个起作用。例：a11x1+a12x2<B1a21x1+a22x2<B2

解：引入0-1变量Y1,Y2和足够大的正数M，则a11x1+a12x2<B1+M1Y1a21x1+a22x2<B2+M2Y2Y1+Y2=10-1整数规划：建模某企业生产产品的费用如下，建立0-1规划模型单耗量产品资源IIIIII资源量A248500B234300C123100单件可变费用456固定费用100150200单件售价810120-1整数规划：建模解：设Xj是第j种产品的产量。Yj是0－1变量，表示是（Yj=1）否（Yj=0）生产第j种产品。maxZ=4X1+5X2+6X3–100Y1

–150Y2

–200Y32X1+4X2+8X3£5002X1+3X2+4X3£300X1+2X2+3X3£100X1£

M1Y1X2£

M2Y2X3

£

M3

Y3X1,

X2,

X3³0整数Y1,Y2,Y3为0－1变量。

s.t.0-1整数规划：隐枚举法0-1整数规划：隐枚举法0-1整数规划：隐枚举法0-1整数规划：隐枚举法原始-对偶算法通过对偶问题来求解原问题的最优解或者近似解，统称为原始-对偶算法对于0-1整数规划问题，是很难通过互补松弛性来求得最优解，但我们依然可以通过原问题(Primal)和对偶问题(Dual)的弱对偶性来求得一个近似解原始-对偶算法原始-对偶算法原始-对偶算法原始-对偶算法的应用：顶点覆盖顶点覆盖问题是指从图中选取最少的顶点，这些顶点能够覆盖图中所有的边(一个顶点覆盖一条边，指这个顶点和这条边相连)。数学模型。设G=(V,E)，节点个数为n，边的条数为m，令xv

为0-1变量，0代表不选取顶点v，1代表选取顶点v，则顶点覆盖的0-1整数规划模型:原始-对偶算法的应用：顶点覆盖顶点覆盖问题是指从图中选取最少的顶点，这些顶点能够覆盖图中所有的边(一个顶点覆盖一条边，指这个顶点和这条边相连)。对偶：图的最大匹配问题原始-对偶算法的应用：顶点覆盖扩展顶点覆盖问题：给每个顶点都赋予一个权重wv(wv>0)，顶点覆盖问题转化为求顶点集合，使其能够覆盖所有的边且顶点集的总权重最小。线性模型对偶模型原始-对偶算法的应用：顶点覆盖原始-对偶算法来求解带权重顶点覆盖问题的近似最优解。原始-对偶算法的应用：顶点覆盖原始-对偶算法来求解带权重顶点覆盖问题的近似最优解。原始-对偶算法的应用：顶点覆盖原始-对偶算法的应用：顶点覆盖高级算法设计与分析高级图算法主要内容最大流最小割图的中心性算法社群发现算法流网络找到一个从s出发，到t的流量最大的流，这就是最大流问题网络的流网络的流需要满足的两个条件：网络的流如何找到最大流从流量为0开始，逐步增加流量，直到达到最大流量为止从s出发，找到一条到t的可行路径，并将流增加到这个路径能够支持的最大流量在剩余的流网络（残存网络）中再找一条可行的路径，增加相应的流重复以上步骤网络的流原始流网络找到一条路径残存网络？残存网络网络的流残存网络新的路径：新的流网络网络的流残存网络此时已无法在此残存网络中再找到一条从s到t的路径，前面的流为最大流Ford-Fulkerson算法Ford-Fulkerson算法Ford-Fulkerson算法的两个问题当在残存网络中无法再找出一条从s到t的路径时，那么得到的流一定是最大流吗？最大流最小割定理在残存网络中如何找到一条从s到t的路径？Edmonds-Karp算法最大流最小割定理最大流最小割定理最大流最小割定理最大流最小割定理最大流最小割定理设f是最大流，其所对应的残存网络Gf还存在一条从s到t的路径p，

在残存网络Gf

上可以找到一个流f′

最大流最小割定理最大流最小割定理结论1:也就是由最大流最小割陈述2得出的(S,T)割上，(S,T)的流量(从S到T的流量)等于(S,T)的容量最大流最小割定理(S′,T′)是任意s-t割,根据能量守恒来证明，即从源节点s来的流f等于从集合S流到T的流

结论2:是s−t流f等于任意(S′,T′)割最大流最小割定理(S′,T′)是任意s-t割结论3:

f小于等于任意(S′,T′)割的容量最大流最小割定理由结论1和结论2，可知s−t流f等于(S,T)割的容量，即f=C(S,T)结合结论3

，可知(S,T)割的容量小于等于任意割，即C(S,T)≤C(S′,T′)，即C(S,T)是最小割

最大流最小割定理Edmonds-Karp算法在残存网络中如何找到一条从s到t的路径?图的深度优先遍历方法？Edmonds-Karp算法最短路径算法Dijsktra算法(复杂度O(mlogn))广度优先搜索（O(m)）短路径为vs→v2→vt

或者vs→v3→vt，所以通过两次增广路径即可找到网络的最大流Edmonds-Karp算法：复杂度基于最短路径算法证明：设在残存网络G中找到流f，形成新的残存网络G’。从G到G’，增加了指向上一层级的边，并删除了指向下一层级的关键边增加的边并不会减少从s到其他节点的距离，但减少的边有可能会增加s到其他节点的距离，所以引理得证Edmonds-Karp算法：复杂度基于最短路径算法Edmonds-Karp算法：复杂度边ei→j再次成为关键边时，源节点到vi的距离至少增加了2跳Edmonds-Karp算法：复杂度可以得出边ei→j最多(n−2)/2次成为关键边总的关键边的次数为O(m∗(n−2)/2)=O(mn)Edmonds-Karp算法最大容量路径也为vs→v2→vt

或者vs→v3→vt，所以也通过两次增广路径即可找到网络的最大流最大容量路径算法Dijsktra算法

Edmonds-Karp算法

Dijkstra算法，对路径的边求最小容量，并最大化之，Edmonds-Karp算法Edmonds-Karp算法流量分解证明Edmonds-Karp算法流量分解证明由流量守恒，可得：在每次容量更新中，路径中最小容量的边(至少一条)的容量会被置0，因图G边的条数是mEdmonds-Karp算法流量分解定理说明了最大流fopt

可以被分解为最多m个路径流{f1,f2,···,fm}，在这些路径流中，必然存在一个流fk≥fopt/m,1≤k≤m，而此流所在路径上所有边的容量必然≥fopt/m。引理得证。Edmonds-Karp算法Edmonds-Karp算法如果原始图G的边数为m，则在任意的残存图Gt中，其边的条数不会超过2m，所以对任意残存图Gt，剩余最大流为

因为容量都为整型主要内容最大流最小割图的中心性算法社群发现算法图的中心性算法度中心性(DegreeCentrality):一个点与其他点直接连接的程度紧密中心性(ClosenessCentrality):一个节点到所有其他节点的距离，一个拥有高紧密性中心性的节点拥有着到所有其他节点的距离较小;中介中心性(BetweennessCentrality):一个节点位于最短路径上的次数，如果有很多条最短路径经过此节点，说明此节点的中介中心性越高;特征向量中心性(EigenvectorCentrality):一个节点的重要性有时也取决于其邻居节点的重要性，与之相连的邻居节点越重要，则该节点特征向量中心性就越高;PageRank:PageRank也是考虑邻节点重要性的一种中心性算法，可看出是特征向量中心性的一种变体。度中心性度中心性是来衡量一个节点重要性相对简单的算法，其基于一个非常直接的观察，和越多其他节点连接的节点越重要紧密中心性紧密中心性用来衡量一个节点处于图的中心的程度，当一个节点越处于中心的位置，则其在图上散播信息的能力越强。为了适应图不是强连通图的情况，采用调和平均数紧密中心性前面的表述形式难以处理这种对几个子图进行连接的情形紧密中心性Dangalchev变体中介中心性在社交网络中，有时候并不是那些具有最多关注者的节点(度中心性)或者处于网络中心位置的节点(紧密中心性)是最重要的，而是那些起着关键桥梁或者中介作用的节点起着决定性的作用其中，σjk

是节点vj到节点vk

的最短路径的个数，σijk是节点vj到节点vk

且经过节点vi

的最短路径的个数中介中心性假设从节点vj

到vk

的最短路径在就要到达vk

前，可沿着不同的路径分别经由三个节点u1、u2、u3，也就是u1、u2、u3

是vk

在最短路径上的前一邻节点中介中心性中介中心性算法如何降低复杂度？快速中介中心性算法累积节点对依赖简单场景节点vs

到任意其他节点只存在一条最短路径，即σst=1,∀vt∈V

快速中介中心性算法累积节点对依赖：简单场景快速中介中心性算法快速中介中心性算法快速中介中心性算法快速中介中心性算法快速中介中心性算法累积节点对依赖：简单场景从前面的例子可以看出，累积节点对依赖(δ值)是个递归式，所以其计算类似于动态规划，也就是从最底层的值，这里是树中叶子节点的δ值(其值为0)开始计算，依次沿着树枝向跟节点计算快速中介中心性算法累积节点对依赖：一般场景在简单场景中，如果最短路径经过某个节点vj，则必然经过其父节点。但是在一般场景中，并不存在这样的关系，也就是最短路径经过节点vj，但并不一定经过其前一跳邻节点从vs

到vk

的最短路径数目共有σsk

个，从vs

到v1

的最短路径数目共有σs1

个。所以我们只需考虑σsk/σs1

比例的最短路径快速中介中心性算法累积节点对依赖：一般场景特征向量中心性在度中心性中，节点的重要程度只考虑了连接数，而没有考虑到连接节点的重要程度。在社交网络上，和一个有影响力的节点有连接关系，显然比和一个普通节点有连接关系，更能使提高自身的重要程度。特征向量中心性特征向量中心性图的邻接矩阵特征向量中心性第一次迭代特征向量中心性第二次迭代特征向量中心性第三次迭代特征向量中心性第四次迭代收敛时特征向量中心性从以上式子可知，特征向量中心性x是图的邻接矩阵A的特征值为λ时的特征向量，这就是为什么称之为特征向量中心性的原因特征向量中心性特征向量中心性发现节点3和节点5

的特征向量中心性是一致的，这个从图12.7很容易得到验证，这两个节点的邻节点是相似的，它们都连接了4节点，同时连接对方。此外，节点4具有最大的特征向量中心性，这个从图中也容易得出，节点4具有最多的邻节点，且其邻居具有较大的特征向量中心性值。PageRankPageRank是谷歌的网页排序算法，可以认为其特性向量中心性算法的一个变体：节点的重要性不仅仅取决于有多少个其他节点指向自己，同时也取决于那些指向自己的节点的重要性PageRankPageRankPageRankPageRankPageRank另得主要内容最大流最小割图的中心性算法社群发现算法社群发现社群发现基于模块度的算法基于标签传播的算法基于团的算法社群发现:基于模块度的算法模块度其中m是图边的条数;A为邻接矩阵，也就是说如vi和vj间存在边，Aij=1，否则，Aij=0;ki表示vi的度;Si表示vi所属的社群，Sj表示vj所属的社群，当Si=Sj时，δ(Si,Sj)=1，当Si̸=Sj时，δ(Si,Sj)=0。社群发现:基于模块度的算法模块度社群发现:基于模块度的算法模块度基于模块度的算法：例子基于模块度的算法合并方式将每个节点看成一个社群，之后逐步的合并社群，直到所有的节点成为一个社群或者直到合并再不能增加模块度为止分割方式将整个图看成一个的社群，之后逐步的分割社群，直到每个节点都成为一个社群或者直到分割再不能增加模块度为止Girvan-Newman算法基于分割方式，每次删除条边如何选择一条边？最多最短路径通过的边FastNewman算法基于合并方式Louvain算法基于合并方式：合并和粗化轮流进行，直到模块度不能再增加为止合并Louvain算法基于合并方式合并：当一个节点vi并入某个社群S时，只有社群S和节点vi所代表社群的模块度发生改变，其他社群没有变化Louvain算法基于合并方式Louvain算法基于合并方式Louvain算法：例子第3个图的模块度Louvain算法：例子第4个图的模块度基于标签传播的算法在基本标签传播算法LPA的初始化阶段，每个节点被赋予一个标签，一个简单的标签赋予方式是每个节点被赋予自身的标号。之后，每个节点从其邻节点中选择一个数目最多的标签作为自身的标签，当数目最多的标签具有多个时，则随机选择一个基于标签传播的算法：例子基于标签传播的算法：例子基于标签传播的算法重叠社群的标签传播算法：COPRA算法COPRA算法：例子COPRA算法：例子因α=1/Nc=1/2，节点a和节点g保留所有的二元组，其他节点因其二元组的从属系数都小于1/2，所以选择一个最大从属系数的二元组COPRA算法：例子社群发现:基于团的算法CPM(CliquePercolationMethod)算法CPM算法：例子CPM算法：例子CPM算法：例子对角线小于4的全部置为0，其他置为1，非对角线元素小于3的全部置为0，其他置为1CPM算法：例子可得c1没有和任何其他团连，所以独立成一个社群;c4和c5连通，c5和c6连通，所以这3个团是一个社群高级算法设计与分析NP问题主要内容基本概念、归约P问题的证明NPC问题的证明算法效率多项式时间算法O(nc)forsomeconstantc非多项式时间算法复杂度为O(n)的算法是高效率?复杂度为O(nlogn)?O(n2)?O(n10)?O(nlogn)?O(2n)?O(n!)?基本概念：P问题基本概念：NP问题基本概念：NPC问题基本概念：关系P问题，NP问题和NP完全问题的关系（认为，没有得到证实）基本概念：NPC问题判断是否NP问题也就是给出一个证书，可否在多项式时间内判断它是否是原问题的一个解最优化问题需要转化为判断性问题基本概念：NPC问题旅行商问题转化为：此图中是否存在总权重为1的回路?此图中是否存在总权重为2的回路?…此图中是否存在总权重为n的回路?一个优化问题可分解为多个判定性问题如果能够证明一个判定性问题为NP难时，显然原问题也是NP难的基本概念：归约性通俗的讲，一个问题(如Q1)可以规约为另外一个问题(如Q2)是指问题Q1可以转换为问题Q2，之后可以通过求解Q2的方法来求解Q1如:求解一元一次方程(问题Q1)可归为求解一元二次方程(问题Q2):一元二次方程的二次项系数为0即可，之后可以通过求解一元二次方程的方法来求解一元一次方程基本概念：归约基本概念：归约归约具有传递性如果问题A可归约为问题B，问题B可归约为问题C，则问题A一定可归约为问题C。基本概念：归约证明基本概念：归约性主要内容基本概念、归约P问题的证明NPC问题的证明P问题的证明2合取范式(CNF)的可满足性问题(SAT)P问题的证明2合取范式(CNF)到图的转换

P问题的证明2合取范式(CNF)到图的转换

P问题的证明2合取范式(CNF)到图的转换当且仅当2CNF中存在子句(x∨y)，图G中存在边¬x→y

(和边¬y→x)P问题的证明P问题的证明P问题的证明P问题的证明P问题的证明主要内容基本概念、归约P问题的证明NPC问题的证明NPC问题的证明第一个NPC问题电路可满足性问题问题：给定一个逻辑电路，问是否存在一种输入使输出为True其它的NPC问题都是由这个问题归约而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”。有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题归约到它就行了公式可满足性问题公式可满足性问题:公式可满足性问题公式可满足性证明这是一个NP问题公式可满足性问题公式可满足性证明归约证明：电路可满足性归约到公式可满足性显而易见，每个电路都可写成一个布尔公式也就是存在f，使得任何一个实例x属于电路，当且仅当f(x)属于公式但，直接写的话，因每个电路门输出线扇出为2或者2以上导致布尔公式的规模出现指数增长公式可满足性问题公式可满足性证明我们的目的不是将电路转换为布尔公式，而是证明可满足性，如果电路有可满足指派，则电路每个门输出都由其输入决定，写成表达式如右x7公式可满足性问题公式可满足性证明以上转换为多项式时间如果电路有可满足性实例，则电路输出为1，而公式输出也为1如果公式输出为1，则显然电路输出也为1公式可满足性为NPC问题3-CNF可满足性问题每个子句有3个文字3-CNF可满足性问题公式可满足性证明这是一个NP问题公式可满足性可以归约到3-CNF将布尔公式转换为子句的合取式将子句转换为合取范式将子句转为3个文字的合取取式3-CNF可满足性问题1.将布尔公式转换为子句的合取式建立布尔公式的语法树3-CNF可满足性问题1.将布尔公式转换为子句的合取式建立布尔公式的语法树将语法分析树看成电路，得出归约的布尔公式此布尔公式为合取式3-CNF可满足性问题2.将子句转换为合取范式构造每个子句的真值表3-CNF可满足性问题2.将子句转换为合取范式构造每个子句的真值表根据真值表中值为0的项，得出析取范式此析取范式等价于子句的否3-CNF可满足性问题2.将子句转换为合取范式构造每个子句的真值表根据真值表中值为0的项，得出析取范式此析取范式等价于子句的否运用德摩根定律，得出合取子句（将析取范式再取否）3-CNF可满足性问题3.将子句转为3个文字的合取取式3-CNF可满足性问题以上映射为多项式时间将布尔公式转换为子句的合取式同布尔电路转换为布尔公式将子句转换为合取范式每个子句至多变为8个子句（至多3个变量）将子句转为3个文字的合取取式至多引入4个子句由以上步骤可知：3-CNF是可满足的当且仅当以上三个步骤的每一步都是可满足的=》以上转换为归约团问题团问题团问题证明这是一个NP问题团问题3合取范式可以归约为团问题构造图一个子句对应一组顶点对于任意两个在不同组的顶点，如果满足“这两个顶点不是‘否’的关系”这一条件，就用一条边连接团问题是一组可满足赋值，其对应图中的灰色团团问题团问题还有一个疑问：归约为一个特殊的图，能说明一般图的团问题也是NP完全的吗？顶点覆盖问题顶点覆盖问题顶点覆盖问题证明这是一个NP问题顶点覆盖问题顶点覆盖问题顶点覆盖问题顶点覆盖问题哈密顿回路哈密顿回路哈密顿回路证明哈密顿回路哈密顿回路哈密顿回路可以这样定义附件图吗？哈密顿回路用附件图替换哈密顿回路用附件图替换哈密顿回路多项式转换哈密顿回路以上过程是一种归约哈密顿回路以上过程是一种归约高级算法设计与分析近似算法目录概述旅行商问题子集和问题集合覆盖-整数规划斯坦纳最小树概述NPC问题该如何求解?如果规模很小，用指数运行时间算法对一些特殊的情况，如果有多项式时间可以解决，则设计多项式算法对用一般情况，则通过多项式时间的近似解法概述近似解的精确度C：某一算法解的代价C*：最优解的代价如果一个解达到此因子，则称算法C为ρ(n)近似算法概述近似模式：对于一个输入为n的实例，通常近似算法的因子为（1+ε）算法时间除了和n相关，和ε也相关如果对于任意一个ε>0，该算法都可以在输入规模为n的多项式时间内完成，称此模式为多项式时间近似模式显然此种模式下，当ε趋近于0时，算法逼近最优值，但可能算法的复杂度急剧增加，如时间复杂度为多项式时间近似模式中一种更好的模式称为完全多项式时间近似模式，其复杂度为：这种模式当ε减少时，运行时间不会指数增长，而是多项式增长旅行商问题旅行商问题为NPC问题定义：对于完全无向图G=（V，E），设c(A)为子集A的总代价三角不等式：旅行商问题满足三角不等式的旅行商问题生成最小生成树按对树进行先序的顺序访问节点上述算法中，生成最下生成树可以用Kruskal算法或者Prim算法，复杂度都为O(mlogn)。先序遍历的复杂度为O(n)，所以旅行商问题的近似算法复杂度为O(mlogn)

旅行商问题旅行商问题最优旅行线路（H*）的总代价的下限为最小生成树（T）边的总代价对T进行按先序往返（返回时会再次遍历节点）遍历（W），W刚好对所有的边遍历两次旅行商问题一般旅行商问题三角不等式不成立的条件下，ρ近似的旅行商问题是一个NPC问题，则定理自然成立旅行商问题如果图G存在一条哈密顿回路H，则G′必然存在一条代价为n的旅行商回路TSP(同H),此回路为ρ近似旅行商回路如果图G′存在一条ρ近似的旅行商回路TSPρ，则图G必然存在一条哈密顿回路H

子集和问题准确算法（指数时间复杂度）:得出集合S的所有子集，并计算所有子集的和优化在第i-1轮迭代中，计算(e1,e2,…,ei-1)所有的子集和在第i轮迭代中，计算(e1,

e2,…,ei)在相加的过程中，一旦子集和超过t，舍弃子集和问题子集和问题去除相近的元素：x可以被y代替例子子集和问题子集和问题子集和问题子集和问题子集和问题按这两种不同的情况讨论子集和问题子集和问题子集和问题所以：子集和问题子集和问题Ln必然包含0元素，可能包含1元素集合覆盖问题简单集合覆盖

集合覆盖问题：例子集合覆盖问题贪心算法集合覆盖问题算法第i次选择了子集Si加入到顶点覆盖集R，则其总代价+1在选取第i个子集Si时，假设ni个元素被Si首次覆盖，其中每个元素分配到的代价为：集合覆盖问题集合覆盖问题当近似算法选择了i个子集后，子集S中未被覆盖的元素的个数集合覆盖问题集合覆盖问题集合覆盖问题集合覆盖-整数规划带权重的集合覆盖：覆盖所有的元素，其权重总和最小设E={1,2,3,4,5,6,7,8}子集有:S1={1,2,3}w1=1S2={2,7,8}w2=2S3={4,5,6,7}w3=3S4={4,5,6,8}w4=4解:C={S1,S2,S3},C={S1,S2,S4}最优解：C={S1,S2,S3}集合覆盖-整数规划松弛集合覆盖-整数规划算法元素的最大频率f：设g表示包含某一元素的子集个数，则最大的g即元素的最大频率f在所有的LP最优解的子集中，选取xi（每个子集通过LP求解得出的值）的值大于1/f的子集作为IP的解集合覆盖-整数规划证明1：以上选取的子集包含了E中所有的元素集合覆盖-整数规划集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法斯坦纳最小树斯坦纳最小树用最小生成树来近似斯坦纳树？斯坦纳最小树斯坦纳最小树：例子GRTMTGMTTST斯坦纳最小树：例子算法基于原图G，生成R的一个完全图GR，其中任意一条边的权重为原图G中的最短路径基于GR，生成最小生成树TMT

将TMT

中的边替换成原来的最短路径，得到图GMT

如果替换成最短路径后生成的图不是树，则需进一步生成最小生成树TST

斯坦纳最小树：例子斯坦纳最小树：例子斯坦纳最小树：例子W对TST按照先序往返(返回时会再次遍历节点)遍历斯坦纳最小树：例子GST

的旅行商回路和图GR(近似算法完全图)的旅行商回路之间的关系GR的旅行商回路和其上最小生成树TMT

斯坦纳最小树：例子树TMT

和图GMT

图GMT

和近似算法生成的树TST

高级算法设计与分析随机算法目录概述随机快速排序最小圆覆盖弗里瓦德算法集合覆盖最小割概述概述此算法可能返回0，也可能返回n∗a，算法复杂度可能为Θ(1)，也可能为Θ(n)概述：分类1拉斯维加斯算法(LasVegas)算法能够得到一个确定性的解决，但算法执行时间不确定例子:在有n个元素的数组A中，有一半的元素为0，另一半的元素为1(随机分布)，找到一个值为1元素的下标。概述：分类1蒙特卡洛算法(MonteCarlo)蒙特卡洛算法得出的解是不确定的，但是执行时间是确定的概述：分类1概述：分类2概述：分类2分类避免落入最坏情形降低算法复杂度避免落入最坏情形：随机快速排序快速排序的平均复杂度是O(nlogn)，但是在最坏的情况下，算法的复杂度为O(n2)。为了消除这种最差的情况，可以在快速排序引入一种随机因素随机快速排序在数组中随机的选择一个元素作为主元素Lomuto划分避免落入最坏情形：随机快速排序避免落入最坏情形：随机快速排序避免落入最坏情形：随机快速排序秩小于i和大于j的元素被选为主元，i和j的比较概率并不会受到影响如果i和j被选为主元，则i和j进行比较(共2个元素)大于i且小于j的元素被选为主元(共j−i−1个元素)，则i和j不会比较避免落入最坏情形：随机快速排序最小圆覆盖所有三个点形成的圆个数为O(n3)，判断每个圆是否包含所有其他点O(n)，暴力求解的总复杂度为O(n4)最小圆覆盖随机增量法(randomizedincrementalconstruction)增量:通过逐个的添加点，来计算每一步的最小覆盖圆，即计算一个点的最小圆覆盖，两个点的最小圆覆盖，···，直到n个点的最小圆覆盖;随机:通过一种随机的方式来添加点，避免算法跌入最坏情况。最小圆覆盖设目前新添加的点是pi，那么存在两种情况:如果添加的新点pi

已经被包含在Ci−1

内，那么Ci=Ci−1

添加的新点pi

没有被包含在Ci−1

内，此时需要增大圆，增大到什么时候为止?圆刚好能够包含pi

。最小圆覆盖假设结论不成立：最小圆覆盖pi在圆上，可以通过遍历{p1,p2,···,pi−1}上任意的两个点组合来确定Ci

p1

加入，这样p1

和pi

形成两个节点的最小圆，再依次加入{p2,···,pi−1}，直到找到第一个不被当前最小圆包含的点(设为pj)。pj和pi，它们是{p1,p2,···,pj,pi}这些点的最小圆边界上的点再次对{p1,p2,···,pj−1}这些点增量判断，得到{p1,p2,···,pj,

pi}这些点的最小圆重复上述流程，直到得到{p1,p2,···,pi−1,pi}所有这些点的最小圆最小圆覆盖最小圆覆盖最小圆覆盖算法复杂度最小圆覆盖算法复杂度主函数：因为点排列的随机性，第i个点在Ci

边界上的概率只有3/i（或者2/i）

最小圆覆盖算法复杂度MinDisc1Piont函数的复杂度最小圆覆盖算法复杂度MinDisc1Piont函数的复杂度最小圆覆盖算法复杂度主函数分类避免落入最坏情形降低算法复杂度弗里瓦德算法(Frievald’sAlgorithm)弗里瓦德算法(Frievald’sAlgorithm)弗里瓦德算法(Frievald’sAlgorithm)集合覆盖集合覆盖的随机算法基于IP建模，以及其对应的松弛LP问题假设已经求得LP问题的最优解x∗，在随机算法中，最优解x∗

看成子集S的选取概率集合覆盖某个元素ei通过随机算法没有被覆盖的概率集合覆盖抛k次硬币，只要出现一次硬币朝上，子集Sj被选中集合覆盖为了算法能够得出一个合法解，我们可以通过多次执行上面的抛硬币流程，直到得出合法解为止算法repeat期望执行次数为多少次？集合覆盖算法repeat期望执行次数为多少次？即求算法执行一次repeat，得出合法解，且代价（权重之和）小于4k·OPTLP

的概率集合覆盖集合覆盖集合覆盖最小割最小割最小割随机的方式得出一个最小割的概率是多少?最小割最小割最小割最小割最小割最小割最小割在得到一个收缩图G后，对图G应用两次随机收缩算法，并递归的应用以上方法通过7

次收缩，可随机得到4

个割，但如果进行独立的收缩，则需要4∗3=12次的收缩。最小割最小割最小割最小割递归收缩图的叶子层（也就是边界条件）看成是第0层，其上一层为第1层，以此类推，则第k+1层节点得出最小割概率p_{k+1}的递归式：高级算法设计与分析在线算法目录基本概念确定性在线算法在线最小生成树时间序列搜索随机在线算法租买问题在线二分图最大匹配概述离线算法在前面讨论的算法中，问题实例的所有数据在计算时，都是已知的，称为离线算法在线算法问题实例的数据是逐渐到来的，但是又需要对已经到来的数据进行计算，也就是说算法必须在输入数据不是很完全可知的情况下，完成相应的计算并输出结果如股票买卖、物流中的装车问题在线算法是近似算法概述人工智能算法试图从以往的数据中寻找出规律，并根据目前的分配状态，来智能的分配目前到达的任务在线算法数据完全未知假设存在一个对手(adversary)：这个对手对设计的算法了如指掌，所以能够针对算法给出最坏数据到达实例(称为最坏实例)，来使得算法的效率最低，所以设计在线算法时，通常需要分析在最坏实例下算法的性能。概述：流程股票买卖为例概述：定义竞争度ρ概述：定义在线算法的下界下界表达式给出了在最差实例下，任意在线算法ALG和OPT存在大于等于的关系，如果某算法ALG′的ρ=α，且c=0,b=0，说明在线算法ALG′的性能已经最优，因为所有在线算法在最坏实例下都是大于等于竞争度ρ的，当在线算法ALG′的竞争度是小于等于ρ，显然ALG′已经最优。确定性在线算法：在线最小生成树在线最小生成树图中的顶点不是一开始就已知，而是逐个到达，并要求一旦一个顶点到达就需要加入到树中，且让生成的树总代价尽量小。一个比较简单的在线算法是让到达的顶点通过离树内最近的顶点加入到树中。如，在第k个顶点到达时，选取前面k−1个顶点中和第k个顶点距离最近的顶点，通过此顶点将第k个顶点加入到树中。我们把这种算法称为最小生成树的贪心在线算法。确定性在线算法：在线最小生成树在线最小生成树确定性在线算法：在线最小生成树确定性在线算法：在线最小生成树确定性在线算法：在线最小生成树确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索确定性在线算法：时间序列搜索目录基本概念确定性在线算法在线最小生成树时间序列搜索随机在线算法租买问题在线二分图最大匹配随机在线算法策略的做出是随机性，形成随机在线算法，随机在线算法的好处是，假设的对手无法猜测算法的策略。随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题回到上面租买问题的例子ρ=4/3

的竞争度，这个竞争度比任意的确定性算法都要好，但这个竞争度是实例{I1,I2,I3}下的最优竞争度吗随机在线算法：租买问题随机实例下确定性算法费用和竞争度的计算随机在线算法：租买问题随机在线算法：租买问题随机在线算法：租买问题随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配按秩进行贪心匹配的确定性算法随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配在小数二分图匹配中，一个到达的顶点(a∈A)可以和B中的顶点(可以有多个)部分匹配随机在线算法：在线二分图最大匹配一个非常简单的算法是:当一个顶点ai到达时，和所有可匹配的顶点进行均匀匹配水位算法(waterlevelalgorithm)是一个非常著名的确定性在线算法，当A中的一个顶点a到达时，算法依据顶点a所有邻顶点的匹配状态，将a的匹配分配到这些邻顶点中，使得分配后，所有的邻顶点的匹配总量相似随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配随机在线算法：在线二分图最大匹配高级算法设计与分析启发式算法内容概述模拟退火Tabusearch遗传算法蚁群算法优化问题经典优化算法通过对解空间的枚举（离散），或者对目标函数的微分（连续）求最优解默认为存在唯一最优解但很多优化问题无法通过上述方法求得最优解问题不是凸的（凸优化）解空间太大大多数问题只能求出近似解近似算法、随机算法启发式算法启发式算法启发式算法(heuristicalgorithm)指通过对过去经验的归纳推理以及实验分析来解决问题的方法，即借助于某种直观判断或试探的方法，以求得问题的次优解或以一定的概率求其最优解，所以可以认为启发式算法一种基于经验或者实验算法的统称元启发式算法(metaheuristic)元启发式算法都从自然界的一些现象取得灵感(e.g.模拟退火、遗传算法)，通过这些现象获取的求解过程(元启发式算法)来解决实际的一些问题启发式算法元启发式算法看成构造启发式算法的一些基础方法，而启发式算法就是利用元启发式算法，结合被求解问题的特征，设计出来的面向特定问题的算法启发式算法通常基于自然界中发现的一些规律或者准则能够被计算机计算和处理目标是得出最优解的近似解，但不能确定得到的解就是最优解但通常得到的解比局部最优解要好适用于不同的问题，并能同时考虑一些约束条件启发式算法启发式算法局部搜索方法经典的启发式算法（元启发式算法）模拟退火（Simulatedannealing）禁忌搜索（Tabusearch）遗传算法（Geneticalgorithms）蚁群算法（Antcolonies）局部搜索：2-opt算法2-opt变换在旅行商问题中，去除某一回路l的两条边e1和e2，形成了两个子图，对这两个子图重新连接形成新的回路l′，l′是通过对l的2-opt交换形成的局部搜索：2-opt算法局部搜索：2-opt算法局部搜索：3-opt算法内容概述模拟退火Tabusearch遗传算法蚁群算法模拟退火什么是退火——物理上的由来退火（annealing）现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」，quenching）时，会导致不是最低能态的非晶形。模拟退火什么是退火——物理上的由来如下图所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）模拟退火算法概述若目标函数f在第i+1步移动后比第i步更优，即f(Y(i+1))<=f(Y(i))，则总是接受该移动；若f(Y(i+1))>f(Y(i))(即移动后的解比当前解要差)，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）。Metroplis准则模拟退火Metroplis准则温度越高，算法接受新解的概率越高。这个根据一定概率选择是否接受差解的方法叫做Metropolos准则模拟退火：算法模拟退火：算法模拟退火：旅行商问题旅行商问题输入：旅行图、初始温度、最小温度、降温系数输出：旅行回路算法随机选择城市顺序在第i步的基础上，随机交换两个（或多个）城市的顺序（移动一步）如果第i+1步的代价更小，则作为当前哈密顿回路，否则依据Metroplis准则定义的概率作为当前回路，重复执行此步骤n次按照降温系数降低温度，重复以上步骤直到迭代次数达到预设值或者温度下降到预设值模拟退火：旅行商问题内容概述模拟退火Tabusearch遗传算法蚁群算法Tabusearch从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于，太过于对某一局部区域以及其邻域的搜索，导致一叶障目。为了找到全局最优解，禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它，从而或得更多的搜索区域。Tabusearch：相关概念邻域所谓邻域，简单的说即是给定点附近其他点的集合。邻域就是指对当前解进行一个操作(这个操作可以称之为邻域动作)可以得到的所有解的集合。邻域动作邻域动作是一个函数，通过这个函数，对当前解s，产生其相应的邻居解集合。例如：对于一个bool型问题，其当前解为：s=1001，当将邻域动作定义为翻转其中一个bit时，得到的邻居解的集合N(s)={0001,1101,1011,1000}，其中N(s)∈S。Tabusearch：相关概念禁忌表禁忌对象：由于需要避免一些操作的重复进行，就要将一些元素放到禁忌表中以禁止对这些元素进行操作，这些元素就是我们指的禁忌对象（通常指找到的局部最优解）。禁忌长度：禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象x一个数（禁忌长度）t，要求对象x在t步迭代内被禁，在禁忌表中采用tabu(x)=t记忆，每迭