使用C++解决八数码问题

使用C++解决八数码问题八数码问题问题描述:通过单步移动把下面的矩阵移动成1-8环绕一周的矩阵(即0在中间,1-8顺序排成一圈,1在哪无所谓)217860345283164705 \begin{matrix} 2&8&3\\ 1&6&4\\ 7&0&5\\ \end{matrix}(1)分别用宽度和深度搜索进行;(2)假设启发式的方程为f(n)=d(n)+…

大家好,又见面了,我是你们的朋友全栈君。

八数码问题


问题描述:通过单步移动把下面的矩阵移动成1-8环绕一周的矩阵(即0在中间,1-8顺序排成一圈,1在哪无所谓)

217860345 2 8 3 1 6 4 7 0 5



(1) 分别用宽度和深度搜索进行;

(2) 假设启发式的方程为f(n)=d(n)+h(n),其中d(n)为层次或深度,h(n)为错误的个数,使用启发式算法解决;

(3) 编程(分别用宽度搜索,深度搜索和启发式算法),并分析步数。


Solution:
(1) 如下图所示,广度(宽度)优先搜索是每次将一层的所有可能状态都搜索完毕再进入下一层,深度优先搜索是每次将一个树的分支搜索完毕再进入另一个分支。



figure1


  图中的每一个节点都记为一个状态,根节点记为初始状态和初始节点,目标叶子节点记为目标状态和目标节点。0在移动的过程中,产生的状态可能与前面已经存在的状态重复(图中的重复状态已删去),为避免这些重复状态,节省空间和时间,使用hash函数判断产生的状态是否存在,如果存在,则终止该分支。

  具体的,使用康托展开计算状态的hash值。广度优先搜索时,对比open表和close表来判断新产生的分支是否重复。深度优先搜索时,对比自己的父节点,父节点的父节点,…,直到初始节点,来判断新产生的分支是否重复。

深度优先搜索时,由于有的分支可能较深,深度搜索时,为避免时间太长,可限制搜索的深度,比如,最大搜索深度为8。

(2) 启发式搜索就是在状态空间中对每一个状态进行评估,找到最好的状态,再从这个状态出发直至到达目标状态。每次寻找最佳的状态可以省略大量不需要的搜索,提高了效率。
  题目中给出的评估方程为f(n)=d(n)+h(n),其中d(n)为层次或深度,h(n)为错误的个数。题目中虽然没有要求1的位置,但是为了简单的计算h(n),编程时,规定1在左上角,1-8顺时针排列。
  由于初始状态比较有规律,所以在使用启发式搜索的条件下,程序只会在深度为1的节点发生分叉,如下图所示:



figure2


  正确路径的d(n)依次为0,1,2,3,4,5,h(n)依次为5,3,4,3,2,0。

(3) 算法原理
广度优先搜索的算法如下:
a) 把初始节点放入Open表中;
b) 如果Open表为空,则问题无解,失败退出;
c) 把Open表的第一个节点取出放入Close表,并标记该节点为n;
d) 考察n节点是否为目标节点。如果是,则得到问题的解,成功退出;
e) 如果节点n不可扩展,则转第b)步;
f) 扩展节点n,将其子节点放入Open表的尾部,并为每一个子节点设置指向父亲节点的指针,然后转第b)步。

深度优先搜索的算法如下:
a) 把初始节点放入Open表中;
b) 如果Open表为空,则问题无解,失败退出;
c) 把Open表的第一个节点取出放入Close表,并标记该节点为n;
d) 考察n节点是否为目标节点。如果是,则得到问题的解,成功退出;
e) 如果节点n不可扩展,则转第b)步;
f) 扩展节点n,将其子节点放入Open表的头部,并为每一个子节点设置指向父亲节点的指针,然后转第b)步。

