《高级算法设计》课件 第1、2章 线性规划;高级图算法

高级算法设计与分析线性规划基本概念基本概念基本概念线性规划的形式：线性规划：定义标准型和松弛型标准型和松弛型非标准型目标函数不是最大化，而是最小化约束条件是大于等于约束约束条件是等式约束;存在一些变量没有非负约束标准型和松弛型非标准型例子标准型和松弛型标准型和松弛型标准型和松弛型标准型：标准型和松弛型松弛型：在松弛型中，等式左边的变量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̸