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 {
    //節(jié)點類，收集所有的不同的被需要的元素，例如估計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)
//結(jié)合歸并排序，把兩個容器混合成一個
{
    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)
//調(diào)用上面的歸并排序
{
    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)
//擴展所有節(jié)點
{
    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 << "拓展節(jié)點： " << 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)   //檢查確定不是父節(jié)點（重復(fù)的狀態(tài)）
            {
                right1 = true;
                if (heurType == 1)  //等代價搜索（只有深度代價h，沒有節(jié)點之間代價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，沒有節(jié)點之間代價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)   //沒有重復(fù)
        {
            up1 = true;
            if (heurType == 1)  //等代價搜索（只有深度代價h，沒有節(jié)點之間代價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)   //沒有重復(fù)
        {
            down1 = true;
            if (heurType == 1)      //等代價搜索（只有深度代價h，沒有節(jié)點之間代價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) //只添加已經(jīng)生成的節(jié)點
    {
        a.push(right);
    }
    if (left1)
    {
        a.push(left);
    }
    if (up1)
    {
        a.push(up);
    }
    if (down1)
    {
        a.push(down);
    }
    if (heurType != 1)  //因為啟發(fā)式搜索成本會變化，所以不對等代價搜索排序
    {
        orderSort(a);
    }
}

void mySearch(vector<int> &start, vector<int> &finish, int &blank, int &score)
{
    queue<Node> work;   //所有節(jié)點的隊列OPEN
    vector<int> par;
    work.push(Node(start, 0, 0, 0, 0, blank, par));     //創(chuàng)建初始節(jié)點
    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)//目標(biāo)狀態(tài)
            {
                done = true;
                success = true;
            }
            else
            {
                move(temp, work, finish, score);    //拓展當(dāng)前節(jié)點
                ++added;            //看看我們已經(jīng)探索的節(jié)點數(shù)
            }
        }
        else
        {
            done = true;
            success = false;
        }
    }
    if (success)        //目標(biāo)找到
    {
        cout << "發(fā)現(xiàn)目標(biāo)" << endl;
        cout << "求結(jié)這個問題算法探索了 " << added << " 個節(jié)點。" << endl;
        cout << "隊列中節(jié)點數(shù)峰值為" << maxSize << "。" << endl;
        cout << "目標(biāo)節(jié)點的深度是" << 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) //異常值報錯并循環(huán)請求
    {
        cout << "輸入了無效字符，請重新輸入當(dāng)前行";
        temp.clear();       //清空本次輸入
        getInput(temp);
    }
    for (int i = 0; i < temp.size(); ++i) //真正存儲當(dāng)前圖
    {
        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 << "請輸入你的初始狀態(tài)，用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) //查看空格數(shù)量
        {
            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;   //目標(biāo)狀態(tài)
    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. 寬度優(yōu)先搜索" << 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;
}