第10章竞赛树

1、第10章 竞赛树学习内容m竞赛树q完全二叉树，高效替换最大（小）元q按指定的方式断开连接m胜者树、败者树m应用：装箱问题（bin packing）10.1 引言mn个选手进行乒乓球淘汰赛m最终剩下一名胜者竞赛优胜者胜者树m将比赛用树的结构来描述m外部节点选手，内部节点比赛结果mwinner tree：内部节点记录胜者m竞赛树选择树（selection tree）定义m定义胜者树：对于n 名选手，胜者树是一棵含n 个外部节点，n1个内部节点的完全二叉树，每个内部节点记录了相应赛局的胜者胜者树例胜者树的修改m选手d的得分发生改变q他与c的比赛结果可能改变若改变，与a的比赛结果也可能改变q需修改d根

2、路径上的节点，遇到比赛结果未变的节点即停止qO(logn)mn个选手n-1场比赛初始化Q(n)例10-1排序m最小胜者树， Q(nlogn)qn个元素n名选手，初始化胜者树q元素的值较小胜q最后的胜者最小值元素q将该选手（元素）的值改为最大值(如)必败，重构该赢者树最终胜者为次大元素例10-1排序q重复，可以完成n个元素的排序q初始化时耗为Q(n)q每次改变胜者的值并重构胜者树的Q(logn)，共n-1次，排序总时间为(nlogn)例10-2外部排序m外部排序q数据集过大，无法全部放在内存中q一部分、一部分地放在内存中处理、排序q产生部分排序结果runq将若干run合并在一起得到最终的run例

3、10-2外部排序m16000个数据q内存中一次可排序1000个数据（一个run）q生成16个runq将这16个run 4个4个地合并，5个步骤后就合并为单一的run合并run的方法m合并k个runq从k个run的前面不断移出元素（各个run中最小值），选择其中最小的（所有未处理数据中最小的），放入输出run中q当所有数据都移入到输出run中，则结束q最少需要多少内存？实际合并run的例子m上例q16000个数据，每个run 1000个数据q合并4个run，内存分为5个缓冲区，4个输入，1个输出，均为200个数据大小q不断从输入缓冲区读取数据，放入输出缓冲区输出缓冲区已满写入磁盘，继续合并某个输

4、入缓冲区空，读取输入run，继续合并q4000个数据都写入输出run，合并结束利用胜者树生成runmn个数的序列，逐个扫描，构造run1.p个选手的胜者树，选手输入元素2.选手得分 值（元素值） run号（前p个选手均为1）3.胜负判定 先比较run号，较小者胜 run号相同，值小者胜利用胜者树生成run4.重复以下步骤1) 将最终胜者W放入run中，哪个run？它的run号所指定的那个2) 在输入序列中选取下一元素N取代W若其值大于等于W，设置相同run号否则，run号设为W的run号加1重构胜者树qrun的平均长度为2p为什么？利用胜者树进行k路合并m每产生一个输出run元素k个输入run

5、元素寻找最小值：O(kn)m利用胜者树求最小值：Q(k+nlogk)10.2 胜者树抽象数据类型抽象数据类型WinnerTree实例完全二叉树，每个节点代表相应比赛的赢者，外部节点代表选手操作Create()：创建一个空的赢者树Initialize(a, n)：对有n个选手a1:n的赢者树进行初始化Winner()：返回比赛的赢者Replay(i)：选手i变化时，重组赢者树10.3 胜者树的实现10.3.1 定义m特殊完全二叉树公式化描述q选手e1:nq胜者树内部节点t1:n-1ti内容：胜者数组e的索引树和数组元素的对应关系关键：寻找父节点m外部节点ei，确定其父节点tpq内部节点最底层最左

