宽度讲义1.doc

飞扬奥赛信息学奥林匹克精英教育 宽度搜索 第5页共5页八数码问题 个编有数码的滑牌，能在的井字格中滑动。井字格中总有一格是空格，用表示，因而空格周围的数码滑牌都可能滑到空格中去。下图是数码滑牌在井字格中的两种状态：283123164804705765初始状态目标状态 以左图为初始状态，右图为目标状态，找出从初始状态到目标状态的滑牌移步序列，具体要求：（）输入初始状态和目标状态的数据；（不用检验输入）、分别以两行输入上述两项数据： 例：Enter the initial state:2 8 3 1 6 4 7 0 5 Enter the final state:1 2 3 8 0 4 7 6 5 （）实现从初始状态到目标状态的转换（初始状态一定能按规则移动到目标状态）； （）输出结果，每移动一步都必须在屏幕上显示； 、移动每一步时的序号，最后一步的序号即为移动总步数； 、每一步移动后以表格形式显示状态。 （）要求能使移动步数尽可能少。题意分析：1、棋盘的初始状态、目标状态。如图初始状态目标状态2 8 3 1 2 31 6 4 8 0 47 0 5 7 6 5输入不必查错2、移动规则0 表示空位，规则空位可以上、下、左、右，注意边界。3、棋盘从初始状态移动到目标状态最少移动步骤。求解分析从初始状态出发，按规则生成全部移动一步的布局；检查此布局是否已生成（已生成则放弃此布局）检查是否为目标状态，是则打印步骤。不是再从移动一步的所有布局出发，生成全部移动两步的所有布局，做如上检查，直至到达目标状态。按此方法到达目标状态的解一定是步骤最少的解。如图1、建立产生式系统产生式系统即数据与操作。也就是此题的棋盘和规则。1）结点描述棋盘描述3*3的棋盘，用二维数组表示。记录空位的位置，省去查找空位。记录此布局的由来，即父指针。2）移动规则空位上下左右移动。偏移量：1.上x行：-1y列：02.右x行：0y列：13.下x行：1y列：04.左x行：0y列：-1注意棋盘越界3）结点存储所有生成的结点存储在队列中，一维数组描述队列，Open指针表示队列的首指针，Closed指针表示队列的尾指针。宽度框架1、数据描述棋盘定义Type arr1 = Array1.3,1.3Of Integer;结点定义Type node = Record gh:arr1;棋盘x, y: Integer;空位位置p: Integer;父指针End;队列定义Type Work_Type = Array1.1000 Of node; 队列的长度初始状态、目标状态ConstStart: arr1 = (2,8,3),(1,6,4),(7,0,5);Finish: arr1 = (1,2,3),(8,0,4),(7,6,5); 规则定义Constdx: Array1.4Of -1.1 = (-1, 0, 1, 0);dy: Array1.4Of -1.1 = ( 0, 1, 0, -1);变量说明Work: Work_Type; Open, Closed: Integer;队列指针2、程序框架1)将初始状态放入队列With Work1 Do Begin gh := Start; x := 3; y := 2;空位位置 p := 0;父指针为0End;2)置指针Open := 1; Closed := 0;3)宽度扩展每层结点Repeat Inc(Closed); For I:=1 To 4 Do Beginnx := WorkClosed.x + dxI;ny := WorkClosed.y + dyI; 计算空位移动的位置If nx, ny 在界内 Then Begin Inc(Open);准备接受新结点 生成新布局WorkOpen.gh := WorkClosed.gh;s := WorkClosed.ghnx, ny;WorkOpen.ghWorkClosed.x, WorkClosed.y := s;WorkOpen.ghnx, ny := 0;记录空位位置WorkOpen.x := nx; WorkOpen.y := ny;设置父指针WorkOpen.p := Closed;If WorkOpen.gh布局在队列Work1.Open-1中Then Dec(Open) 放弃此结点Else If WorkOpen.gh布局与目标一致 Then 打印End; End;Until Open = Closed;4）判重编写函数判断两布局一致Function Same(a, b: arr1):Boolean;Var I, j: Integer; 局部变量Begin Same := True; 首先认为a, b布局一致 For I:=1 To 3 Do For j:=1 To 3 Do If aI, j bI, j Then BeginSame := False;Exit; End;End;5、判断WorkOpen.gh是否在队列中Function Exist(Open: Integer):Boolean;Var I: Integer;局部变量Begin Exist := False; 认为Open 志向的布局不在1-(Open-1)中 For I:=1 To Open-1 Do If Same(WorkOpen.gh, WorkI.gh) Then Begin Exist := True;Exit;End;End;6、打印首先统计出路径中的结点位置（利用父指针）Procedure Print;Var s: Array1.100Of Integer; 存放路径中结点位置的数组 I, j: Integer;Begin I := 0; j := Open; RepeatInc(i);SI := j;j := Workj.p; Until j = 0; For j:=I DownTo 1 Do Show(sj);End;显示棋盘Procedure Show(k: Integer);Var I, j: Integer;Begin For I:=1 To 3 Do BeginFor j:=1 To 3 Do Write(Workk.ghI, j:4);WriteLn; End;End;注意：输出解后停止程序算法复杂度分析1、时间复杂度目标状态处在解答树的深度；棋盘判重时间（二维数组判重）；新结点在队列中查找时间2、空间复杂度结点的描述Type arr1 = Array1.3,1.3Of Byte;node = Recordgh: arr1;棋盘x, y: Byte;空位位置p: Integer;父指针End;结点的生成速度 4dep成指数增长空间复杂度是此算法的主要矛盾。队列中的结点少了可以提高查找时间。算法优化根据算法分析可以作如下针对性的优化空间复杂度树的深度是决定空间复杂度的主要问题利用双向宽度可以减少结点的数量，提高空间、时间效率。双向宽度是从初始状态和目标状态同时出发求解如解在树的n层上单向： T1=40+41+4N-1 结点个数双向： T2=2*（40+41+4(N-1)/2）N分奇偶 结点个数双向的结点数远远小于单向如：N=5;T1=1+4+16+64+256=3