中科大算法设计与分析.pdf

Edit by James Wu 2011/1/10 1.概率算法部分概率算法部分 1.0 几个基本概念几个基本概念 1.0.1 期望时间和平均时间的区别期望时间和平均时间的区别 确定算法的平均执行时间确定算法的平均执行时间：输入规模一定的所有输入实例是等概率出现时，算法的平均执行时间 概率算法的期望执行时间概率算法的期望执行时间：反复解同一个输入实例所花的平均执行时间 概率算法的平均期望时间概率算法的平均期望时间：所有输入实例上平均的期望执行时间 概率算法的最坏期望时间概率算法的最坏期望时间：最坏的输入实例上的期望执行时间 1.0.2 Uniform 函数函数 在在 X 中随机，均匀和独立地取一个元素的算法中随机，均匀和独立地取一个元素的算法：ModularExponent(a,j,p)/求方幂模求方幂模 s=aj mod p,注意先求注意先求 aj可能会溢出可能会溢出 s 1;while j0 do if(j is odd)s sa mod p;a a2 mod p;j j div 2;return s;Draw(a,p)/在在 X 中随机取一元素中随机取一元素 j uniform(1.p-1);return ModularExponent(a,j,p);/在在 X 中随机取一元素中随机取一元素 1.1 概率算法的分类概率算法的分类 1.1.1 数字算法数字算法 主要用于找到一个数字问题的近似解 使用的理由 现实世界中的问题在原理上可能就不存在精确解，例如，实验数据本身就是近似的，一个无理数在计算机中只能近似地表示 精确解存在但无法在可行的时间内求得，有时答案是以置信区间的形式给出的 1.1.2 Monte Carlo 算法算法 特点：MC 算法总是给出一个答案，但该答案未必正确，成功(即答案是正确的)的概率正比于算法执行的时间 缺点：一般不能有效地确定算法的答案是否正确 1.1.3 Las Vagas 算法算法 LV 算法绝不返回错误的答案。特点：获得的答案必定正确，但有时它仍根本就找不到答案。和 MC 算法一样，成功的概率亦随算法执行时间增加而增加。无论输入何种实例，只要算法在该实例上运行足够的次数，则算法失败的概率就任意小。1.1.4 Sherwood 算法算法 Sherwood 算法总是给出正确的答案。当某些确定算法解决一个特殊问题平均的时间比最坏时间快得多时，我们可以使用Sherwood 算法来减少，甚至是消除好的和坏的实例之间的差别。1.2 算法的实现方式算法的实现方式 1.1.1 数字算法数字算法 1.1.1.1 HitorMiss 算法计算积分（面积法）算法计算积分（面积法）HitorMiss(f,n)k 0;for i 1 to n do,x uniform(0,1);y uniform(0,1);if f(x,y)在满足的面积内 then k+;return k/n;1.1.1.2 Crude 算法计算积分（积分化求平均值法）算法计算积分（积分化求平均值法）Crude(f,n,a,b)sum 0;for i 1 to n do,x uniform(a,b);sum sum+f(x);return(b-a)sum/n;1.1.1.3 两种方法的比较两种方法的比较 对于给定的迭代次数 n，Crude 算法的方差不会大于 HitorMiss 的方差。但不能说，Crude 算法总是优于 HitorMiss。因为后者在给定的时间内能迭代的次数更多。例如，计算 值时，Crude 需计算平方根，而用投镖算法 darts 时，即 HitorMiss无需计算平方根。1.1.1.4 确定的算法确定的算法梯形算法（上底加下底乘以高除以梯形算法（上底加下底乘以高除以 2）Trapezoid(f,n,a,b)/假设 n 2 delta (b-a)/(n-1);sum (f(a)+f(b)/2;for x a+delta step delta to b delta do sum sum+f(x)return sum delta;一般地，在同样的精度下，梯形算法的迭代次数少于 MC 积分，但是有时确定型积分算法求不出解，若用 MC 积分则不会发生该类问题，或虽然发生，但概率小得多。在确定算法中，为了达到一定的精度，采样点的数目随着积分维数成指数增长，例如，一维积分若有 100 个点可达到一定的精度，则二维积分可能要计算 1002个点才能达到同样的精度，三维积分则需计算 1003个点。(系统的方法)但概率算法对维数的敏感度不大，仅是每次迭代中计算的量稍增一点，实际上，但概率算法对维数的敏感度不大，仅是每次迭代中计算的量稍增一点，实际上，MC 积分特别适合用于计算积分特别适合用于计算 4 或更高维数的定积分。或更高维数的定积分。若要提高精度，则可用混合技术：部分采用系统的方法，部分采用概率的方法若要提高精度，则可用混合技术：部分采用系统的方法，部分采用概率的方法 1.1.1.5 例例 1：求集合的势：求集合的势 问题描述问题描述：估算一个集合中元素的个数 解决思路解决思路：设 X 是具有 n 个元素的集合，我们有回放地随机，均匀和独立地从 X 中选取元素，设 k 是出现第 1 次重复之前所选出的元素数目，则当n 足够大时，k 的期望值趋近为?，这里?L?6?N?s?t?w?u 利用此结论可以得出估计|X|的概率算法：?L?J?t?L?:?L?t?G?6?算法算法：SetCount(X)k 0;S ;a uniform(X);do k+;S S,a-;a uniform(X);while(a?S)return 2k2/复杂度复杂度：注意：k 的期望值是?，上述算法 n 需足够大，且运行多次后才能确定 n=|X|，即取多次运行后的平均值才能是 n。该算法的时间和空间均为?，因为?1.1.1.6 例例 2：多重集合中不同数目的估计多重集合中不同数目的估计 用散列表?，若以元素 e 的 hash(e)以 0001 开头（前面k-1 个 0），则?最后返回?中第一个出现 0 的位置?，则集合中不同元素的下界和上界分别是2z-2,2z 复杂度复杂度：时间 O(N)，空间：O(lgN)1.1.2 Sherwood 算法算法 1.1.2.1 Sherwood 算法的基本思想算法的基本思想 对于一个确定性算法，它的平均时间很容易计算：T（确定性算法平均时间）=（每次执行的时间之和）/（执行总次数）但是会存在这样一个不好的情况：某次执行的时间远远大于平均执行某次执行的时间远远大于平均执行时间，比如最坏情况。时间，比如最坏情况。Sherwood 算法的目的就是为了解决这个问题，利用概率的方法（或者利用概率的方法（或者说随机的方法）避免了最坏情况的发生说随机的方法）避免了最坏情况的发生，但这是要付出其他的时间代价（比如在取随机的时候需要花费一点时间），所以 Sherwood 算法的平均时间稍稍大于确定性算法的平均时间。Sherwood 算法的应用范围：在确定性算法中，它的平均执行时间较优，最坏性能较差，这样的算法就用 Sherwood 算法去改进 Sherwood 一般方法是：将被解的实例变换到一个随机实例。/预处理 用确定算法解此随机实例，得到一个解。将此解变换为对原实例的解。/后处理 1.1.2.2 Sherwood 算法预处理的数学模型算法预处理的数学模型 1.确定性算法：f:X-Y 2.确定性算法的实例集合：X,size 为 n 时写作 Xn 3.Sherwood 算法用于均匀随机抽样的集合：A，size 为 n 时写作 An，|An|=|Xn|4.随机抽样的预处理及后处理时用到的一对函数，对应上面的，（PPT在这里有误）u:X?H A-Y v:A?H Y-X u,v 满足三个性质：?z?:?;?:?;?:?”?;，使得?这条对应，其中?表示有且仅有一个?z?:?;?:?;?:?”?;，使得?这条对应?z 函数 u,v 在最坏情况下能够有效计算 1.1.2.3 Sherwood 算法的过程算法的过程 确定算法 f(x)可改造为 Sherwood 算法：RH(x)/用 Sherwood 算法计算 f(x)n length*x+;/x 的 size 为 n r uniform(An);/随机取一元素 y u(x,r);/将原实例 x 转化为随机实例 y s f(y);/用确定算法求 y 的解 s return v(r,s);/将 s 的解变换为 x 的解 1.1.2.4 例例 1：选择和排序的：选择和排序的 Sherwood 算法算法 只需进行简单的打乱顺序即可，u 即表示打乱顺序函数 shuffle Shuffle(T)n length*T+;for i 1 to n-1 do /在 T i.n 中随机选 1 元素放在 T i 上 j uniform(i.n);T*i+T*j+;1.1.2.5 例例 2：离散对数计算：离散对数计算?z 问题描述问题描述：设 a=gx mod p，记 logg,pa=x，称 x 为 a 的(以 g 为底模除 p)对数。从 p，g，a 计算 x 称为离散对数问题。问题在于：给出 p,g,a，怎么求 x?z 简单算法简单算法：?x,计算 gx 最多计算 0 x p-1 或 1xp，因为实际上离散对数是循环群；验证 a=gx mod p 是否成立。dlog(g,a,p)/当这样的对数不存在时，算法返回 p x 0;y 1;do x+;y y*g;/计算 y=gx -while(a y mod p)and(x p);return x 问题：最坏问题：最坏 O(p)，若，若 P 很大怎么办？所以简单算法不行很大怎么办？所以简单算法不行 而且而且 x 的算出来的快慢取决于的算出来的快慢取决于 a 的取值，的取值，a 的取值能够让算法较早找到正的取值能够让算法较早找到正确的确的 x，则算法很快就完了，否则很慢，直到，则算法很快就完了，否则很慢，直到 p。?z Sherwood 算法解决方法算法解决方法 根据上面的分析，Sherwood 算法应该使得这个算法不会根据 a,p 的取值影响算法的快慢 定理：1.Logg,p(st mod p)=(logg,p s+logg,p t)mod(p-1)2.Logg,p(gr mod p)=r,0=r vali do i ptr*i+;return i;4 种算法：种算法：?z A(x),时间复杂度时间复杂度 O(n)A(x)return Search(x,head);?z D(x)，时间复杂度，时间复杂度 O(n/3)D(x)i uniform(1.n);y val*i+;case x y:return Search(x,ptri);/case2 otherwise:return i;/case3，x=y?z B(x)，时间复杂度，时间复杂度 O(?)算法基本思想算法基本思想：对于一个有序表 S，它上面的元素分别是 a1,a2,an，它们之间可以是乱序的，要查找的 x 是其中一员。若把 a1,a2,an有序排列成为 ao1ao2aon，x 仍然是其中一员。把 ao1ao2aon划分成 L个区间，x 也必然是某个区间中的一员。那么根据 Search(x,i)是一个有序查找过程，只需要找到 x 所在区间中在 x 之前的元素的 index，或者 x 所在区间的前面任何一个区间的元素的 index，在调用 Search(x,index)，其时间肯定不超过 2n/L，而且期望时间是 n/L。而根据 S 中元素分布的均匀性，a1,a2,an排列的前 L 个元素在概率上，是由 ao1ao2aon的 L 划分中，每个区间各取一个元素组成的，所以会出现：ao1ao2aon的L划分中x所在区间中在x之前的元素，或者是，x 所在区间的前面任何一个区间的元素，满足这两点中的任意一点即可，数越大越靠近 X。那么算法可以这么描述：找 S 的 a1,a2,an序列的前 L 个元素中最大的数，得到它的 index，然后用 Search(x,index)，经过期望时间n/L，最终找到 x，则时间复杂度是 O(L+n/L)，当 L=?时取到最小值 O(2?)B(x)/设设 x 在在 val1.n中中 i head;max val*i+;/max 初值是表初值是表 val 中最小值中最小值 for j 1 to?do /在在 val 的前个的前个?数中找不大于数中找不大于 x y val*j+;/的最大整数的最大整数 y 相应的下标相应的下标 i if max y x then,i j;max y;/endif /endfor return Search(x,i);/从从 y 开始继续搜索开始继续搜索?z C(x)，时间复杂度，时间复杂度 O(?)，平滑，平滑 B(x)在不同实例上的执行时间在不同实例上的执行时间 C(x)/设设 x 在在 val1.n中中 i head;max val*i+;/max 初值是表初值是表 val 中最小值中最小值 for k 1 to?do /在在 val 中进行中进行?次寻找，找到最大的一个整数及其下标次寻找，找到最大的一个整数及其下标 j uniform(1n);y val*j+;/的最大整数的最大整数 y 相应的下标相应的下标 i if max 0)then/nb=0 时无安全位置，第时无安全位置，第 k+1 个皇后尚未放好个皇后尚未放好 /在所有在所有 nb 个安全位置上，个安全位置上，(k+1)th 皇后选择位置皇后选择位置 j 的概率为的概率为 1/nb kk+1；/try1.k+1是是(k+1)-promising try*k+j；/放置放置(k+1)th 个皇后个皇后 col col j；diag45 diag45 j-k；diag135 diag135 j+k；/endif until（nb=0）or（k=8）；）；/当前皇后找不到合适的位置或当前皇后找不到合适的位置或 try 是是 /8-promising 时结束。时结束。success （nb0）；）；4.问题的改进问题的改进 上述完全随机的方法的期望时间还是有点多，就采用折中的方法：先用 Las Vegas 排头几行，再用回溯法去做，只需将 QueensLV 的最后两行改为：until nb=0 or k=stepVegas；if（nb0)then/已随机放好已随机放好 stopVegas 个皇后个皇后 backtrace(k,col,diag45,diag135,success);else success false；结论：一半略少的皇后随机放置较好。结论：一半略少的皇后随机放置较好。1.1.3.5 例例 2：模：模 P 平方根平方根 问题描述：问题描述：设 p 是一个奇素数，若整数 x1,p-1且存在一个整数 y，使得?，则称 x 为模 p 的二次剩余，若 y 1,p-1，则 y 称为 x 模 p 的平方根。问题所求：问题所求：当给定 x 和奇素数 p 时，求 y。重要结论：结论 PPT 上有很多，这里只列举一个，若 y 是 x 模 p 的平方根，则 p-y也是。Las Vegas 解决算法：解决算法：rootLV(x,p,y,success)/计算计算 y a uniform(1.p-1);/我们并不知道我们并不知道 a 应取多少应取多少 if?“?then /可能性很小可能性很小 success true；y a；Else 计算计算 c，d 使得使得?Q?Q?F?k?E?o?7?E?:?“?;if d=0 then success false；/无法求出无法求出 else/c=0 success true；y Euclid_Modify(d,p);/?计算计算?!?使得使得?!?Euclid_Modify(a,b)/计算计算?Q?Q?F?使得使得?，即，即?E?!?stack stackAB(int,int)/定义一个定义一个(int,int)类型的栈类型的栈 While(b 0)stackAB.Push(a,b);/将将(a,b)入栈入栈 ta;ab;bt t%b;x=1;y=0;while(stackAB!=empty)(a,b)stackAB.Pop();/出栈出栈 tx;xy;yt (a/b)y;If(x0)While(x b 0)xx b;else if(x 0)while(x+b 0)xx+b;return x;1.1.3.6 例例 3：整数的因数分解整数的因数分解 问题描述：问题描述：寻找合数 n 的非平凡因数（不是 1 和 n）算法步骤：算法步骤：?z Step1：在 1n-1 之间随机选择 x i)若 x 碰巧不与 n 互素，则已找到 n 的一个非平凡因子(即为 x)ii)否则设?，若 y 是 k-平滑，则将 x 和 y 的因数分解保存在表里。此过程重复直至选择了 k+1 个互不相同的整数，并且这些整数的平方模 n 的因数已分解(当 k 较小时，用 split(n)分解）?z Step2：在 k+1 个等式之中找一个非空子集，使相应的因数分解的积中前 k 个素数的指数均为偶数(包含 0)，用 0-1 矩阵去实现 使用 Gause-Jordan 消去法可得到线性相关的行?z Step3：在 step2 中找到线性相关的行后：1.令 a 为相应 xi的乘积 2.令 b 是 yi的乘积开平方 若?，则只需求 a+b 和 n 的最大公因子即可获得 n 的非平凡因子。时间分析：时间分析：如何选择如何选择 k.1)k 越大，?是 k-平滑的可能性越大(x 是随机选取的)2)k 越小，测试 k-平滑及因数分解 yi的时间越小，确定 yi 是否线性相关的时间也越少，但?不是 k-平滑的概率也就较大。设?通常取?时较好，此时 Dixon 算法分裂 n 的期望时间为?，成功的概率至少为 1/2.1.1.4 Monte Carlo 算法算法 1.1.4.1 基本概念基本概念 Monte Carlo 算法偶然会犯错，但它无论对何实例均能以高概率找到正确解。当算法出错时，没有警告信息。偏真偏假的概念只在 Monte Carlo 算法里出现?Def1：设 p 是一个实数，且 1/2p1，若一个 MC 算法以不小于 p 的概率返回一个正确的解，则该 MC 算法称为 p-正确，算法的优势（advantage）是 p-1/2.?Def2：若一个 MC 算法对同一实例决不给出两个不同的正确解，则该算法称是相容的（consistent）或一致的。?基本思想：为了增加一个一致的、p-正确算法成功的概率，只需多次调用同一算法，然后选择出现次数最多的解。?Def：(偏真算法)为简单起见，设 MC(x)是解某个判定问题，对任何 x，若当 MC(x)返回 true 时解总是正确的，仅当它返回 false 时才有可能产生错误的解，则称此算法为偏真的(true-biased)。?Def：(偏 y0算法)更一般的情况不再限定是判定问题，一个 MC 是偏 y0的(y0是某个特定解)，如果存在问题实例的子集 X 使得：若被解实例?，则算法 MC(x)返回的解总是正确的(无论返回 y0还是非 y0)若?，正确解是 y0，但 MC 并非对所有这样的实例 x 都返回正确解。1.1.4.2 两两个定理个定理 1.设 2 个正实数之和+n/2);majMC(T,)k for i 1 to k do if maj(T)then return true;/成功成功 return false;/可能失败可能失败 时间复杂度时间复杂度：O(nlg(1/)1.1.4.4 例例 2：素数测定：素数测定 问题描述问题描述：判断一个大于 4 的奇数是否是素数 基本概念基本概念：?z 伪素数和伪证据：设 2an-2，一个满足?（即 n 可整除 an-1-1）的合数 n 称为以 a 为底的伪素数，a 称为 n 的素性伪证据。?z 强伪素数和强伪证据：设 n 是一个大于 4 的奇整数，s 和 t 是使得?的正整数，其中 t 为奇数，设 B(n)是如下定义的整数集合：?:?;当且仅当 2an-2 且满足下述 2 个条件之一：?=?s?I?K?J?r?;?且?为整数，使得?当 n 为当 n 为素数时，?小，使得 n 满足条件 1 或者条件 2，所以?，这一点可以由?定理很容易得证 当 n 为合数时，若?，则称 n 为一个以 a 为底的强伪素数强伪素数，称 a为 n 素性的强伪证据强伪证据。强伪证据的性质强伪证据的性质：?z 强伪证据数目比伪证据数目少很多?z 若 n 是素数，则强伪证据集合?z 若 n 是合数，则强伪证据的个数?，这一点说明当 n为合数时，强伪证据数目3/4，正确的概率75%偏性特点偏性特点：偏假，一次检验 3/4correct，只要坚持出 n 不是素数，返回 false，则一定正确 算法算法：Btest(a，n)/n 为奇数，为奇数，?F?，返回，返回?;?:?;/即返回真说明即返回真说明 n 是强伪素数或素数是强伪素数或素数 s0；t n-1；/t 开始为偶数开始为偶数 repeat s+；t t2；until t mod 2=1；/n-1=2st，t 为奇数为奇数 x at mod n；if x=1 or x=n-1 then return true；/满足满足or，for i 1 to s-1 do/验证验证 x x2 mod n；if x=n-1 then return true；/满足，满足，return false；一次测试：MillRab(n)/奇奇 n4，返回真时表示素数，假表示合数，返回真时表示素数，假表示合数 auniform(2.n-2);return Btest(a,n);/测试测试 n 是否为强伪素数是否为强伪素数 多次测试：?少?RepeatMillRob(n,k)for i 1 to k do if MillRob(n)=false then return false;/一定是合数一定是合数 return true；时间复杂度时间复杂度：?1.1.4.5 矩阵乘法验证矩阵乘法验证 问题描述问题描述：设设 A，B，C 为为 nn 矩阵，判定矩阵，判定 AB=C?MC 方法方法：设 X 是一个长度为 n 的二值向量(0/1 行向量)，将判断 AB=C改为判断 XAB=XC？偏性偏性：偏假，一次检验 1/2correct，算法算法：一次检验：goodproduct(A,B,C,n)for i1 to do x*i+uniform(0.1);if(XA)B=XC then return true;else return false;多次检验，将出错概率降低到?，则至少要?少?次 RepeatGoodProduct(A,B,C,n)for i1 to?R?5?”?A?S do /重复重复?R?5?”?A?S次次 if GoodProduct(A,B,C,n)=false then return false;/偏假的，有一次假即可返回偏假的，有一次假即可返回 return true;时间复杂度时间复杂度：?2.消息传递系统中的基本算法消息传递系统中的基本算法 2.1 基本概念基本概念 2.1.1 分布式模型分布式模型 异步共享存储模型异步共享存储模型：用于紧耦合机器，通常情况下各处理机的时钟信号不是来源于同一信号源 异步异步 msg 传递模型传递模型：用于松散耦合机器及广域网 同步同步 msg 传递模型传递模型：这是一个理想的 msg 传递系统 2.1.2 错误的种类错误的种类 初始死进程初始死进程：指在局部算法中没有执行过一步 崩溃错误崩溃错误(损毁模型损毁模型)：指处理机没有任何警告而在某点上停止操作 拜占庭错误拜占庭错误：一个出错可引起任意的动作,即执行了与局部算法不一致的任意步。拜占庭错误的进程发送的消息可能包含任意内容 2.1.3 消息传递系统概念消息传递系统概念 状态状态：pi的每个状态由 2r 个 msg 集构成，outbufi*l+(1lr)和 inbufi*l+(1lr)，其中r 是信道个数 初始状态初始状态：Qi包含一个特殊的初始状态子集：每个 inbufil必须为空，但 outbufil未必为空 转换函数转换函数：输入：pi可访问的状态，输出：对每个信道 l，至多产生一个 msg 输出，转换函数使输入缓冲区(1lr)清空 配置配置：配置是分布式系统在某点上整个算法的全局状态，向量=(q0,q1,qn-1),qi是pi的一个状态 事件事件：系统里所发生的事情均被模型化为事件，对于msg传递系统，有两种，comp(i)和 del(i,j,m)执行执行：系统在时间上的行为被模型化为一个执行，它是一个由配置和事件交错的序列。该序列须满足各种条件，主要分为两类?z 安全性条件安全性条件：表示某个性质在每次执行中每个可到达的配置里都必须成立?z 活跃性条件活跃性条件：表示某个性质在每次执行中的某些可达配置里必须成立。若一个执行也满足所有要求的活跃性条件，则称为容许执行容许执行 调度调度：一个调度总是和执行联系在一起的，它是执行中的事件序列：1,2,。并非每个事件序列都是调度。例如，del(1,2,m)不是调度，因为此事件之前，p1没有步骤发送(send)m 容许的调度容许的调度：若它是一个容许执行的调度 容许的执行容许的执行：指无限的执行 Msg 复杂度：复杂度：算法在所有容许容许的执行上发送 msg 总数的最大值(同步和异步系统)时间复杂度：时间复杂度：同步系统：最大轮数，即算法的任何容许执行直到终止的最大轮数。异步系统：假定任何执行里的 msg 延迟至多是 1 个单位的时间，然后计算直到终止的运行时间 消息复杂度：消息复杂度：消息总数/消息中总的位数长度。请注意和 Msg 复杂度的不同。2.2 生成树上的广播和汇集生成树上的广播和汇集 2.2.1 广播广播 基本思想基本思想：根节点发送 Msg 给孩子。收到 Msg 的节点转发 Msg 给孩子。Msg 复杂度复杂度：O(n-1)，因为生成树每条边有一个 Msg 时间复杂度时间复杂度：O(D)，D 为生成树直径 2.2.2 汇集汇集/敛播敛播 基本思想：基本思想：汇集是从所有节点收集信息至根 Msg 复杂度复杂度：O(n-1)，因为生成树每条边有一个 Msg 时间复杂度时间复杂度：O(D)，D 为生成树直径 2.3 指定根指定根构造生成树构造生成树 DFS 或或 BFS 2.3.1 洪泛洪泛 基本思想：基本思想：设 pr是特殊处理器。从 pr开始，发送 M 到其所有邻居。当 pi第1 次收到消息 M（不妨设此 msg 来自于邻居 pj）时，pi发送 M 到除 pj外的所有邻居。Msg 复杂度：复杂度：O(2e-E(Pr)时间复杂度：时间复杂度：O(D)2.3.2 构造生成树构造生成树 基本思想基本思想：回应和，具体算法略 证明注意要点证明注意要点：在证明构造 DFS 或者 BFS 时，要按以下步骤证明：先证连通性先证连通性。可用反证或归纳法证明。再证无环性再证无环性。可用反证法证明假设存在环 pi1,pikpi1 最后证明生成的是最后证明生成的是 DFS 或者或者 BFS。可用归纳法证明 构造构造 BFS 树树：Pj 收到 Pi 的 Msg 立马转发给所有除 Pi 以外的邻居 Msg 复杂度复杂度：O(m)，m 为边数 时间复杂度时间复杂度：O(D)，D 为直径 构造构造 DFS 树树：只有收到一条 Msg 或或才转发 Msg Msg 复杂度复杂度：O(m)时间复杂度时间复杂度：O(m)2.4 不指定根时构造生成树不指定根时构造生成树 基本思想基本思想：每个结点均可自发唤醒，试图构造一棵以自己为根的 DFS 生成树。若两棵 DFS 树试图链接同一节点(未必同时)时，该节点将加入根的 id 较大的 DFS 树。已知条件已知条件：个具有 m 条边和 n 个节点的网络，自发启动的节点共有 p 个，其中 ID值最大者的启动时间为 t Msg 复杂度：复杂度：O(pn2)。最坏情况下，每个处理器均试图以自己为根构造一棵 DFS 树。因此，Alg2.4 的 msg 复杂性至多是 Alg2.3 的 n 倍：O(m*n)时间复杂度：时间复杂度：时间复杂度为 O(t+m)3.环上选举算法环上选举算法 3.1 无聊无聊 3.2 Leader 选举问题选举问题 3.2.1 问题问题 在一组处理器中选出一个特殊结点作为 leader 3.2.2 用途用途 简化处理器之间的协作；有助于达到容错和节省资源。例如，有了一个 leader，就易于实现广播算法 代表了一类破对称问题。例如，当死锁是由于处理器相互环形等待形成时，可使用选举算法，找到一个 leader并使之从环上删去，即可打破死锁。3.2.3 问题描述问题描述 问题从具有同一状态的进程配置开始，最终达到一种配置状态。每个处理器最终确定自己是否是一个 leader，但只有一个处理器确定自己是 leader，而其他处理器确定自己是 non-leader。3.2.4 选举算法定义选举算法定义（1）每个处理器具有相同的局部算法；（2）算法是分布式的，处理器的任意非空子集都能开始一次计算；（3）每次计算中，算法达到终止配置。在每一可达的终止配置中，只有一个处理器处于领导人状态，其余均处于失败状态 3.3 匿名环匿名环 3.3.1 几个定义几个定义 匿名算法匿名算法：若环中处理器没有唯一的标识符，则环选举算法是匿名的 一致性的算法一致性的算法：若算法不知道处理器数目，则算法称之为 uniform，否则若知道处理器数目 n，则称之为非一致性算法。上面两个的形式化描述：在一个匿名、一致性的算法中，所有处理器只有一个状态机；在一个匿名、非一致性的算法中，对每个 n 值（处理器数目）都有单个状态机，但对不同规模有不同状态机，也就是说 n 可以在代码中显式表达。3.3.2 几个定理几个定理 引理引理 3.1：在环 R 上算法 A 的容许执行里，对于每一轮 k，所有处理器的状态在第 k 轮结束时是相同的。（用归纳法证明）定理定理 1：同步环系统中不存在匿名的、一致性的领导者选举算法（用引理 3.1证明，note:每个处理器同时宣布自己是 Leader）定理定理 2：异步环系统中不存在匿名的领导者选举算法 证明：每个处理器的初始状态相同，状态机相同，接收的消 息序列也相同（只有接收消息的时间可能不同），故 最终处理器的状态一致。由于处理一条消息的至多需 要 1 时间单位，若某时刻某个处理器宣布自己是 Leader （接收到 m 条消息），则在有限时间内（m 时间单位）其他处理器也会宣布自己是 Leader。所以，每个处理器会陆续宣布自己是 Leader。矛盾，证毕。3.3 异步环异步环 3.3.0 均匀和非均匀之分均匀和非均匀之分 由于没有匿名的异步环选举算法，这里默认所有算法非匿名，虽然说均匀对应一致，非均匀对应非一致，但实际上它们还是有差别的 均匀算法均匀算法：每个标识符 id，均有一个唯一的状态机，但与环大小 n 无关。而在匿名算法中，均匀则指所有处理器只有同一个状态。（不管环的规模如何，只要处理器分配了对应其标识符的唯一状态机，算法就是正确的。）非均匀算法非均匀算法：每个 n 和每个 id 均对应一个状态机，而在匿名非均匀算法中，每个 n 值对应一个状态机。（对每一个 n 和给定规模 n 的任意一个环，当算法中每个处理器具有对应其标识符的环规模的状态机时，算法是正确的。）3.3.1 LCR：一个简单的：一个简单的 O(n2)算法算法 基本思想基本思想：选择最大的 id 每个处理器 Pi发送一个 msg(自己的标识符)到左邻居，然后等其右邻居的msg 当它接收一个 msg 时，检验收到的 idj，若 idjidi，则 Pi转发 idj给左邻，否则没收 idj(不转发)。若某处理器收到一个含有自己标识符的 msg，则它宣布自己是 leader，并发送一个终止 msg 给左邻，然后终止。当一处理器收到一个终止msg时，向左邻转发此消息，然后作为non-leader终止。因为算法不依赖于 n，故它是均匀的。正确性正确性：只要分析出最终只有一个 Leader 被选中就行了 Msg 复杂性复杂性：若处理器按照 n-1,n-2,0,顺时针排列，顺时针转发 msg，则标号为 i的处理器的 msg 会被转发 i+1 次，最终的 Leader 又会向每个处理器转发通知（共 n次转发），则 Msg 复杂性=?E?:?E?E?s?;?L?:?J?6?;?5?4 时间复杂性时间复杂性：显然是 O(n)量级 3.3.2 K 邻居法：一个邻居法：一个?:?;算法算法 基本思想基本思想：每个局部Leader慢慢扩大自己的邻居范围，每经过一个阶段增长一倍的邻居。算法按阶段执行，在第 l 阶段一个处理器试图成为其 2l-邻接的临时 leader。只有那些在 l-th 阶段成为临时领袖的处理器才能继续进行到(l+1)th 阶段。因此，l 越大，剩下的处理器越少。直至最后一个阶段，整个环上只有一个处理器被选为 leader。在第i阶段的一开始，局部Leader向它的两边发送一个的msg，id 是局部 Leader 的 id，i 表示第 i 阶段，hop 表示经过的邻居数，也就是跳数。邻居分别沿路径转发 msg，每到达一个邻居，hop+。当到达 hop=2i时，就不再转发，邻居回答 reply，转发向局部 Leader，这样一个局部 Leader 在第 i 阶段最多会产生4*2i个 msg，之所以说最多，是因为有些局部 Leader 会被别的局部 Leader 吞并，这样它的 msg 就不会再被邻居转发或者 reply 正确性：因为具有最大 id 的处理器的 probe 消息是不会被任何结点没收的，所以该处理器将作为 leader 终止算法；另一方面，没有其他 probe 消息能够周游整个环而不被吞没。因此，最大 id 的处理器是算法选中的唯一的 leader。Msg 复杂度（最坏情况下）复杂度（最坏情况下）：在 phase i 里：?一个处理器启动的 msg 数目至多为：4*2i?有多少个处理器是启动者呢？i=0，有 n 个启动着（最多），则会产生 4n 个 msg i 1，在 i-1 阶段结束时成为临时 leader 的节点均是启动者。对每个 i 1，在 phase i 结束时，临时 leader 数至多为 n/(2i+1).在结束阶段，产生的总 Leader 会转发通知，产生 n 个 msg 则 msg 复杂度为：?v?E?v?t?6?7?-?5?E?J?Q?z?J?H?C?:?J?F?s?;?E?w?J?L?1?:?J?H?C?J?;?j?e?:?5?;?5 时间复杂度时间复杂度：只盯着最终 Leader 看，因为它最终成为 Leader 了算法才能结束。它从局部 Leader 走向最终 Leader，需要经过?个阶段，在第 i 个阶段，它至少需要经过 2*2i个时刻才能确认自己还保持着局部 Leader 的身份，最终再发送自己是终极 Leader 的通知，所以时间复杂度是?t?t?j?e?:?5?;?4?E?J?L?u?J?F?v?L?:?;3.3.3 下界下界?:?;基本思想基本思想：对于大小为 n 的环采用构造法，将两个大小为 n/2 的不同环粘贴在一起形成一个大小为 n 的环，将两个较小环上的耗费执行组合在一起，并迫使(n)个附加 msg 被接收，这样总的耗费就是 M(n)=2M(n/2)+(n)，这样的递归方程的解是M(n)=(nlgn)；开调度定义：设 是一个特定环上算法 A 的一个调度，若该环中存在一条边 e 使得在 中，边 e 的任意方向上均无 msg 传递，则 称为是开调度，e 是 的一条开边。具体方法见 PPT，过于繁琐，就是利用开调度构造出(n)=(n/2-1)/2。总体过程：1)在 R1 和 R2 上构造 2 个独立的调度，每个接收 2M(n/2)各 msg:1 2 2)强迫环进入一个静