八数码问题求解（1）深度优先搜索

jayce 发布于2019-06-26 18:12 / 2960人阅读

摘要：老师让用中方式都实现一遍，分别是广度优先搜索深度优先搜索和启发式搜索。先分享深度优先搜索，后两篇我会分享广度优先搜索和启发式搜索的实现。

人工智能课，第一个实验就是八数码问题。老师让用3中方式都实现一遍，分别是广度优先搜索、深度优先搜索和启发式搜索。心塞╮(╯▽╰)╭。紧急补了一些数据结构的知识，就匆匆上阵。先分享深度优先搜索，后两篇我会分享广度优先搜索和启发式搜索的实现。

概念就不讲了，百度就行了。简单说一下我的实现：Situation类存储节点信息，包括父节点的code值（code是一个字符串，存储的是八数码的状态，比如“138427056”），当前节点的code值，以及深度（深度从0开始，即起始节点深度为0）；在Test.cpp的main函数中，我定义了两个链表open和closed分别存放未被扩展的节点和被扩展的节点。深度优先，新生成的有效的子节点存放在open表的开头。每次扩展，拿open表的开头的那个节点来扩展，方法是把open表的头节点移动到closed表的末端，生成的最多4个有效的子节点存放在open表的开头。其他就是比较生成的节点和目标节点是否相等了。

以下代码在win8.1下VS2013中测试成功。

头文件Deep.h：

#include
#include"queue"
#include"string"
#include

using namespace std;

const string GOAL = "803214765";

class Situation{
private:
    
public:
    string father;
    string code;//当前状态
    int deep;
    Situation up();
    Situation down();
    Situation left();
    Situation right();
    bool isGoal();
    bool isInOpen(deque &open);
    bool isInClosed(deque &closed);
    void show() const;
    void show(string) const;
    void show_deque(deque &) const;
    deque showWay(deque &closed);
    void showAnswer(deque &closed);//显示解答
    Situation() :father(""), code(""), deep(-1){};
};

Deep.cpp：

#include"Deep.h"

Situation Situation::up(){
    string::size_type loc = code.find("0");//0的位置,从0开始计数
    Situation son;
    son.code = code;
    son.deep = deep + 1;
    if (loc>=3){
        char temp = son.code[loc];//即0
        son.code[loc] = son.code[loc - 3];
        son.code[loc-3] = temp;
    }
    else{
        son.code = "";
    }
    return son;
}

Situation Situation::down(){
    string::size_type loc = code.find("0");//0的位置,从0开始计数
    Situation son;
    son.code = code;
    son.deep = deep + 1;
    if (loc<=5){
        char temp = son.code[loc];//即0
        son.code[loc] = son.code[loc + 3];
        son.code[loc + 3] = temp;
    }
    else{
        son.code = "";
    }
    return son;
}

Situation Situation::left(){
    string::size_type loc = code.find("0");//0的位置,从0开始计数
    Situation son;
    son.code = code;
    son.deep = deep + 1;
    if (loc!=0&&loc!=3&&loc!=6){
        char temp = son.code[loc];//即0
        son.code[loc] = son.code[loc - 1];
        son.code[loc - 1] = temp;
    }
    else{
        son.code = "";
    }
    return son;
}

Situation Situation::right(){
    string::size_type loc = code.find("0");//0的位置,从0开始计数
    Situation son;
    son.code = code;
    son.deep = deep + 1;
    if (loc!=2&&loc!=5&&loc!=8){
        char temp = son.code[loc];//即0
        son.code[loc] = son.code[loc + 1];
        son.code[loc + 1] = temp;
    }
    else{
        son.code = "";
    }
    return son;
}

bool Situation::isGoal(){
    return code == GOAL;
}

bool Situation::isInOpen(deque &open){
    /*deque::iterator it = open.begin();
    while (it != open.end()){
        if (code == (*it).code){
            return true;
        }
        it++;
    }*/
    for (int i = 0; i < open.size();i++){
        if (code==open.at(i).code){
            return true;
        }
    }
    return false;
}

