eightnumberfrm.pas

此软件是八数码软件

        for j := 1 to 3 do
        begin
          if ( Target[i,j] <> 0 )
          then
          begin
             for p := 1 to 3 do
             begin
                for q := 1 to 3 do
                begin
                   //找到相同数字，则计算距离和
                   if ( Queue[n].status[p,q] = Target[i,j] ) then
                   begin
                      count := count + ABS(i-p) + ABS(j-q);
                      break;
                   end; //end of if ( Queue[n].status[p,q] = Target[i,j] )

                end;//end of for q

             end; //end od for p

          end; //end of if ( Target[i,j] <> 0 )

        end;//end of for j

     end;//end of for i

     HValue2 := count;  //返回启发式函数的值

end;


///////////////////////////////////////////////////
////Initialize过程初始化初始结点
////入口：procedure----AStar1BtnClick()
////      procedure----AStar2BtnClick()
////      procedure----BFSBtnClick()
////      procedure----AStar1ResultOutput
////      procedure----AStar2ResultOutput
////      procedure----BFSResultOutput
////参数：无
///////////////////////////////////////////////////
procedure TEightNumber.Initialize;
var i,j:integer; //循环变量
begin
   //**********************初始化初始结点**********************

   //**********确定初始状态的空格的行列坐标
   for i := 1 to 3 do
   begin
      for j := 1 to 3 do
      begin
         if ( Queue[1].status[i,j]=0 )
         then begin
                Queue[1].x := i;
                Queue[1].y := j;
              end;
      end;//end of for j
   end;//end of for i

   //确定评价函数f的值，f = g + h ;
   Queue[1].value := HValue1( 1 ) + Depth( 1 );

   //头结点没有父结点，确定指针指向空
   Queue[1].prior := 0;

   //头结点一开始放在Open表
   Queue[1].flag := 0;

   //头结点没有父结点，设置parentcount为0，其parent数组元素也为0
   Queue[1].parentcount := 0;
   for i := 1 to 4 do
   begin
       Queue[1].parent[i] := 0;
   end;//end of for i

   //头结点还没有展开，还没有子结点，设置childcount为0，其child数组元素也为0
   Queue[1].childcount :=0;
   for i := 1 to 4 do
   begin
       Queue[1].child[i] := 0;
   end;//end of for i

end;


///////////////////////////////////////////////////
////IsAncestor函数判断结点m是否结点n的祖先
////是祖先则返回True，不是祖先则返回false
////入口：function----AStar(method:integer):integer
////参数：某两个结点在Queue数组中的下标
///////////////////////////////////////////////////
function TEightNumber.IsAncestor(m, n: integer): boolean;
var i :integer;  //循环变量
    FindAncestor : boolean; //是否有祖先关系
    head,tail :integer;  //数组指针
    pcount :integer; //记录某一结点的父亲结点的个数
begin
    //初始化ancestor数组，令其所有元素全部归零
    //Low(ancestor)和High(ancestor)分别代表ancestor数组的下标的下限和上限，
    //此处实质为1和200，这样做的好处是增加兼容性和易修改性
    for i := Low(ancestor) to High(ancestor) do
    begin
        ancestor[i] := 0;
    end;//end of for i

    //ancestor数组中的数据全是结点n的祖先的下标
    //ancestor数组的第一项存入n
    ancestor[1] := n;
    FindAncestor := False;
    head := 0;  //ancestor数组的头指针
    tail := 1;  //ancestor数组的尾指针

    while (head <> tail) do
    begin
        head := head + 1;
        //取出head指针指向的结点的父亲结点的个数
        pcount := Queue[ancestor[head]].parentcount;
        //如果父亲结点的个数为0，则表示该结点没有父亲，则不再向上搜索。此结点实质为头结点
        //如果父亲结点的个数大于0，则表示该结点没有父亲，则继续向上搜索
        if (pcount > 0) then
        begin
           for i := 1 to pcount do
           begin
               tail := tail + 1; //新增ancestor数组的元素
               ancestor[tail] := Queue[ancestor[head]].parent[i]; //将n的新找到的祖先放入ancestor数组的新的元素中
               if (ancestor[tail] = m) then  //在n的祖先中找到m，则设置FindAncestor为True
               begin
                    FindAncestor := True;
                    break;
               end;//end of if (ancestor[tail] = m)
           end;//end of for i
        end;//end of if (pcount > 0)
        if FindAncestor then break;
    end;//end of while

    IsAncestor := FindAncestor;  //返回结点m是否结点n的祖先，True 或者 False


end;

///////////////////////////////////////////////////
////IsTarget函数判断参数指定的结点是否达到目标状态
////达到则返回True，没有达到则返回false
////入口：procedure---AStar()
////      procedure---BFS()
////      procedure---MemorizeAStar1Road()
////      procedure---MemorizeAStar2Road()
////      procedure---MemorizeBFSRoad()
////参数：某一结点在Queue数组中的下标
///////////////////////////////////////////////////
function TEightNumber.IsTarget(n: integer): boolean;
var  i,j : integer;  //循环变量
     ok : boolean;   //是否相等监测器
