no44.htm

常用经典算法及讲解

lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1 . 4</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>节和<span lang=EN-US>2</span></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><i><span lang=EN-US style='font-size:
5.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;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 / 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</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'>x</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</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 , 0 , 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'>( 0 , 1 , 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'>( 0 , 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;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>( 1 , 0 , 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'>( 0 , 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 , 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;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>( 1 , 1 , 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 , 1 , 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'>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 , 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'>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'>1 6
- 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'>0 /
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'>i </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'>i</span></i><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'>x </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'>i</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'>x</span></i><i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>i </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'>A</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'>H</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'>x</span></i><span lang=EN-US style='font-size:10.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= [ 1 , 1 ,
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'>w </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'>c </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 , 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 / 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'>A</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'>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'>expansion node</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'>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'>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'>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'>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'>E</span><i><span lang=EN-US style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>-</span></i><span