当前位置:编程学习 > VC++ >>

VC中利用人工智能解决八迷宫问题

 前言

  随着计算机技术的发展,人工智能(Artificial intelligence,下文简称"AI")已经成为世界各国一个热门的研究方向。对于这一领域的内容,国内起步较晚,目前虽然网络上各种编程文章很多,但是关于如何编程解决人工智能问题的文章和资料少之又少。近日,笔者有幸在国外网站上发现了这一篇精彩文章,该文通过VC实例来说明如何解决及实现人工智能问题,例子程序虽然相对来说比较简单,但有一定的代表性,对有兴趣研究这一领域的朋友们有借鉴意义。

  一、"八迷宫"游戏简介

  在大学进行AI模块开发的时候,我就开始着手写这篇文章,目的是介绍我所了解到的一些让人感兴趣的问题。对于什么是人工智能,我想没有任何人愿意花费大量时间进行争论。

  当你读到这里的时候,推荐你下源代码,因为粘贴和拷贝的代码与源代码的作用相比是远远不及的。在本文中,我将使用一个单人游戏"八迷宫"作为一个例子,这个游戏的规则如下:

  有一个3X3的网格,包含1到8这几个数(因此,有一个格子是空的),最初这8个数的排列是随机的,例如,下面的排列是一种可能情况:

6 1 7
3 4
5 8 2

  游戏玩家可以向东、南、西、北等方向移动这个空格,移动空格时,空格所占位置的数字将填补到原来空格的位置。例如,对于上图来说,如果向北移动空格,游戏的状态将如下图所示:

6 1
3 4 7
5 8 2


  当游戏状态实现如下所示的状态时,游戏结束。

1 2 3
8 4
7 6 5

  二、解决"八迷宫"问题的方法

  解决上述问题的方法主要有以下几种:

  1、Breadth First Search(按照"横向"原则搜索).

  2、Depth First Search(按照"深度"原则搜索).

  3、Heuristic Search(启发式搜索).

  4、A* search.

  实现这些方法的代码非常相似,但是它们工作的方式是截然不同的。所有的上述方法都要使用一个链表,而且最初的链表都只有一个成员,它对应着游戏网格的最初状态。这个成员向它所有可能的子状态进行膨胀(每种移动所产生的结果都被考虑了进去),然后所有这些子状态都被添加到链表中。这种处理将在一个循环中进行持续处理,直到实现目标状态,也就是说直到游戏结束为止。

  实现"八迷宫"单人游戏的伪代码如下:
Do
  Current_Item = Remove_Item_From_List
  Child_State_Array = Expand (Current_State)
  Add_to_List(Child_State_Array)
  If child_State_Array Holds the solution then IsGameOver = true
Loop while (IsGameOver = false)


   这个结构的代码可以在上述所有的人工智能方法中看到,各种方法的区别仅仅在于它们是如何在链表中进行排序。

   1、在 breadth first search方法中,各个成员都是按照某一固定的方向被添加到链表中,删除时按相反方向进行。

   2、在 depth first search方法中,各个成员的添加和删除都是在链表的同一个方向进行。

   3、在heuristic search方法中,各个成员可以在链表的任意方向进行添加,然而,在从链表中删除一个成员时,每一个成员被"heuristic"函数进行打分(对于状态来说,分数越高越接近于最终状态),得分最高的项目将被从链表中删除。

   4、A*方法使用两个heuristic函数,并将最终的两个得分加在一起。使用两个heuristics函数极大地提高了程序发现下步最佳状态的能力,但是却降低了程序的运行速度。

   其实,三、四方法是第二种方法的延伸和变种,区别仅在于启发式搜索的方式不同罢了,这一点读者朋友们可以在后面的代码中细细体味。实际上"八迷宫"这种游戏的heuristic函数的可以是这么一个函数,它计算拥有正确位置的网格个数,或是100-状态深度。

   使用启发式的搜索有利有弊,在这个例子中,使用启发式可能使程序的主循环降低10倍速度,然而,它降低了循环的次数,可能从6百万次降低到了4000次,这节省了内存的负荷,以及例子程序的运行时间。(这提醒了我,我使用的最初的状态使用了25步解决了问题),这看起来不是很多,但如果没有启发式搜索,搜索将1秒钟处理300兆的内存,除非你使用功能强大的处理机器,(我使用的是1.3G,256兆的机器),否则你可能需要减少结束游戏所需要的移动次数,要低于10。

  三、程序代码

  首先,要声明的是,游戏网格在程序中对应着一个拥有10个成员变量的数组,网格每个位置按照从左到右、从上到下的位置排序。对于网格状态,可实现一个状态类,它对应着网格的各种状态,并拥有所有操作网格时所需要的代码和变量,这个类命名为CState,代码如下:

