no44.htm

常用经典算法及讲解

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.1pt;
mso-char-indent-count:2.0;mso-char-indent-size:10.05pt;mso-layout-grid-align:
none;text-autospace:none'><b><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>例<span lang=EN-US>4</span></span></b><b><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></b><b><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>迷宫老鼠</span></b><b><span lang=EN-US style='font-size:10.0pt;font-family:
Arial;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>] </span></b><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'>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 6 -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 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 , 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 , 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 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 , 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 , 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 , 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><i><span lang=EN-US style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-</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'>m a z e</span></i><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 , 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 , 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'>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'>( 1 , 2 )</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'>m a z e</span></i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>( 1 , 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'>16-3b </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,1) (1,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 , 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><i><span lang=EN-US style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-</span></i><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 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'>E</span><i><span
lang=EN-US style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>-</span></i><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 , 3 )</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'>m a z e</span></i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>( 1 , 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 6 - 3 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'>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 , 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><i><span lang=EN-US style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-</span></i><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 , 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 , 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 , 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><i><span lang=EN-US style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-</span></i><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 , 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 , 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 , 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 , 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 , 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 , 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 , 1 )</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning: