A_star算法（人工智能1）

01.png
02.png
03.png
04.png
05.png
06.png
07.png
08.png
09.png
10.png
11.png

head.h

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <list>
#include <algorithm>


using namespace std;

class Node {
    //节点类，收集所有的不同的被需要的元素，例如估计s->n最小代价g，n-1->n估计最小代价h,深度
public:
    vector<int> state;
    int gn;
    int hn;
    int depth;
    int total;
    int blank;
    vector<int> parent;
    Node(vector<int> a, int b, int c, int d, int e, int f, vector<int> g)
    {
        this->state = a;
        this->gn = b;
        this->hn = c;
        this->depth = d;
        this->total = e;
        this->blank = f;
        this->parent = g;
    }
};

vector<Node> merge(vector<Node> a, vector<Node> b)
//结合归并排序，把两个容器混合成一个
{
    vector<Node> c;
    int i = 0;
    int j = 0;
    while ((i < a.size()) && (j < b.size()))
    {
        Node look = a.at(i);
        Node there = b.at(j);
        if (look.total > there.total)
        {
            c.push_back(there);
            ++j;
        }
        else
        {
            c.push_back(look);
            ++i;
        }
    }
    while (i < a.size())
    {
        Node look = a.at(i);
        c.push_back(look);
        ++i;
    }
    while (j < b.size())
    {
        Node there = b.at(j);
        c.push_back(there);
        ++j;
    }
    return c;
}

vector<Node> mergesort(vector<Node> arr)
//归并排序
{
    if (arr.size() == 1)
    {
        return arr;
    }
    vector<Node> l1;
    int left = arr.size() / 2;
    for (int i = 0; i < left; ++i)
    {
        l1.push_back(arr.at(i));
    }
    vector<Node> r1;
    for (int i = left; i < arr.size(); ++i)
    {
        r1.push_back(arr.at(i));
    }
    l1 = mergesort(l1);
    r1 = mergesort(r1);

    return merge(l1, r1);
}

void orderSort(queue<Node> &input)
//调用上面的归并排序
{
    vector<Node> holder;
    while (input.size() > 0)
    {
        holder.push_back(input.front());
        input.pop();
    }
    holder = mergesort(holder);
    for (int i = 0; i < holder.size(); ++i)
    {
        input.push(holder.at(i));
    }
}

int manDist(vector<int> a, vector<int> &b)
//计算曼哈顿距离
{
    int goal[3][3] = { { 1, 2, 3 },{ 4, 5, 6 },{ 7, 8, 0 } };
    int comp[3][3] = { { a.at(0), a.at(1), a.at(2) },{ a.at(3), a.at(4), a.at(5) },{ a.at(6), a.at(7), a.at(8) } };
    int totaldiff = 0;
    int deltx = 0;
    int delty = 0;
    int look = 0;
    for (int k = 0; k < 3; ++k)
    {
        for (int l = 0; l < 3; ++l)
        {
            look = comp[k][l];
            for (int i = 0; i < 3; ++i)
            {
                for (int j = 0; j < 3; ++j)
                {
                    if (goal[i][j] == look)
                    {
                        deltx = abs(k - i);
                        delty = abs(l - j);
                        totaldiff = (totaldiff + (deltx + delty));
                    }
                }
            }
        }
    }
    return totaldiff;
}

int missPlaced(vector<int> a, vector<int> &b)
//错位距离
{
    int diff = 0;
    for (int i = 0; i < a.size(); ++i)
    {
        if (a.at(i) != b.at(i))
        {
            ++diff;
        }
    }
    return diff;
}