6、节点编号2s，s=q最底层内部节点数目n-2sq最底层外部节点数目LowExt=(n-2s)*2) 1(log2n关键：寻找父节点qi：完全二叉树统一编号映射为父节点p编号q最终公式为LowExtinLowExtiLowExtiips),1(, 2/ )21(110.3.2 公式化描述的实现templateclass WinnerTree public: WinnerTree(int TreeSize = 10); WinnerTree() delete t; void Initialize(T a, int size, int(*winner)(T a, int b, int c); int

7、 Winner() const return (n) ? t1 : 0; int Winner(int i) const return (i n) ? ti : 0; void RePlay(int i, int(*winner) (T a, int b, int c); void Output() const;WinnerTree类（续） private: int MaxSize; int n; / current size int LowExt; / lowest-level external nodes int offset; / 2k - 1 int *t; / array for w

8、inner tree T *e; / element array void Play(int p, int lc, int rc, int(*winner)(T a, int b, int c);10.3.3 构造函数templateWinnerTree:WinnerTree(int TreeSize)/ Constructor for winner tree. MaxSize = TreeSize; t = new intMaxSize; n = 0;10.3.4 初始化胜者树m接受函数指针winnerq比较两个元素间的胜者q用户提供，可实现不同的比赛规则构造胜者树m依次扫描所有外部节点（选

9、手），调用Play（比赛）q两个外部节点（或有一个内部节点）比赛，构造出最底层内部节点q若新节点为其父的右孩子，则与其兄弟比赛，构造父节点左孩子必然已构造完重复此步骤，直至新节点为左孩子或到达根节点（整个胜者树构造完毕）初始化函数templatevoid WinnerTree:Initialize(T a, int size, int(*winner)(T a, int b, int c)/ Initialize winner t for array a. if (size MaxSize | size 2) throw BadInput(); n = size; e = a; / compu

10、te s = 2log (n-1) int i, s; for (s = 1; 2*s = n-1; s += s);初始化函数（续） LowExt = 2*(n-s); offset = 2*s-1; / play matches for lowest-level external nodes for (i = 2; i = LowExt; i += 2) Play(offset+i)/2, i-1, i, winner);初始化函数（续） / handle remaining external nodes if (n % 2) / special case for odd n, play

11、/ internal and external node Play(n/2, tn-1, LowExt+1, winner); i = LowExt+3; else i = LowExt+2; / i is left-most remaining external node for (; i = n; i += 2) Play(i-LowExt+n-1)/2, i-1, i, winner);比赛函数templatevoid WinnerTree:Play(int p, int lc, int rc, int(*winner)(T a, int b, int c)/ Play matches

12、beginning at tp. / lc and rc are the children of tp. tp = winner(e, lc, rc); / more matches possible if at right child while (p 1 & p % 2) / at a right child tp/2 = winner(e, tp-1, tp); p /= 2; / go to parent 10.3.5 重构胜者树templatevoid WinnerTree:RePlay(int i, int(*winner)(T a, int b, int c)/ Replay m

13、atches for element i. if (i n) throw OutOfBounds(); int p, / match node lc, / left child of p rc; / right child of p / find first match node and its children if (i = 1; p /= 2) tp = winner(e, t2*p, t2*p+1);10.4 败者树m胜者树的重构q总是前一次的最终胜者被取代q沿外部节点根重构，需上次比赛败者与新选手比较q但胜者树记录的是胜者，还需访问孩子节点重构低效例f变为5找到父节点1，判断是否需要

14、修改，需要与e重新比赛，但1保存的是上次的胜者f如果节点1的结果改变，则需找到父节点2，需要与节点4重新比赛，但2保存的是1而不是41234败者树（续）m内部节点保存败者，t0最终胜者m重构时，直接提取节点指向元素，与新元素进行比赛f变为510.5 应用m装箱（bin packing）问题q若干个容量为c的箱子和n个物品q物品i的体积为si（0sic）q可行装载（feasible packing）：将物品都装入箱子而不溢出q最优装载（optimal packing）：使用箱子数目最少的可行装载装箱问题应用实例m卡车装载q运输公司需把包裹装入卡车，每个包裹都有一定重量，每辆卡车也有载重限制q希望

15、用最少的卡车来装载包裹q卡车箱子，包裹物品装箱问题应用实例m集成片分布q给定宽度的电路板上按行布设些电路集成片q集成片高度一致但宽度各不相同q电路板的每行箱子，集成片物品q电路板的宽度箱子容量，集成片长度物品体积NP-完全性介绍m不可判定问题（undecidable problem）q停机问题（halting problem）：令编译器具有检查无限循环的能力q编译器也是程序，具有检查无限循环能力的编译器很难检查自身q递归不可判定的（recursively undecidable）递归不可判定问题m具有检查无限循环能力的编译器q将这个编译器程序称为LOOPq将任意程序P输入LOOP，LOOP执行

16、P，若P无限循环，LOOP输出YES，否则LOOP无限循环q如果将LOOP输入LOOP，会怎么样？如果LOOP(LOOP)停止，则LOOP含无限循环，矛盾如果LOOP(LOOP)无限循环，则LOOP应停止，矛盾类似“这句话是一句谎话”的矛盾不存在这样的程序LOOP！确定型和非确定型机器m确定型机器：每一时刻执行一条指令，然后下一步执行的指令是惟一确定的m非确定型机器：下一步执行的指令是有选择的，机器有能力自由选择导致正确解的指令m前者：目前的标准计算机后者：难以实现的NP类和P类mNP类：非确定型多项式时间，nondeterministic polynomial-timeP类：确定型多项式时间

17、，deterministic polynomial-timemP类问题：目前的计算机可多项式时间求解NP类：不知道！问题属于NP类的检验m用Yes/No描述问题q多项式时间内，能证明一个问题的任意“是”的实例是正确的，则该问题属于NP类m汉密尔顿圈问题q给定一条路径，判定它是否汉密尔顿圈m验证答案较之计算答案容易q是否存在不具有多项式时间解法的问题尚未发现m不是所有可判定问题都属于NP：证明一个图没有汉密尔顿圈NP-完全问题mNP类的子集：NP中最难的问题，NP-completemNP中任一问题都能够多项式地归约为NP-完全问题m问题P1归约为问题P2：存在映射，使得P1的任何实例都可以变换为

18、P2的实例NP-完全问题m“最难的”原因q变换NP-完全问题可作为NP中任何问题的子程序，开销为多项式时间qNP完全问题存在多项式时间解，NP中每个问题必然存在多项式时间解mP1为NP-完全问题，P2为NP类，若P1可多项式地归约为P2，P2也是NP-完全问题旅行商问题是NP-完全问题mtraveling salesman problemm问题：给定一完全图G=(V, E)、边的权值以及整数K，是否存在一个访问所有顶点且权值和=K的简单圈？m汉密尔顿圈问题是NP-完全问题，且可以多项式地归约为旅行商问题，因此旅行商问题是NP-完全问题归约方法m对图G，构造完全图G，V=Vm对(v, w)E，G

19、中其权值设定为1，否则设定为2m另选取K=|V|m则G存在汉密尔顿圈G存在总权值为|V|的旅行商巡回路线归约例第一个NP-完全问题m可满足性问题（satisfiability）：一个布尔表达式作为输入，要求回答是否可以通过式中变量取值使得表达式为真m1971年，Cook证明了SAT是NP-完全的qNP中每个问题都可用一台非确定型机器（图灵机）在多项式时间内求解q而此机器的动作可用一个及其复杂但仍是多项式的布尔表达式模拟，表达式为真图灵机输出为“是”近似解法mNP-完全问题，4种常见近似算法1)最先匹配法（First Fit，FF) 箱子任意排序，依次将物品放入箱子，每个物品放入第一个可容纳它的

20、箱子2)最优匹配法（Best Fit，BF） 数组Avail保存箱子当前可用容量，物品放入可容纳它，且Avail值最小的箱子近似解法3)最先匹配递减法（First Fit Decreasing，FFD） 类似FF，但物品首先按体积递减顺序排序4)最优匹配递减法（Best Fit Decreasing，BFD） 类似BF，但物品首先按体积递减顺序排序mI：装箱问题实例，b(I)：最优解qFF、BF(17/10)b(I)FFD、BFD(11/9)b(I)+4例10-6m四件物品s1:4=3,5,2,4，箱子容量7qFF，箱子初始容量7, 7, 7, 7物品1放入箱子1，箱子容量4, 7, 7, 7