启发式搜索的算法如下:
a) 把初始节点放入Open表中,计算其f值;
b) 如果Open表为空,则问题无解,失败退出;
c) 把Open表的第一个节点取出放入Close表,并标记该节点为n;
d) 考察n节点是否为目标节点。如果是,则得到问题的解,成功退出;
e) 如果节点n不可扩展,则转第b)步;
f) 扩展节点n,计算每一个子节点的f值,并为每个子节点设置指向节点n的指针,将这些子节点放入Open表中;
g) 根据各节点的f值,对Open表中给的全部节点按照从小到大的顺序排序;
h) 转第b)步。

程序运行结果如下:



使用C++解决八数码问题


  广度优先搜索遍历的状态数是115,深度优先搜索遍历的状态数是298,启发式搜索遍历的状态数是8。可以看到启发式搜索的效率是惊人的。

C++源码:

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

// 八数码状态
typedef struct _Status{
    int status[3][3];
    _Status *parent;
    _Status *next;
}Status;

// AStar排序依据
bool decComparator(const Status &s1, const Status &s2){
    int gn1 = 0, gn2 = 0;
    int dn1 = 0, dn2 = 0;
    const Status *ptr1 = &s1;
    const Status *ptr2 = &s2;
    int status[3][3] = {
  
  1,2,3,8,0,4,7,6,5};
    while(ptr1 != NULL){
        gn1 += 1;
        ptr1 = ptr1->parent;
    }
    while(ptr2 != NULL){
        gn2 += 1;
        ptr2 = ptr2->parent;
    }
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            if(s1.status[i][j] != status[i][j]){
                dn1 += 1;
            }
            if(s2.status[i][j] != status[i][j]){
                dn2 += 1;
            }
        }
    }
    return (gn1+dn1) > (gn2+dn2);
}