begin
   ok := True;
   for i := 1 to 3 do
   begin
     for j := 1 to 3 do
     begin
        if (Queue[n].status[i,j] <> target[i,j])
        then  begin
                 ok := False;  //不相等则设置为False
                 break;
              end;//end of if
     end;//end of for j
     if not ok then break;
   end;//end of for i
   IsTarget := ok;   //返回是否相等，True 或者 False
end;

///////////////////////////////////////////////////
////AStar1BtnClick函数用A星算法1搜索路径
////入口：用户点击
////参数：无
///////////////////////////////////////////////////
procedure TEightNumber.AStar1BtnClick(Sender: TObject);
begin
   //设置状态栏显示内容
     StatusBar.Panels[0].Text := '正在计算演示中，请稍等......' ;

   //先设置显示路径结点总数和访问结点总数的Label为不可见
     AStar1RoadLabel.Visible := False;
     AStar1VisitedLabel.Visible := False;

   //清空AStar1Memo的内容
     AStar1Memo.Lines.Clear;

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

   //*********************************************
   //调用InitializeImage过程初始化初始结点的9个Image
     InitializeImage();

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

   //将结果演示出来
     AStar1ShowResult();

   //路径结点总数和访问结点总数赋予对应的Label
     AStar1RoadLabel.Caption := inttostr(AStar1PathTop) + '  ';
     AStar1VisitedLabel.Caption := inttostr(AStarQueueTop) + '  ';

   //设置显示路径结点总数和访问结点总数的Label为可见
     AStar1RoadLabel.Visible := True;
     AStar1VisitedLabel.Visible := True;

   //设置状态栏显示内容
     StatusBar.Panels[0].Text := '欢迎使用本八数码软件';
end;

///////////////////////////////////////////////////
////BFSBtnClick函数用BFS算法1搜索路径
////入口：用户点击
////参数：无
///////////////////////////////////////////////////
procedure TEightNumber.BFSBtnClick(Sender: TObject);
begin
   //设置状态栏显示内容
     StatusBar.Panels[0].Text := '正在计算演示中，请稍等......' ;

   //先设置显示路径结点总数和访问结点总数的Label为不可见
     BFSRoadLabel.Visible := False;
     BFSVisitedLabel.Visible := False;

   //清空BFSMemo的内容
     BFSMemo.Lines.Clear;

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

   //*********************************************
   //调用InitializeImage过程初始化初始结点的9个Image
     InitializeImage();

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

   //将结果演示出来
     BFSShowResult();

   //路径结点总数和访问结点总数赋予对应的Label
     BFSRoadLabel.Caption := inttostr(BFSPathTop) + '  ';
     BFSVisitedLabel.Caption := inttostr(BFSTail)+ '  ';

   //设置显示路径结点总数和访问结点总数的Label为可见
     BFSRoadLabel.Visible := True;
     BFSVisitedLabel.Visible := True;

   //设置状态栏显示内容
    StatusBar.Panels[0].Text := '欢迎使用本八数码软件';
end;


////////////////////////////////////////////////////////////
////BFSResultOutput过程将BFS找到的路径显示在BFSMemo
////入口：procedure----CompareBtnClick()
////参数：无
////////////////////////////////////////////////////////////
procedure TEightNumber.BFSResultOutput();
var i:integer; //循环变量
begin
   //先设置显示路径结点总数和访问结点总数的Label为不可见
     BFSRoadLabel.Visible := False;
     BFSVisitedLabel.Visible := False;

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

   //*********************************************
   //调用MemorizeBFSRoad过程实现2件事情
   //1.用BFS求出从初始结点到目标结点的耗散值最小的路径，
   //2.将路径记录在BFSPath全局数组中
     MemorizeBFSRoad();
     
    if ( BFSPathTop <> 0 ) then
    begin
        BFSMemo.Lines.Clear;
        //显示初始结点
        BFSMemo.Lines.Add( ' ' + inttostr(Queue[1].status[1,1]) + ' ' + inttostr(Queue[1].status[1,2]) + ' ' + inttostr(Queue[1].status[1,3]) );
        BFSMemo.Lines.Add( ' ' + inttostr(Queue[1].status[2,1]) + ' ' + inttostr(Queue[1].status[2,2]) + ' ' + inttostr(Queue[1].status[2,3]) );
        BFSMemo.Lines.Add( ' ' + inttostr(Queue[1].status[3,1]) + ' ' + inttostr(Queue[1].status[3,2]) + ' ' + inttostr(Queue[1].status[3,3]) );

        //循环显示其他结点
        for i := BFSPathTop-1 DownTo 1 do
        begin