21、物品2放入箱子2，箱子容量4, 2, 7, 7物品3放入箱子1，箱子容量2, 2, 7, 7物品4需再用一个箱子共需3个箱子例10-6qBF物品1放入箱子1，箱子容量4, 7, 7, 7物品2放入箱子2，箱子容量4, 2, 7, 7物品3放入箱子2，箱子容量4, 0, 7, 7物品4又可放入箱子1两个箱子qFFD和BFD首先将物品按2、4、1、3排序最后方案均为：使用两个箱子，物品2、3放入箱子1；物品1、4放入箱子2例10-6qBF物品1和2分别放入箱子1和箱子2；物品3放入箱子2，物品4又可放入箱子1两个箱子qFFD和BFD首先将物品按2、4、1、3排序最后方案均为：使用两个箱子，物品2、

22、3放入箱子1；物品1、4放入箱子2利用胜者树实现FF和FFDm最多n个箱子，初始n个空箱子m所有availj=c，将其作为选手构造最大胜者树m对每个物品i，寻找第一个（最左的）可容纳它的箱子利用胜者树实现FF和FFD（续）q从根开始，对当前节点j，考虑其孩子l、ravailtlsi：左子树最大可用容量大于等于i的体积有箱子可容纳i，转向左子树继续搜索availtrsi：转向右子树继续搜索左、右子树都无箱子可容纳i，失败q直至外部节点，将物品放入对应箱子，重构胜者树mQ(nlogn)例s1=8例（续）s2=6s3=5FirstFit函数void FirstFitPack(int s, int n

23、, int c)/ Output first fit packing into bins of size c. / n is the number of objects and s their size. WinnerTree *W = new WinnerTree (n); int *avail = new int n+1; / bins / initialize n bins and winner tree for (int i = 1; i Initialize(avail, n, winner);FirstFit函数（续） / put objects in bins for (i =

24、1; i = n; i+) / put si in a bin / find first bin with enough capacity int p = 2; / 从根节点的左孩子开始搜索 while (p Winner(p); if (availwinp si) / 当前节点子树中无箱子可容纳物品i p+ ; / 因此转到它的兄弟父节点的右子树继续搜索 p *= 2; /转到当前节点的孩子继续搜索，也是从左孩子开始 int b; / will be set to bin to use p /= 2; / 当前p为外部节点，转到其父节点while循环中 / 最后处理的那个节点FirstFit

25、函数（续） if (p Winner(p); / b为胜者，可能是右孩子，需检查箱子b-1（左孩子） / 当然b也可能是左孩子，但这种检查不会导致错误 if (b 1 & availb-1 = si) b-; else / p=n：n为奇数，while最后一次检查节点n-1，不能容纳i b = W-Winner(p/2); / 转到p(n)外部节点，需查其父 / 节点，获取胜者节点p在avail中位置 cout Pack object i in bin b RePlay(b, winner); 循环匹配法mb个箱子看作一个环m物品i放入箱子jm物品i+1从箱子(j+1)%b开始，寻找第一个可容纳它的箱子m若未找到，启用一个新箱子，bb+1循环匹配法例m6个物