void move(Node expand, queue<Node> &a, vector<int> &b, int &heurType)
//扩展所有节点
{
    int expandgn = expand.gn;
    int expandhn = expand.hn;
    int expandDepth = expand.depth;
    int expandTotal = expand.total;
    int expandBlank = expand.blank;
    int check = expand.blank;
    vector<int> modify = expand.state;
    vector<int> use = modify;
    Node right = Node(use, 1, 0, 1, 1, 1, modify);
    bool right1 = false;
    Node left = Node(use, 1, 0, 1, 1, 1, modify);
    bool left1 = false;
    Node up = Node(use, 1, 0, 1, 1, 1, modify);
    bool up1 = false;
    Node down = Node(use, 1, 0, 1, 1, 1, modify);
    bool down1 = false;
    //输出拓展情况
    /*cout << "拓展节点： " << endl;
    for(int i=0; i < modify.size(); ++i) //
    {
    if((i == 3) || (i == 6))
    {
    cout << endl;
    }
    cout << modify.at(i) << " ";
    }
    cout << endl;
    cout << " g(n) = " << expandgn << "  h(n) = " << expandhn << endl;*/
    int temp = 0;
    int missHeur = 0;
    int manHeur = 0;
    expandgn = expandgn + 1;
    if (check + 1 <= 8)
        //检查能否向右边移动
    {
        if ((check != 2) && (check != 5))
            //不在边上
        {
            temp = use.at(check);
            use.at(check) = use.at(check + 1);
            use.at(check + 1) = temp;
            if (use != expand.parent)   //检查确定不是父节点（重复的状态）
            {
                right1 = true;
                if (heurType == 1)  //等代价搜索（只有深度代价h，没有节点之间代价g）
                {
                    right = Node(use, expandgn, 0, (expandDepth + 1), expandgn, (expandBlank + 1), modify);
                }
                else if (heurType == 2) //错位距离
                {
                    missHeur = missPlaced(use, b);
                    right = Node(use, expandgn, missHeur, (expandDepth + 1), (expandgn + missHeur), (expandBlank + 1), modify);
                }
                else    //曼哈顿距离
                {
                    manHeur = manDist(use, b);
                    right = Node(use, expandgn, manHeur, (expandDepth + 1), (expandgn + manHeur), (expandBlank + 1), modify);
                }
            }
        }
    }
    use = modify;
    if (check - 1 >= 0) //可以左移
    {
        if ((check != 3) && (check != 6))   //不在边上
        {
            temp = use.at(check);
            use.at(check) = use.at(check - 1);
            use.at(check - 1) = temp;
            if (use != expand.parent)
            {
                left1 = true;
                if (heurType == 1)  //等代价搜索（只有深度代价h，没有节点之间代价g）
                {
                    left = Node(use, expandgn, 0, (expandDepth + 1), expandgn, (expandBlank - 1), modify);
                }
                else if (heurType == 2) //错位距离
                {
                    missHeur = missPlaced(use, b);
                    left = Node(use, expandgn, missHeur, (expandDepth + 1), (expandgn + missHeur), (expandBlank - 1), modify);
                }
                else        //曼哈顿距离
                {
                    manHeur = manDist(use, b);
                    left = Node(use, expandgn, manHeur, (expandDepth + 1), (expandgn + manHeur), (expandBlank - 1), modify);
                }
            }
        }
    }
    use = modify;
    if (check + 3 <= 8)     //可以上移
    {
        temp = use.at(check);
        use.at(check) = use.at(check + 3);
        use.at(check + 3) = temp;
        if (use != expand.parent)   //没有重复
        {
            up1 = true;
            if (heurType == 1)  //等代价搜索（只有深度代价h，没有节点之间代价g）
            {
                up = Node(use, expandgn, 0, (expandDepth + 1), (expandgn + 1), (expandBlank + 3), modify);
            }
            else if (heurType == 2)     //错位距离
            {
                missHeur = missPlaced(use, b);
                up = Node(use, expandgn, missHeur, (expandDepth + 1), (expandgn + missHeur), (expandBlank + 3), modify);
            }
            else        //曼哈顿距离
            {
                manHeur = manDist(use, b);
                up = Node(use, expandgn, manHeur, (expandDepth + 1), (expandgn + manHeur), (expandBlank + 3), modify);
            }
        }
    }
    use = modify;
    if (check - 3 >= 0) //可以向下移
    {
        temp = use.at(check);
        use.at(check) = use.at(check - 3);
        use.at(check - 3) = temp;
        if (use != expand.parent)   //没有重复
        {
            down1 = true;
            if (heurType == 1)      //等代价搜索（只有深度代价h，没有节点之间代价g）
            {
                down = Node(use, expandgn, 0, (expandDepth + 1), (expandgn + 1), (expandBlank - 3), modify);
            }
            else if (heurType == 2)     //错位距离
            {
                missHeur = missPlaced(use, b);
                down = Node(use, expandgn, missHeur, (expandDepth + 1), (expandgn + missHeur), (expandBlank - 3), modify);
            }
            else        //曼哈顿距离
            {
                manHeur = manDist(use, b);
                down = Node(use, expandgn, manHeur, (expandDepth + 1), (expandgn + manHeur), (expandBlank - 3), modify);
            }
        }
    }
    if (right1) //只添加已经生成的节点
    {
        a.push(right);
    }
    if (left1)
    {
        a.push(left);
    }
    if (up1)
    {
        a.push(up);
    }
    if (down1)
    {
        a.push(down);
    }
    if (heurType != 1)  //因为启发式搜索成本会变化，所以不对等代价搜索排序
    {
        orderSort(a);
    }
}

void mySearch(vector<int> &start, vector<int> &finish, int &blank, int &score)
{
    queue<Node> work;   //所有节点的队列OPEN
    vector<int> par;
    work.push(Node(start, 0, 0, 0, 0, blank, par));     //创建初始节点
    Node temp = work.front();
    bool done = false;
    bool success = false;
    int added = 0;
    int maxSize = work.size();
    while (!done)           //没有找到
    {
        if (work.size() > maxSize)      //最大队列长度
        {
            maxSize = work.size();
        }

        if (work.size() > 0)        //队列长度大于0
        {
            temp = work.front();
            work.pop();
            if (temp.state == finish)//目标状态
            {
                done = true;
                success = true;
            }
            else
            {
                move(temp, work, finish, score);    //拓展当前节点
                ++added;            //看看我们已经探索的节点数
            }
        }
        else
        {
            done = true;
            success = false;
        }
    }
    if (success)        //目标找到
    {
        cout << "发现目标" << endl;
        cout << "求结这个问题算法探索了 " << added << " 个节点。" << endl;
        cout << "队列中节点数峰值为" << maxSize << "。" << endl;
        cout << "目标节点的深度是" << temp.depth << "" << endl;
    }
}