// 八数码搜索
class EightPuzzle{
private:
    unsigned char allHash[362880];
    Status root;
    Status goal;
private:
    int nextNumber;
    Status next[4];
public:
    EightPuzzle(Status *root, Status *goal){
        memcpy(&this->root.status, &root->status, sizeof(int)*9);
        this->root.parent = NULL;
        this->root.next = NULL;
        memcpy(&this->goal.status, &goal->status, sizeof(int)*9);
        this->goal.parent = NULL;
        this->goal.next = NULL;
    }
private:
    // 判断是否是目标状态
    inline int IsGoal(Status *tmp){
        return memcmp(&tmp->status, &goal.status, sizeof(int)*9);
    }
    // 下一个可行的状态
    int NextStatus(Status *tmp){
        nextNumber = 0;
        int posi, posj;
        for(int i = 0; i < 9; i++){
            posi = i/3, posj = i - i/3*3;
            if(tmp->status[posi][posj] == 0){
                break;
            }
        }
        if(posi-1 >= 0){
            Status left = *tmp;
            left.status[posi][posj] = left.status[posi-1][posj];
            left.status[posi-1][posj] = 0;
            if(allHash[Cantor(left.status)] == 0){
                next[nextNumber] = left;
                next[nextNumber].parent = tmp;
                nextNumber++;
            }
        }
        if(posi+1 <= 2){
            Status right = *tmp;
            right.status[posi][posj] = right.status[posi+1][posj];
            right.status[posi+1][posj] = 0;
            if(allHash[Cantor(right.status)] == 0){
                next[nextNumber] = right;
                next[nextNumber].parent = tmp;
                nextNumber++;
            }
        }
        if(posj-1 >= 0){
            Status up = *tmp;
            up.status[posi][posj] = up.status[posi][posj-1];
            up.status[posi][posj-1] = 0;
            if(allHash[Cantor(up.status)] == 0){
                next[nextNumber] = up;
                next[nextNumber].parent = tmp;
                nextNumber++;
            }
        }
        if(posj+1 <= 2){
            Status down = *tmp;
            down.status[posi][posj] = down.status[posi][posj+1];
            down.status[posi][posj+1] = 0;
            if(allHash[Cantor(down.status)] == 0){
                next[nextNumber] = down;
                next[nextNumber].parent = tmp;
                nextNumber++;
            }
        }
        return nextNumber;
    }
    // 康托展开
    int Cantor(int arr[][3]){
        int fac[10] = {
  
  1,1,2,6,24,120,720,5040,40320,362880};
        int index = 0;
        for(int i = 7; i >= 0; i--){
            int irow = i/3, icol = i - i/3*3;
            int count = 0;
            for(int j = 8; j > i; j--){
                int jrow = j/3, jcol = j - j/3*3;
                if(arr[jrow][jcol] < arr[irow][icol]){
                    count++;
                }
            }
            index += (count*fac[8-i]);
        }
        return index;
    }
public:
    // 广度优先搜索
    int BFS(){
        int step = 0;
        memset(allHash, 0, 362880);
        queue<Status> openTable;
        Status *closeTable = new Status;;
        Status *current = closeTable;
        Status *tmp;
        openTable.push(root);
        allHash[Cantor(root.status)] == 1;
        while(!openTable.empty()){
            tmp = new Status;
            *tmp = openTable.front();
            openTable.pop();
            step++;
            current->next = tmp;
            current = current->next;
            if(IsGoal(tmp) == 0){
                PrintPath(tmp);
                freeCloseTable(closeTable);
                return step;
            }
            int nextNumber = NextStatus(tmp);
            if(nextNumber == 0){
                continue;
            }
            for(int i = 0; i < nextNumber; i++){
                openTable.push(next[i]);
                allHash[Cantor(next[i].status)] == 1;
            }
        }
        cout << "BFS failed." << endl;
        freeCloseTable(closeTable);
        return -1;
    }
    // 深度优先搜索
    int DFS(){
        int depth = 0;
        int step = 0;
        stack<Status> openTable;
        Status *closeTable = new Status;;
        Status *current = closeTable;
        Status *last;
        Status *tmp;
        openTable.push(root);
        while(!openTable.empty()){
            tmp = new Status;
            *tmp = openTable.top();
            openTable.pop();
            step++;
            current->next = tmp;
            current = current->next;
            if(IsGoal(tmp) == 0){
                PrintPath(tmp);
                freeCloseTable(closeTable);
                return step;
            }
            memset(allHash, 0, 362880);
            last = tmp;
            depth = 0;
            while(last != NULL){
                allHash[Cantor(last->status)] = 1;
                last = last->parent;
                depth++;
            }
            if(depth > 8){
                continue;
            }
            int nextNumber = NextStatus(tmp);
            if(nextNumber == 0){
                continue;
            }
            for(int i = 0; i < nextNumber; i++){
                openTable.push(next[i]);
            }
        }
        cout << "DFS failed." << endl;
        freeCloseTable(closeTable);
        return -1;
    }
    // 启发式搜索
    int AStar(){
        int step = 0;
        memset(allHash, 0, 362880);
        vector<Status> openTable;
        Status *closeTable = new Status;;
        Status *current = closeTable;
        Status *tmp;
        openTable.push_back(root);
        allHash[Cantor(root.status)] == 1;
        while(!openTable.empty()){
            tmp = new Status;
            *tmp = openTable[openTable.size()-1];
            openTable.pop_back();
            step++;
            current->next = tmp;
            current = current->next;
            if(IsGoal(tmp) == 0){
                PrintPath(tmp);
                freeCloseTable(closeTable);
                return step;
            }
            int nextNumber = NextStatus(tmp);
            if(nextNumber == 0){
                continue;
            }
            for(int i = 0; i < nextNumber; i++){
                openTable.push_back(next[i]);
                allHash[Cantor(next[i].status)] == 1;
            }
            sort(openTable.begin(), openTable.end(), decComparator);
        }
        cout << "AStar failed." << endl;
        freeCloseTable(closeTable);
        return -1;
    }
private:
    // 打印路径
    void PrintPath(Status *head){
        if(head == NULL){
            return;
        }
        else{
            PrintPath(head->parent);
            for(int i = 0; i < 3; i++){
                for(int j = 0; j < 3; j++){
                    cout << head->status[i][j];
                }
                cout << endl;
            }
            cout <<endl;
        }
    }
    // 释放close表
    void freeCloseTable(Status *closeTable){
        Status *current;
        while(closeTable != NULL){
            current = closeTable->next;
            free(closeTable);
            closeTable = current;
        }
    }
};

