no55.htm

常用经典算法及讲解

lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>17-1c </span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>所示。此时队列中包含（</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）和（</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）两个节点。随后节点（</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）变成下一个</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>E</span><span lang=EN-US style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-节点，由于此节点不能到达任何新的节点，所以此节点即被删除，节点（</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）成为新的</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>E</span><span lang=EN-US style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-节点，将队列清空。节点（ </span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）展开，（</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>2</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）被加入队列中，而（</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）被删除。（</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>2</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）变为新的</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>E</span><span lang=EN-US style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-节点，展开此节点后，到达节点（</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>3</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>），即迷宫的出口。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:20.0pt;
mso-char-indent-count:2.0;mso-char-indent-size:10.0pt;mso-layout-grid-align:
none;text-autospace:none'><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>使用</span><span lang=EN-US style='font-size:
10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>F I
F O</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>搜索，总能找出从迷宫入口到出口的最短路径。需要注意的是：利用回溯法找到的路径却不一定是最短路径。有趣的是，程序</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>6 - 11</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>已经给出了利用</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>F I F O</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>分枝定界搜索从迷宫的（</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）位置到（</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>n</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>n</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;mso-ascii-font-family:"Times New Roman";color:black;
mso-font-kerning:0pt'>）</span><span style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'> </span><span style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>位置的最短路径的代码。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:20.0pt;
mso-char-indent-count:2.0;mso-char-indent-size:10.0pt;mso-layout-grid-align:
none;text-autospace:none'><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>例<span lang=EN-US>5</span></span><span
lang=EN-US style='font-size:10.0pt;font-family:Arial;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>-2 [0/1</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>背包问题</span><span lang=EN-US style='font-size:10.0pt;font-family:Arial;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>] </span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>下面比较分别利用</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>F I F O</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>分枝定界和最大收益分枝定界方法来解决如下背包问题：</span><i><span lang=EN-US style='font-size:10.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n</span></i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>=3, <i>w</i>=[20,15,15], <i>p</i>=[40,25,25],
<i>c</i>= 3 0</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>。</span><span lang=EN-US style='font-size:
10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>F I
F O</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>分枝定界利用一个队列来记录活节点，节点将按照</span><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>F I F O</span><span style='font-size:10.0pt;font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>顺序从队列中取出；而最大收益分枝定界使用一个最大堆，其中的</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>E</span><span lang=EN-US style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-节点按照每个活节点收益值的降序，或是按照活节点任意子树的叶节点所能获得的收益估计值的降序从队列中取出。本例所使用的背包问题与例</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1 6 . 2</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>相同，并且有相同的解空间树。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;mso-layout-grid-align:
none;text-autospace:none'><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>使用</span><span lang=EN-US style='font-size:
10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>F I
F O</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>分枝定界法搜索，初始时以根节点</span><span lang=EN-US style='font-size:
10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>A</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>作为</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>E</span><span lang=EN-US
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>-节点，此时活节点队列为空。当节点<o:p></o:p></span></p>

<p class=MsoNormal align=left style='text-align:left;mso-layout-grid-align:
none;text-autospace:none'><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>A</span><span style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>展开时，生成了节点</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>B</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>和</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>C</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，由于这两个节点都是可行的，因此都被加入活节点队列中，节点</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>A</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>被删除。下一个</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>E</span><span lang=EN-US style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-节点是</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>B</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，展开它并产生了节点</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>D</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>和</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>E</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>D</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>是不可行的，被删除，而</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>E</span><span style='font-size:10.0pt;