📄 road.htm
字号:
</td> </tr> <tr style='height:27.6pt'> <td width=58 style='width:43.3pt;border:solid windowtext .5pt;border-top: none;mso-border-top-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt; height:27.6pt'> <p class=MsoNormal align=center style='text-align:center'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family: "Times New Roman"'>兵</span></p> </td> <td width=58 style='width:43.3pt;border-top:none;border-left:none;border-bottom: solid windowtext .5pt;border-right:solid windowtext .5pt;mso-border-top-alt: solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt; height:27.6pt'> <p class=MsoNormal align=center style='text-align:center'><![if !supportEmptyParas]> <![endif]><span lang=EN-US><o:p></o:p></span></p> </td> <td width=58 style='width:43.3pt;border-top:none;border-left:none;border-bottom: solid windowtext .5pt;border-right:solid windowtext .5pt;mso-border-top-alt: solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt; height:27.6pt'> <p class=MsoNormal align=center style='text-align:center'><![if !supportEmptyParas]> <![endif]><span lang=EN-US><o:p></o:p></span></p> </td> <td width=58 style='width:43.35pt;border-top:none;border-left:none; border-bottom:solid windowtext .5pt;border-right:solid windowtext .5pt; mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt; padding:0cm 5.4pt 0cm 5.4pt;height:27.6pt'> <p class=MsoNormal align=center style='text-align:center'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family: "Times New Roman"'>兵</span></p> </td> </tr></table><p class=MsoNormal style='text-indent:21.0pt'><span lang=EN-US><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoNormal style='text-indent:21.0pt'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>棋盘的下部有两个空置的小格作为华容道的出口。棋子就在这个长方形的棋盘内滑动，滑动过程中棋子不允许重叠。华容道是一个比较复杂的游戏，要移动很多步才能完成。据有关资料介绍，对于上面的布局（华容道游戏还有多种布局），已知的最好走法是</span><spanlang=EN-US>81</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>步。</span></p><p class=MsoNormal><span lang=EN-US><span style="mso-spacerun:yes"> </span></span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>笔者采用双向广度优先搜索的方法搜索出在一定意义下最佳的解题步骤，并指导我系学生姚刚用</span><spanlang=EN-US>DELPHI V5.0</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>开发了一个相应的电脑游戏。本文首先介绍了该算法的基本思想，然后通过完整的</span><spanlang=EN-US>PASCAL</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>源程序及其注释给出该算法的具体的实现，最后给出搜索的结果。至于相应的电脑游戏，读者可从将在</span><spanlang=EN-US>2001</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>年</span><span lang=EN-US>10</span><spanstyle='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>月</span><span lang=EN-US>1</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>日之前开通的“信息学（计算机）奥林匹克”网站上找到，该网站是天津师范大学网站（</span><spanlang=EN-US>http://www.tjnu.edu.cn</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>）的二级网站。</span></p><p class=MsoNormal><span lang=EN-US><span style="mso-spacerun:yes"> </span></span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>二、算法简介</span></p><p class=MsoNormal style='text-indent:21.0pt'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>我们用一个</span><spanlang=EN-US>5*4</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>的数组来记录棋盘状态，用标号</span><span lang=EN-US>1-5</span><spanstyle='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，</span><span lang=EN-US>8</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，</span><spanlang=EN-US>9</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>来表示各个棋子，例如，初始状态可表示为</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>4<span style="mso-spacerun: yes"> </span>9<span style="mso-spacerun: yes"> </span>9<spanstyle="mso-spacerun: yes"> </span>5<span style="mso-spacerun:yes"> </span></span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>4<span style="mso-spacerun: yes"> </span>9<span style="mso-spacerun: yes"> </span>9<spanstyle="mso-spacerun: yes"> </span>5<span style="mso-spacerun:yes"> </span></span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>2<span style="mso-spacerun: yes"> </span>8<span style="mso-spacerun: yes"> </span>8<spanstyle="mso-spacerun: yes"> </span>3<span style="mso-spacerun:yes"> </span></span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>2<span style="mso-spacerun: yes"> </span>1<span style="mso-spacerun: yes"> </span>1<spanstyle="mso-spacerun: yes"> </span>3<span style="mso-spacerun:yes"> </span></span></p><p class=MsoNormal style='text-indent:21.0pt'><span lang=EN-US><spanstyle="mso-spacerun: yes"> </span>1<span style="mso-spacerun: yes"> </span>0<span style="mso-spacerun: yes"> </span>0<spanstyle="mso-spacerun: yes"> </span>1</span></p><p class=MsoNormal style='text-indent:21.0pt'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>（单向）广度优先搜索是大家熟知的算法，其基本步骤如下：</span></p><p class=MsoNormal style='margin-left:37.2pt;text-indent:-16.2pt;mso-list:l0 level1 lfo2;tab-stops:list 37.2pt'><![if !supportLists]><span lang=EN-US>1．<spanstyle='font:7.0pt "Times New Roman"'> </span></span><![endif]><spanstyle='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>将初始结点入队。队头指向该结点，队尾指向该结点之后。</span></p><p class=MsoNormal style='margin-left:39.6pt;text-indent:-18.0pt;mso-list:l1 level1 lfo3;tab-stops:list 39.6pt;layout-grid-mode:char;mso-layout-grid-align:none'><![if !supportLists]><spanlang=EN-US>2．<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]><spanstyle='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>将队头结点出队，生成所有可能的扩展结点，队头指向下一个结点。如果某个新生成的结点已符合目标则结束，否则通过比较，将与已在队列中的结点不重复的新结点入队。队尾指向新结点之后。</span></p><p class=MsoNormal style='margin-left:39.6pt;text-indent:-18.0pt;mso-list:l1 level1 lfo3;tab-stops:list 39.6pt'><![if !supportLists]><span lang=EN-US>3．<spanstyle='font:7.0pt "Times New Roman"'> </span></span><![endif]><spanstyle='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>重复</span><span lang=EN-US>2</span><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>，直到某个结点符合目标或队列空（即队尾位于队头之前）为止。</span></p><p class=MsoNormal style='text-indent:21.0pt'><span style='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>我们采用的双向广度优先搜索是指建立两个队列，分别从初始状态和目标状态出发进行搜索，直到遇到一个共同的结点（状态）为止。与单向搜索相比，其效率要高得多。但这一方法必须要事先知道目标状态。实际计算表明，与单向搜索相比，我们的双向搜索方法可节省一半的空间，而时间不到前者的一半。因而是一个很有效的算法。</span></p><p class=MsoPlainText style='text-indent:21.0pt'>从理论上讲，广度优先搜索得到的结果在某种确定的意义下应该是最优的。</p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>三、PASCAL源程序及其注释</span></p><p class=MsoPlainText><span lang=EN-US>program road;{用 PASCAL7.0<spanstyle="mso-spacerun: yes"> </span>BP（大内存模式）运行，不要用TURBO运行}</span></p><p class=MsoPlainText><span lang=EN-US>const<span style="mso-spacerun:yes"> </span>range2=6000;{搜索队列的最大结点数}</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>b1=[2,3,4,5];</span></p><p class=MsoPlainText><span lang=EN-US>type</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>arr1=array [0..6,0..5] of byte;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>arr2=array [1..5,1..4] of byte;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>node_sd=record{标准结点，采用小数组arr2，用于主队列存储结点}</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>parent:integer; {存放父结点编号}</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>i1,j1,i2,j2:byte;{存放空格坐标}</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>arr:arr2; {存放结点状态}</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>end;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>node_ext=record {扩展结点，采用加边的大数组arr1，用于工作结点，可减少对边缘的判断}</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>parent:integer;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>i1,j1,i2,j2:byte;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>arr:arr1;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>end;</span></p><p class=MsoPlainText><span lang=EN-US>var</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>queue,queue2:array [0..range2] of ^node_sd;{搜索队列，分别从源点与目标点出发}</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>work,work2:arr1;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>pp,qhead,qend,qhead2,qend2:integer;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>node2:node_ext;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>fname:string;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>f1:text;</span></p><p class=MsoPlainText><span lang=EN-US>procedure ext_to_sd(node0:node_ext; varnode3:node_sd); forward;</span></p><p class=MsoPlainText><span lang=EN-US>procedure prtnode(node3:node_ext);forward;</span></p><p class=MsoPlainText><span lang=EN-US>procedure sd_to_ext(node0:node_sd;varnode3:node_ext); forward;</span></p><p class=MsoPlainText><span lang=EN-US><![if !supportEmptyParas]> <![endif]><o:p></o:p></span></p><p class=MsoPlainText><span lang=EN-US>procedure<span style="mso-spacerun:yes"> </span>initwork;<span style="mso-spacerun: yes"> </span>{No.1初始化}</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>var i,j:integer;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes"> </span>begin {1}</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>writeln('Input file name for result...');</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>readln(fname);</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>assign(f1,fname);</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>rewrite(f1);</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span><span style="mso-spacerun:yes"> </span>qhead:=0;<span style="mso-spacerun: yes"> </span>qend:=1;<span style="mso-spacerun: yes"> </span>qhead2:=0;<spanstyle="mso-spacerun: yes"> </span>qend2:=1;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>for i:=0 to 6 do</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>for j:=0 to 5 do</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>work[i,j]:=20;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>for i:=1 to 2 do<span style="mso-spacerun:yes"> </span>{源点状态}</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>begin</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>work[i,1]:=4;work[i,2]:=9; work[i,3]:=9; work[i,4]:=5;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>end;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>work[3,1]:=2; work[3,2]:=8; work[3,3]:=8;work[3,4]:=3;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>work[4,1]:=2; work[4,2]:=1; work[4,3]:=1;work[4,4]:=3;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:yes"> </span>work[5,1]:=1; work[5,2]:=0; work[5,3]:=0;work[5,4]:=1;</span></p><p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -