[人工智能]八数码问题

作者:bibodeng 发布于:2012-11-2 14:37 Friday 分类:linux

【接触人工智能】

这个学期开了人工智能的课程,对于计算机的应用的理解又加深了一步。科学家通过开发更加高效可行的算法,使得解决问题更加智能,而不是使用bruce force,因为面对海量的运算,再强大的计算机也力不从心。故而需要又一些聪明的算法,可以用最快的方法,或者在保证正确性的情况下,做到更快。就拿八数码问题来说,由于博弈中有很多的可能性,而每种可能性都能继续产生下一步情况,这样整个解空间将非常地庞大。如下图所示,一个初始棋盘,每一步有4(也有可能3,2)种可能,这样每一步都使得解空间加倍。但是解八数码的时候,往往是尝试那些朝着目标的方向进行的。例如我们可以简单的认为,错位数少的就比那些错位数多的距离目标状态更近了。故而这样就可以减少很多搜索量了,这样我们就可以引入一个启发值,来使得距离目标更近的状态先搜索,这样我们或许就能更快地到达目标状态,也就能找到解了。

 

【八数码问题】

问题的描述: 有九宫,每宫里面有0-9中的某个数字,如下图,而我们需要移动0,直到棋盘到达目的状态。0只能在棋盘中往相邻宫格移动。

我们可以想象小时候玩的八数码小玩具,有一格是空的,而其他板块可以和空格进行交换(移动),而这种玩具和古代的华容道很相像,只是比华容道简单很多而已。

如下图所示,我们要将如下状态转换成目标状态,比如是一个环形 的12345678,0在正中间:

点击查看原图

根据问题的定义,我们应该想像得出解决方案了。 根据软件设计的过程,我们先对软件进行划分模块,程序的核心是由AStarPuzzle的类封装的,里面包括状态的结构定义,以及状态的输出到参数vector,openlist和closelist以及各种关于程序逻辑的实现;而界面方面,我决定采用Qt界面,一个是因为喜欢在ubuntu下活动,另外一个是Qt看起来比MFC容易得多,程序负责的就是接受用户的操作,用一些信号和槽完成交互,例如从界面中获取数据,以及将后台产生的数据送到前台显示。由于Qt才刚开始学,一开始很混乱,后来对于它的槽和信号机制有了点了解,也就慢慢地能驾驭了,其实还是看文档比较有用。


开发过程中得到的一个很严重的体会就是:开发之前先分析一下怎么做,按照软件工程的方法来进行细化一下,当然前提是要对自己的目标(需求)和工具很了解(这里是Qt),然后才开始写代码,这样会轻松很多。遇到问题时,离开电脑前,好好思考一下,从远处看,你会更看得到该怎么做。这就好比画画,先有个物体的框架,然后去描绘那些细节,而一头扎进细节里面,画出来的东西可能没法看,而有时候画着忘记该怎么走了,应该好好后退几步审视一下,说不定会有头绪。貌似废话有点多了,但这是非常深切的体会,如果掌握了这种方法,可以节省大量的时间。


[A星算法解决八数码问题]

根据八数码的解的空间的图(是一个看起来像树的图,每走一步会派生出),我们要对解空间进行搜索,以通过一系列步骤到达目标状态,那么这一系列的步骤就是我们需要的走法。

从网上拿来的图:

点击查看原图

这其实就是一个搜索问题,那么我们就应该有像深度遍历或者广度遍历的一个队列,只是这个队列是按照我们定义的fx = hx + gx来进行排序的,这里采用的是优先队列的方法,将状态封装成为类,自动生成优先数,然后将那些还没有探测过的节点放入openlist这个优先队列中,优先数高的排前面。根据A*算法原理,最终一定可以找到最优解的,而且运算量大大减少。扩展它的子节点,放到openlist,然后那些探测过的节点则放入closelist中,最终从目标状态往上寻找祖先就可以找到解的路径了。

好了,下面就是具体实现了,代码有点糟糕:P

class AStarPuzzle
{
public:
        priority_queue <PuzzleState, vector<PuzzleState>,greater<PuzzleState> > openList;         // 一个open表  优先队列,方便取出最优的节点
    vector<PuzzleState> closeList;            // 一个close表

    int boardSize ;                 // 棋盘大小 默认为 3
    int curStep;                        // 当前所走步数,每当深入一层,curStep加1,而上浮一层则减1
        char gameType;                  // 用来记录当前的游戏状态 : 随机或者是自定义棋盘

    PuzzleState *curState;      // 当前状态,一开始为初始节点
        PuzzleState *goalState;         // 目标状态
        vector<PuzzleState> resultSteps;   // the result steps

public:     // 方法
    void Initialize();                                                          // 初始化对象
    
    void SetBoardSize();        // 设置棋盘边长
        void SetBoardSize(int size);

    void SetBeginState();       // 设置起始状态
        void SetBeginState(vector<int> &vint);
    void SetGoalState();        // 设置目标状态
        void SetGoalState(vector<int> &vint);
    void SetGameType();     // 设置 随机还是自定义模式
        void SetGameType(char &type);

    PuzzleState* GetFirstNodeFromOpenList();                    // 从open表中取下第一个节点
    void ExternState(PuzzleState* father, int direction, int spacePos);     // 扩展某个方向的state
    void ExternNext(PuzzleState *father);                           // 扩展下一步,向4或3或2个方向扩展,传入的参数为open表和父节点,遇到不符合的舍弃
    bool IsIn(vector<PuzzleState> &closeList, PuzzleState *p);   // 判断某节点是否在close表中
    int AddNodeToOpenList(PuzzleState *node)    ;           // 向open表添加一个节点
    int MoveNodeToCloseList(PuzzleState *node);         // 移动节点到close表中
    // void SortOpenNode();                                             // 对open表进行排序 如果是链表则可以用普通排序方法实现
    