/* 声明网格中空格所有可能移动的方向,至于为什么要包括"NONE"将在后面的代码中显现出来;*/
enum DIRECTION { NONE, NORTH, EAST, SOUTH, WEST };

// 声明CState类
class CState {
  private:
   // 使用1 to 9号索引来对应网格的每个位置, 定义为 char类型是为了节省内存;
   char Grid[10];
   char Depth; //Depth变量对游戏的最初原始状态演变到当前状态所经历的步数;
   //我们需要记录下父状态是如何进行移动而得到当前状态的;
   DIRECTION OperatorApplyed;
   // 父状态指针,当程序结束时,我们可以利用它跟踪所经历的状态,从而给出答案;
   CState *PrevState;

   // 寻找当前网格中的空格位置或某一个具体数字的位置,默认状态是寻找空格位置;
   inline int FindBlank(char Search=0) {
    int Blank=1;
    while (Grid[Blank] != Search) {
     Blank++;
    }
    return Blank;
   }

   // 按照规定的方向移动空格;
   void MoveBlank(DIRECTION Direction) {
    int Blank = FindBlank();
    // 我们需要记住本次操作所移动的方向;
    OperatorApplyed = Direction;
    switch (Direction) {
     case NORTH:
      Grid[Blank] = Grid[Blank - 3];
      Grid[Blank - 3] = 0;
      break;
     case EAST:
      Grid[Blank] = Grid[Blank + 1];
      Grid[Blank + 1] = 0;
      break;
     case SOUTH:
      Grid[Blank] = Grid[Blank + 3];
      Grid[Blank + 3] = 0;
      break;
     case WEST:
      Grid[Blank] = Grid[Blank - 1];
      Grid[Blank - 1] = 0;
      break;
    }
   }

   /* 下面的函数将被用于第一种方法的heuristics函数的一部分,它得到两个索引位置的直角距离,它还用于确定一个数字当前位置与其应该所在位置的直角距离;
   int GetDistanceBetween(int Tile1, int Tile2) {
    int X1, X2;
    int Y1, Y2;
    int temp=0;
    // 将grid位置转换为X,Y坐标;
    Y1 = 1;
    Y2 = 2;
    X1 = Tile1;
    X2 = Tile2;
    if(Tile1 > 3) { Y1 = 2; X1 = Tile1 - 3; }
    if(Tile1 > 6) { Y1 = 3; X1 = Tile1 - 6; }
    if(Tile2 > 3) { Y2 = 2; X2 = Tile2 - 3; }
    if(Tile2 > 6) { Y2 = 3; X2 = Tile2 - 6; }
    //为了确保距离值为正说,进行必要的换位处理;
    if(Y1 - Y2 < 0) {
     temp = Y1;
     Y1 = Y2;
     Y2 = temp;
    }
    if(X1 - X2 < 0) {
     temp = X1;
     X1 = X2;
     X2 = temp;
    }
    return ((Y1 - Y2) + (X1 - X2));
   }

  public:
   // 异常处理;
   class ERROR_ILLEGAL_MOVE{};
   class ERROR_NO_MORE_DIRECTIONS{};
   class ERROR_OUT_OF_BOUNDS{};
   //用于heuristic函数;它代表了当前状态与前一状态的距离;这个数值越小越好。
   int GetDepth() {
    return Depth;
   }

   // CState类构造函数;
   CState() {
    Depth = 0;
    Grid[1] = 6; // for slower machines use 4
    Grid[2] = 1; // for slower machines use 1
    Grid[3] = 7; // for slower machines use 3
    Grid[4]
补充:软件开发 , Vc ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,