int main()
{
    Status init = {
  
  2,8,3,1,6,4,7,0,5,0,NULL};
    Status goal = {
  
  1,2,3,8,0,4,7,6,5,0,NULL};
    EightPuzzle ep = EightPuzzle(&init, &goal);
    cout << "BFS********\n" << endl;
    cout << "step: " << ep.BFS() << endl;
    cout << "***********\n" << endl;
    cout << "DFS********\n" << endl;
    cout << "step: " << ep.DFS() << endl;
    cout << "***********\n" << endl;
    cout << "AStar******\n" << endl;
    cout << "step: " << ep.AStar() << endl;
    cout << "***********\n" << endl;
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/158091.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Delphi教程推荐

    Delphi教程推荐
    非常适宜Delphi初学者。选择Delphi开发同学的眼光是不错的,由于使用Delphi开发应用软件可以提高编译的效率,前提是你要好好学习Delphi教程,对你以后的开展肯定有很大帮助的。  Delphi(Delphi培训)是Borland公司研制的新一代可视化开发工具,它应用范围非常广,无论是Windows系统还是LINUX系统上都能完美运行。  书名:《Delphi2005程序设计教程》  作/译者:刘瑞新  出版社:机械工业出版社  出版日期:2005年07月  内容提要 

  • stm32f103替换_能力复用

    stm32f103替换_能力复用文章来源:刚接触STM32F103,在尝试编写“按键中断”和“PWM呼吸灯”程序的时候,发现例程都用到了管脚复用AFIO://打开管脚复用AFIORCC_APB2PeriphClockCmd(RCC_APB2Periph_AFIO,ENABLE);写到“232USART串口通信”程序时,当我非常自信的写下上面这句代码后,发现例程里面却没有这句话,很让人摸不着头脑……查了很多资料,加上

    2022年10月10日
  • Adobe Photoshop CC 打开时报错~配置错误:请卸载并重新安装该产品

    Adobe Photoshop CC 打开时报错~配置错误:请卸载并重新安装该产品

  • java多线程—Thread、Runnable和Callable区别

    多线程编程优点进程之间不能共享内存,但线程之间共享内存非常容易。系统创建线程所分配的资源相对创建进程而言,代价非常小。Java中实现多线程有3种方法:继承Thread类实现Runnable接口实现Callable接口(参考&lt;Java编程思想(第4版)&gt; 21.2.4章节,原来一直以为是2种,后来发现是3种)回到顶部第一种实现方法—继承Thread类继承Thread类,需要覆盖方法r…

  • 超声波倒车雷达原理[通俗易懂]

    超声波倒车雷达原理[通俗易懂]汽车倒车中使用的倒车雷达防撞报警系统即是俗称的倒车雷达,在汽车倒车时,超声波倒车雷采用超声波测距原理探测汽车尾部离障碍物的距离,是汽车泊车辅助装置。倒车时,当汽车尾部探测到障碍物时,倒车雷达就实时动态显示离障碍物的距离,达到设定的安全警告值时,倒车雷达立即发出报警声,以警示驾驶员,辅助驾驶员安全倒车。现在大多数都配置有倒车雷达。倒车雷达电路种类较多,本文介绍基于单片机控制的倒车雷达系统,该系统采用…

  • 用西尔特编程器解密芯片_配方法解一元二次方程

    用西尔特编程器解密芯片_配方法解一元二次方程z3-solver是由MicrosoftResearch(微软)开发的SMT求解器,它用于检查逻辑表达式的可满足性,可以找到一组约束中的其中一个可行解,缺点是无法找出所有的可行解(对于规划求解问题可以是scipy)。z3-solver可应用于软/硬件的验证与测试、约束求解、混合系统的分析、安全、生物,以及几何求解等问题。Z3主要由C++开发,提供了.NET、C、C++、Java、Python等语言调用接口,下面以python接口展开讲解。……

    2022年10月13日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号