    void DoBestFirstSearch();                                           // 完成程序功能的函数调用,检查open表是否空,如果不空进行
        void PrintPath(PuzzleState* p);                                 // 输出路径
        void PrintPath(PuzzleState *p, vector<PuzzleState> &vps);
    void PrintPuzzleEnd();                                                  // 输出程序运行结束
        void produceDefaultGoalStatus(vector<int> &vint);
};

/*
*   问题状态节点类,存储当前棋盘状态
*   这是一个节点
*/
class PuzzleState
{
    // 在该状态中,包含了一个棋盘的数组
public: 
    vector<int> board;   // 棋盘
    int curFloor;       // 当前遍历到的层 用于记录 g(x)    在AStarPuzzle里面可以通过走过的步数来计层数
    int distance;      //  当前状态到目标状态之间的距离 h(x) 其实就是错位个数
    int heuristicValue;     // 启发值,f(x) = h(x)+g(x)

    PuzzleState(void);
    PuzzleState(vector<int> vec, int boardsize);          // 构造函数和析构函数
    ~PuzzleState(){};
    

    int RandomGrid(int boardsize);  // 传入一个棋盘数组,然后随机分布格子
    int CustomerGrid(const vector<int> &vec, int boardsize);  // 用户自定义设置格子布局
    bool IsGoalState(const std::vector<int> &goal, int boardsize);        //  判断棋盘状态是否是目标状态
    void SetHeuristicValue();


        int GuessDistance(const PuzzleState *goal, int boardsize);  // 估算从该状态到目标位置的距离 即h(x) 错位个数
    // f(x) = h(x) + g(x)   h(x)为错位个数 g(x)为当前遍历层数
    void PrintState(int boardSize);                     // 打印棋盘
    int GetSpacePosition();                                 // 获取空格所在位置
    void SetCurFloor(int floor);

    PuzzleState *parent;    // 父节点

        // 比较函数,用于排序用 原来这是STL默认用来排序优先队列的操作法
        /*bool operator > (const PuzzleState &st1, const PuzzleState &st2){
                return st1.heuristicValue > st2.heuristicValue;                              // 小的优先
        }*/

        bool operator > (const PuzzleState &st2)const{
                return this->heuristicValue > st2.heuristicValue;                             // 小的优先
        }
};

本文附有源代码压缩包,故而只贴出了类的描述。核心在于guessDistance ,这里采用的启发信息是错位个数,其实还可以更好,那就是距离应该在的位置的x距离+y距离。只需要通过修改guessDistance函数即可。至于细节我也不想多罗嗦了,多读几遍A*算法和八数码的书籍,就能弄懂那些函数是干嘛用的了。而且很多人的实现互不相同。

至于界面,下面是代码:

class MainWindow : public QMainWindow
{
    Q_OBJECT

public:
    explicit MainWindow(QWidget *parent = 0);
    ~MainWindow();
    void setStartStatusDisable(bool boo);  // 传入一个布尔值,true为disable, false为enable可写入
    void setGoalStatusDisable(bool boo=true);    // 目标状态
    void setCurStatusDisable(bool boo=true);     // 当前状态 默认为disable
    void setStartBtnDisabled(bool boo);
    void setPauseBtnDisabled(bool boo);
    void setStepChoicesDisabled(bool boo);
    void setStartCustomBtnDisabled(bool boo);

    void setStartStatus(vector<int> &vint);      // 设置状态值到格子里面
    void getStartStatus(vector<int> &vint);      // 从格子里面获取数据

    void setGoalStatus(vector<int> &vint);      // 设置状态值到格子里面
    void getGoalStatus(vector<int> &vint);



    void setGoalCustomBtnDisabled(bool boo);

    void setCurStatus(vector<int> &vint);   // display to grids


    char getGameStartType();
    char getRunType();
    void setBoardSize(int size);
    void setGameStartType(char type);     // when recieve a clicked signal of startstatus button
    void displayAllSteps();                     // 连续输出

public slots:
    void startBtnDown();
    void pauseBtnDown();

    void goalDefaultBtnDown();
    void goalCustomBtnDown();

    void startCustomBtnDown();
    void startRandomBtnDown();

    void setGameStartTypeDefault();
    void setGameGoalTypeDefault();
    void setRunType(int type);      //
    void doSolvePuzzle();        // run the program main
    void produceDefaultStartStatus();
    void produceDefaultGoalStatus();

    // one step a time in cur step layout
    void displayPreStep();    // pre
    void displayNextStep();  // next

    void setRunTypeSingle();                    // set单步
    void setRunTypeAll();                       // set连续


    void displayCurStep();

private:
    Ui::MainWindow *ui;
    char gameStartType;      // 'r'(random) or 'c'(custom)
    // goal only have default type
    char gameGoalType;      // 'd'(default) or 'c' (custom)
    int runType;            // 1 for single 2 for many
    int boardSize;
    int curStepNum;        // count the curstep
    AStarPuzzle *app;
    QTimer *timer;
};

定义了一些属性来存储数据,虽然可以直接用AStarPuzzle类中封装的来代替,而且最好是让界面仅仅做显示和获取数据,也就是核心的setStatus和getStatus,其他都是效果性的东西。

 点击查看原图

Qt界面非常清爽,我很喜欢

要做到那些按键效果,需要考虑哪个键按下之后,其他键需要enable或者disable。这样才能让用户正确地操作程序。当然这个乱七八糟的怪物不知道什么时候跑出一个错误来。就写到这里,还有很多有趣的人工智能的问题,等待着俺们去探索。

源代码下载

by bibodeng      2012-11-24

标签: 8数码 人工智能 A*

发表评论:

Powered by emlog 京ICP备16017775