eightnumberfrm.~pas

此软件是八数码软件

     row,col : integer;  //空格移动后，空格的新坐标
     SameNumber : integer;   //有结点与新增结点相同，则为该结点的下标，否则为0
     find : boolean;  //找到路径达到目标状态
begin
   //初始化
   min := 1000;
   find := False;
   AStarQueueTop := 1; //AStarQueueTop是全局变量，表示当前结点在数组Queue中的下标
   ChooseNumber := 0;

   //清空AStar1Path或者AStar2Path数组
   if ( method = 1) then
   begin
       for i := 1 to 100 do
       begin
           AStar1Path[i] := 0;
       end;
   end //end of if ( method = 1)

   else  //( method = 2 )
   begin
       for i := 1 to 100 do
       begin
           AStar2Path[i] := 0;
       end;
   end; //end of else ( method = 2 )


   //***************************
   ///////////A星算法///////////
   //***************************
   while ( ( not find ) and ( AStarQueueTop < High( Queue ) ) ) do
   begin
      //*********************************************
      //在Open表中寻找评价函数value值最小的结点
      //将评价函数value的最小值存入min中
      //将结点下标存入ChooseNumber中，
      //下面将展开ChooseNumber结点
      //*********************************************
      for i := 1 to AStarQueueTop do
      begin
        if ( (Queue[i].value < min) and (Queue[i].flag = 0) )  //(Queue[i].flag = 0)表示结点i在Open表中
        then begin
                ChooseNumber := i;
                min := Queue[i].value;
             end;
      end;//end of for i

      //******************************************************************************************
      //
      //如果即将要展开的结点是目标结点，则算法结束
      //如果新增的结点是目标结点，算法依然继续
      //这是因为在以后,由于指针的调整，有可能会使得结点的耗散值减少
      //而要展开结点时，此结点的耗散值不会再减少
      //所以，如果即将要展开的结点是目标结点，则表明已经找到了通向目标结点的耗散值最少的路径，算法结束
      //
      //
      //调用IsTarget函数判断将要展开的ChooseNumber结点是否目标结点
      //如果是目标结点则返回True，否则返回False
      //
      //******************************************************************************************
      if IsTarget( ChooseNumber ) then
      begin
          find := True;
          break;   //exit for while
      end; //end of if IsTarget( ChooseNumber )----判断将要展开的ChooseNumber结点是否目标结点

      Queue[ChooseNumber].flag := 1;//将结点ChooseNumber放入Close表中
      min := 1000; //重置min为1000，留待下一次循环时使用

      ChooseX := Queue[ChooseNumber].x;  //取出展开节点的空格的行坐标
      ChooseY := Queue[ChooseNumber].y;  //取出展开节点的空格的列坐标

      for k := 1 to 4 do
      begin
         row := ChooseX + MoveX[k];         //row和col表示空格移动后，空格的新坐标
         col := ChooseY + MoveY[k];         //k从1到4分别表示空格向上、左、下、右移动

         //以下if的判断条件是判断空格是否可以向上、左、下、右移动
         if ( (row >= 1) and (row <= 3) and (col >= 1) and (col <=3) ) then
         begin
             AStarQueueTop := AStarQueueTop +1;  //新增一个结点
             //////通过展开的结点ChooseNumber设置新增结点AStarQueueTop的8个数字和空格位置
             ////先将结点ChooseNumber的8个数字和空格位置复制到结点AStarQueueTop中
             for i := 1 to 3 do
             begin
                for j := 1 to 3 do
                begin
                   Queue[AStarQueueTop].status[i,j] := Queue[ChooseNumber].status[i,j]
                end;//end of for j
             end;//end of for i
             ////再修改因为空格移动而造成的两个结点的不同之处
             Queue[AStarQueueTop].status[ChooseX,ChooseY] := Queue[ChooseNumber].status[row,col];
             Queue[AStarQueueTop].status[row,col] := 0;

             //*********************************************
             //调用AStarExist函数判断新增结点是否在之前已经生成
             //如果之前已经生成则返回已经生成的结点的下标
             //如果还没有生成则返回0
             SameNumber := AStarExist();

             (***********************************************************
             ****************新增结点在之前并没有已经生成****************
             ***********************************************************)
             if (SameNumber = 0) then     //新增结点在之前并没有已经生成
             begin
                 //////设置新增结点AStarQueueTop的空格的行列坐标
                 Queue[AStarQueueTop].x := row;
                 Queue[AStarQueueTop].y := col;

                 //////设置新增结点AStarQueueTop的空格的指针指向
                 Queue[AStarQueueTop].prior := ChooseNumber;

                 //////设置新增结点AStarQueueTop的评价函数的值
                 if ( method = 1 )
                 then Queue[AStarQueueTop].value := FValue1( AStarQueueTop )
                 else Queue[AStarQueueTop].value := FValue2( AStarQueueTop );

                 //////将新增结点AStarQueueTop放入Open表
                 Queue[AStarQueueTop].flag := 0;

                 //////**********以下初始化新增结点的parent和parentcount域**********
                 //////将新增结点的parentcount设置为0
                 Queue[AStarQueueTop].parentcount := 0;
                 //////将新增结点的parent数组的所有元素初始化为0
                 for i := 1 to 4 do
                 begin
                     Queue[AStarQueueTop].parent[i] := 0;
                     end;//end of for i
                 //////**********以上初始化新增结点的parent和parentcount域**********



                 //////////////以下设置新增结点的parent和parentcount域//////////////
                 //将parentcount加1，表示多一个父亲
                 Queue[AStarQueueTop].parentcount := Queue[AStarQueueTop].parentcount + 1;
                 //////将父亲结点的下标ChooseNumber存入AStarQueueTop的parent数组中，表示ChooseNumber是AStarQueueTop的父亲
                 Queue[AStarQueueTop].parent[Queue[AStarQueueTop].parentcount] := ChooseNumber;
                 //////////////以上设置新增结点的parent和parentcount域//////////////



                 //////**********以下初始化新增结点的child和childcount域**********
                 //////将新增结点的childcount设置为0
                 Queue[AStarQueueTop].childcount := 0;
                 //////将新增结点的child数组的所有元素初始化为0
                 for i := 1 to 4 do
                 begin
                     Queue[AStarQueueTop].child[i] := 0;
                 end;//end of for i
                 //////**********以上初始化新增结点的child和childcount域**********


                 ///////新增结点没有儿子结点，不必设置其child和childcount域///////


                 //////**********以下设置ChooseNumber结点的child和childcount域**********
                 //////将ChooseNumber结点的childcount加1，表示多了一个儿子
                 Queue[ChooseNumber].childcount := Queue[ChooseNumber].childcount + 1;
                 //////将新增结点的下标AStarQueueTop存入ChooseNumber的child数组中，表示AStarQueueTop是ChooseNumber的儿子
                 Queue[ChooseNumber].child[Queue[ChooseNumber].childcount] := AStarQueueTop;
                 //////**********以上设置ChooseNumber结点的child和childcount域**********


             end;//end of if (SameNumber = 0)----新增结点在之前并没有已经生成

             (***********************************************************
             ****************新增结点在之前并没有已经生成****************
             ***********************************************************)
             if (SameNumber > 0) then    //新增结点在之前已经生成
             begin

                ////////////////////////////////////////////////////////////////
                ////////////////新增结点与Open表中的某一结点相同////////////////
                ////////////////////////////////////////////////////////////////
                if (Queue[SameNumber].flag = 0) then  //新增结点与Open表中的某一结点相同
                begin
                   AStarQueueTop := AStarQueueTop - 1;  //撤消新结点

                   (*************************************************
                    新增结点与Open表中的某一结点SameNumber相同表示：
                    SameNumber多了ChooseNumber一个父亲
                    ChooseNumber也多了SameNumber一个儿子
                    *************************************************)
                   //设置SameNumber的parentcount和parent域
                   Queue[SameNumber].parentcount := Queue[SameNumber].parentcount + 1;
                   Queue[SameNumber].parent[Queue[SameNumber].parentcount] := ChooseNumber;
                   //设置ChooseNumber的childcount和child域
                   Queue[ChooseNumber].childcount := Queue[ChooseNumber].childcount + 1;
                   Queue[ChooseNumber].child[Queue[ChooseNumber].childcount] := SameNumber;

                   //***************以下考虑是否要调整指针和重算评价函数的值***************
                   if (Depth( SameNumber ) > Depth( ChooseNumber ) + 1) then //调整指针可以减少耗散值
                   begin
                      //调整指针
                      Queue[SameNumber].prior := ChooseNumber;
                      //调整指针后重新计算评价函数的值
                      if ( method = 1 )
                      then Queue[SameNumber].value := FValue1( SameNumber )
                      else Queue[SameNumber].value := FValue2( SameNumber );
                      
                   end;//end of if (Depth( SameNumber ) > Depth( ChooseNumber ) + 1)----调整指针可以减少耗散值
                   //***************以上考虑是否要调整指针和重算评价函数的值***************

                end;//end of if (Queue[Samenumber].flag = 0)----新增结点与Open表中的某一结点相同


                ////////////////////////////////////////////////////////////////
                ////////////////新增结点与Close表中的某一结点相同///////////////
                ////////////////////////////////////////////////////////////////
                if (Queue[SameNumber].flag = 1) then  //新增结点与Close表中的某一结点相同
                begin
                    AStarQueueTop := AStarQueueTop - 1;//撤消结点

                    //***************************************************************************
                    //调用IsAncestor函数判断SameNumber是否ChooseNumber的祖先
                    //如果SameNumber是ChooseNumber的祖先，则返回True
                    //如果SameNumber不是ChooseNumber的祖先，则返回False
                    //
                    //如果SameNumber是ChooseNumber的祖先，则不做任何动作
                    //如果SameNumber不是ChooseNumber的祖先，则建立parent和child域，
                    //并且调整SameNumber结点及其后裔结点的指针prior域和评价函数值value域
                    //***************************************************************************

                    if not IsAncestor( SameNumber,ChooseNumber ) then
                    begin

                       (*************************************************
                       新增结点与Open表中的某一结点SameNumber相同并且SameNumber不是ChooseNumber的祖先表示：
                       SameNumber多了ChooseNumber一个父亲
                       ChooseNumber也多了SameNumber一个儿子
                       *************************************************)
                       //设置ChooseNumber结点的child和childcount域
                       Queue[ChooseNumber].childcount := Queue[ChooseNumber].childcount + 1;
                       Queue[ChooseNumber].child[Queue[ChooseNumber].childcount] := SameNumber;
                       //设置SameNumber结点的parent和parentcount域
                       Queue[SameNumber].parentcount := Queue[SameNumber].parentcount + 1;
                       Queue[SameNumber].parent[Queue[SameNumber].parentcount] := ChooseNumber;

                       //如果SameNumber结点的耗散值可以减少，则调整SameNumber结点及其后裔结点的指针prior域和评价函数值value域
                       if ( Depth( SameNumber ) > Depth( ChooseNumber ) + 1 ) then
                       begin
                           //调整SameNumber结点的指针指向prior域
                           Queue[SameNumber].prior := ChooseNumber;
                           //调整SameNumber结点的/评价函数值value域
                           if ( method = 1 )
                           then Queue[SameNumber].value := FValue1( SameNumber )
                           else Queue[SameNumber].value := FValue2( SameNumber );

                           //***************************************************************************
                           //调用Adjust过程调整SameNumber结点的后裔结点的指针prior域和评价函数值value域
                           //***************************************************************************
                           Adjust( SameNumber );
                           

                       end;//end o f if ( Depth( SameNumber ) > Depth( ChooseNumber ) + 1 )----SameNumber结点的耗散值可以减少

                    end;//end of if not IsAncestor( SameNumber,ChooseNumber )----SameNumber不是ChooseNumber的祖先

                end;//end of if (Queue[Samenumber].flag = 1)----新增结点与Close表中的某一结点相同

             end;//end of if (SameNumber > 0)----新增结点在之前已经生成

         end;//end of if  ( (row >= 1) and (row <= 3) and (col >= 1) and (col <=3) )----判断空格是否可以向左、上、右、下移动

      end;//end of for k     

   end;//end of while

   //AStar的返回值是最后一个展开的结点的下标
   AStar := ChooseNumber;
end;


///////////////////////////////////////////////////////////////
////AStar1ResultOutput过程将A星算法1找到的路径显示在AStar1Memo
////入口：procedure----CompareBtnClick()
////参数：无
///////////////////////////////////////////////////////////////
procedure TEightNumber.AStar1ResultOutput();
var i:integer; //循环变量
begin
   //先设置显示路径结点总数和访问结点总数的Label为不可见
     AStar1RoadLabel.Visible := False;
     AStar1VisitedLabel.Visible := False;

   //*********************************************
   //调用Initialize过程初始化初始结点
     Initialize();

   //*********************************************
   //调用MemorizeAstar1Road过程实现2件事情
   //1.用A星算法1求出从初始结点到目标结点的耗散值最小的路径，
   //2.将路径记录在AStar1Path全局数组中
     MemorizeAstar1Road();