main.cpp

#include "head.h"
#include <time.h>

#include <iostream>
using namespace std;
void getInput(vector<int> &store) //接收用户输入
{
    char input;
    int keep;
    bool invalid = false;
    vector<int> temp;
    for (int i = 0; i < 3; ++i)
    {
        cin >> input;
        if ((input < '0') || (input > '8') && (input != ' ')) //异常值检查
        {
            invalid = true;
        }
        else
        {
            if (input != ' ') //临时存储图
            {
                keep = input - '0';
                temp.push_back(keep);
            }
        }
    }
    if (invalid) //异常值报错并循环请求
    {
        cout << "输入了无效字符，请重新输入当前行";
        temp.clear();       //清空本次输入
        getInput(temp);
    }
    for (int i = 0; i < temp.size(); ++i) //真正存储当前图
    {
        store.push_back(temp.at(i));
    }
}

int main()
{
    cout << "示例：" << endl << "4 1 3 " << endl << "7 5 0 " << endl << "8 2 6" << endl;
    cout << "1. **Uniform cost search:**" << endl;
    cout << "* _Goal_ = found" << endl;
    cout << "* _Nodes expanded_ = 395*"<<endl;
    cout<< "_Max number of nodes in queue_ = 312" << endl;
    cout << "2. **A* with misplaced heuristic : **" << endl;
    cout << "* _Goal_ = found" << endl;
    cout << "* _Nodes expanded_ = 26" << endl;
    cout << "* _Max number of nodes in queue_ = 24" << endl;
    cout << "3. **A* with manhattan distance : **" << endl;
    cout << "* _Goal_ = found" << endl;
    cout << "* _Nodes expanded_ = 22" << endl;
    cout << "* _Max number of nodes in queue_ = 21" << endl << endl;

    vector<int> init;
    cout << "请输入你的初始状态，用0表示空的格" << endl;
    bool okay = false;
    int counter = 0;
    while (!okay) //获取用户输入
    {
        counter = 0;
        cout << "输入第一行：";
        getInput(init);
        cout << "第二行：";
        getInput(init);
        cout << "三：";
        getInput(init);
        for (int i = 0; i < init.size(); ++i) //查看空格数量
        {
            if (init.at(i) == 0)
            {
                counter++;
            }
        }
        if (counter == 0)
        {
            cout << "你没输入空格，请重新输入" << endl;
            init.clear();
        }
        else if (counter == 1)
        {
            okay = true;
        }
        else
        {
            cout << "你输入不只一个空格，请重新输入" << endl;
            init.clear();
        }
    }
    cout << endl << "你输入的图是 " << endl;
    for (int i = 0; i < init.size(); ++i) //输出初始图
    {
        if ((i == 3) || (i == 6))
        {
            cout << endl;
        }
        cout << init.at(i) << " ";
    }
    cout << endl;
    vector<int> goal;   //目标状态
    for (int i = 1; i < init.size(); ++i)
    {
        goal.push_back(i);
    }
    goal.push_back(0);
    int blankLoc = 0;   //找出空白位置
    for (int i = 0; i < init.size(); ++i)
    {
        if (init.at(i) == 0)
        {
            blankLoc = i;
        }
    }
    cout << "你的空格在： " << blankLoc << endl << endl;
    okay = false;
    int choice = 0;
    while (!okay)
    {
        cout << "请选择你想用哪一个算法 " << endl;
        cout << "1. 宽度优先搜索" << endl;
        cout << "2. 用错位误差的A*" << endl;
        cout << "3. 用曼哈顿距离的A*" << endl;
        cout << "你选的是：";
        cin >> choice;
        if ((choice >= 1) && (choice <= 3))
        {
            okay = true;
        }
        else
        {
            cout << "选择无效" << endl;
        }
    }
    cout << endl;
    //计算运行时间
    clock_t start, finish;
    double totaltime;
    start = clock();
    if (choice == 1)
    {

        mySearch(init, goal, blankLoc, choice);

    }
    else if (choice == 2)
    {
        mySearch(init, goal, blankLoc, choice);
    }
    else
    {
        mySearch(init, goal, blankLoc, choice);
    }
    finish = clock();
    totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
    cout << "此程序的运行时间为" << totaltime << "秒！" << endl;
    char hh;
    cin>>hh;
    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 215,012评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,628评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,653评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,485评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,574评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,590评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,596评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,340评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,794评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,102评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,276评论 1赞 344
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,940评论 5赞 339
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,583评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,201评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,441评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,173评论 2赞 366
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,136评论 2赞 352