bool Situation::isInClosed(deque &closed){
    /*deque::iterator it = closed.begin();
    while (it!=closed.end()){
        if (code == (*it).code){
            return true;
        }
        it++;
    }*/
    for (int i = 0; i < closed.size(); i++){
        if (code == closed.at(i).code){
            return true;
        }
    }
    return false;
}

void Situation::show() const{
    if (!code.empty()){
        cout << code[0] << code[1] << code[2] << endl
            << code[3] << code[4] << code[5] << endl
            << code[6] << code[7] << code[8] << endl << endl;
    }
    else{
        cout << "空的" << endl;
    }
}

void Situation::show(string code) const{
    if (!code.empty()){
        cout << code[0] << code[1] << code[2] << endl
            << code[3] << code[4] << code[5] << endl
            << code[6] << code[7] << code[8] << endl << endl;
    }
    else{
        cout << "空的" << endl;
    }
}

void Situation::show_deque(deque &m_deque) const{
    /*deque::iterator it = m_deque.begin();
    while (it!=m_deque.end())
    {
        (*it).show();
        it++;
    }*/
    for (int i = 0; i < m_deque.size();i++){
        m_deque.at(i).show();
    }
}

//路径
deque Situation::showWay(deque &closed){
    //cout << closed.size() << endl;
    deque dequeList;
    Situation temp = closed.back();
    dequeList.push_back(temp);

    //closed表从后往前，根据father值找到路径
    for (int i = closed.size()-1; i >= 0;i--){
        if (temp.father==closed.at(i).code){
            dequeList.push_back(closed.at(i));
            temp = closed.at(i);
        }
    }
    //cout << dequeList.size() << endl;
    return dequeList;
}

void Situation::showAnswer(deque &closed){
    deque way(showWay(closed));
    cout << "共需要" << way.size() << "步" << endl;
    for (int i = way.size() - 1; i >= 0; i--)
    {
        way.at(i).show();
    }
    //输出目标
    show(GOAL);
}

Test.cpp:

#include
#include"Deep.h"

using namespace std;

void loop(deque &open, deque &closed, int range);

int main(){
    string original = "283164705";
    Situation first;
    deque open, closed;//open存放未扩展节点，closed存放已扩展节点
    int range = 10;//深度界限

    first.code = original;
    first.deep = 0;
    open.push_back(first);
    loop(open,closed,range);
    return 0;
}

void loop(deque &open, deque &closed,int range){
    Situation a;
    int i = 0;
    while (!open.empty()){
        cout << i++ << endl;
        if (open.front().code == GOAL){
            cout << "成功：" << endl;
            a.showAnswer(closed);
            return;
        }
        if (open.empty()){
            cout << "失败" << endl;
            return;
        }
        closed.push_back(open.front());
        open.pop_front();
        //节点n的深度是否等于深度界限
        if (closed.back().deep == range){
            //loop(open,closed,range);不能用递归
            continue; 
        }
        else{
            //扩展节点n,把其后裔节点放入OPEN表的末端
            Situation son1 = closed.back().up();
            Situation son2 = closed.back().down();
            Situation son3 = closed.back().left();
            Situation son4 = closed.back().right();
            /*
            广度优先搜索和深度优先搜索的唯一区别就是子节点放到open表的位置：
            （1）广度优先搜索放到open表的后面
            （2）深度优先搜索放到open表的前面
            */
            if (!son1.code.empty()){
                if (!son1.isInOpen(open)&&!son1.isInClosed(closed)){
                    son1.father = closed.back().code;
                    open.push_front(son1);
                }
            }
            if (!son2.code.empty()){
                if (!son2.isInOpen(open) && !son2.isInClosed(closed)){
                    son2.father = closed.back().code;
                    open.push_front(son2);
                }
            }
            if (!son3.code.empty()){
                if (!son3.isInOpen(open) && !son3.isInClosed(closed)){
                    son3.father = closed.back().code;
                    open.push_front(son3);
                }
            }
             if (!son4.code.empty()){
                if (!son4.isInOpen(open) && !son4.isInClosed(closed)){
                    son4.father = closed.back().code;
                    open.push_front(son4);
                }
                
            }
            //是否有任何后继节点为目标节点
            if (son1.isGoal()){
                cout << "后继节点中有目标节点：" << endl;
                son1.showAnswer(closed);
                break;
            }
            if (son2.isGoal()){
                cout << "后继节点中有目标节点：" << endl;
                son2.showAnswer(closed);
                break;
            }
            if (son3.isGoal()){
                cout << "后继节点中有目标节点：" << endl;
                son3.showAnswer(closed);
                break;
            }
            if (son4.isGoal()){
                cout << "后继节点中有目标节点：" << endl;
                son4.showAnswer(closed);
                break;
            }
        }
    }
}

