no55.htm

常用经典算法及讲解

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;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'>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;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 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'>F I F O</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 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'>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;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'>-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'>16-3a </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 6 - 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'>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><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 , 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'>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'>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'>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'>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'>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'>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'>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'>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'>1 7 - 1 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'>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 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'>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'>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'>1 6 - 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'>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'>17-1b </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'>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'>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'>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'>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'>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'>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'>1</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>）被删除，所得到的迷宫如图</span><span