GPU云服务器云服务器深度优先搜索广度优先搜索最佳优先搜索算法广度优先搜索算法代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/19590.html

基于JavaScript求解八数码最短路径并生成动画效果

摘要：写在最前本次分享一下通过广度优先搜索解决八数码问题并展示其最短路径的动画效果。一个排列中逆序的总数就称为这个排列的逆序数。如果起始状态与结束状态的逆序数的奇偶性相同，则说明状态可达，反之亦然。写在最前本次分享一下通过广度优先搜索解决八数码问题并展示其最短路径的动画效果。欢迎关注我的博客，不定期更新中—— 效果预览该效果为从[[2, 6, 3],[4, 8, 0],[7, 1, ...

Jioby 2019-08-26 11:30 评论0 收藏0
人工智能导论 (七) - 搜索求解策略

摘要：搜索的概念盲目搜索与启发式搜索状态空间知识表示法状态空间的表示法状态空间的图描述启发式图搜索启发式策略运用启发式策略的两种基本情况启发信息和估价函数启发信息估价函数注意八数码问题的启发函数搜索算法搜索算法及其特性分析可采纳性单调性信息性 showImg(https://segmentfault.com/img/remote/1460000017465711);showImg(https...

yanwei 2019-08-16 14:03 评论0 收藏0
如何求ABC的全排列？--如何理解回溯算法？

摘要：它真的是深度优先搜索吗是真的吗是真的如果是的话，那它的搜索空间解空间是什么是向量组成的集合，而。既然深度优先搜索剪枝回溯。什么是全排列？从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。那么ABC的全排列有哪些？根据定义得到：ABCACBBACBCACABCBA 如何通过程序求解？方法一：暴力...

zero 2019-08-16 16:22 评论0 收藏0
算法思想

摘要：基础算法思想类别递推枚举递归分治贪婪回溯试探模拟递推递推分类顺推法从已知条件出发，逐步推算出要解决问题的方法。贪心算法的局限不能保证最后的解是最优的不能求最大最小解问题只能求满足某些约束条件的可行解范围。基础算法思想类别递推枚举递归分治贪婪回溯（试探）模拟递推递推分类顺推法：从已知条件出发，逐步推算出要解决问题的方法。逆推法：从已知结果出发，用迭代表达式...

sshe 2019-08-15 17:50 评论0 收藏0
《AI之矛》（1）【数独Agent】

摘要：而此处针对进一步的搜索，有两个问题需要考虑如何选取搜索起点方格确定哪种搜索策略深度优先搜索，广度优先搜索关于第一个问题，无论选择哪个方格起始搜索，对于能否解决问题来说并不存在差异。 Github仓库地址学习是为了寻找解决问题的答案，若脱离了问题只为知晓而进行的打call，那么随时间流逝所沉淀下来的，估计就只有重在参与的虚幻存在感了，自学的人就更应善于发现可供解决的问题。为了入门AI，...

CatalpaFlat 2019-07-30 15:36 评论0 收藏0