一、实验目的

熟悉和掌握启发式搜索的定义、估价函数和算法过程，并利用A*算法求解N数码难题，理解求解流程和搜索顺序。

二、实验内容

以 8 数码问题和 15 数码问题为例实现 A*算法的求解程序，要求设计多种不同的估价函数。

三、实验要求

1.设置相同的初始状态和目标状态，针对不同的估价函数，求得问题的解，比较它们对搜索算法性能的影响，包括扩展节点数、生成节点数等，填入附表 4.1

2. 实现 A*算法求解 15数码问题的程序，设计两种不同的估价函数，然后重复上述1和2的实验内容，把结果填入 4.2

四、实验报告要求

1. 分析不同的估计函数对 A*算法性能的影响。

2. 根据宽度优先算法和 A*算法求解 8、15 数码问题的结果，分析启发式搜索的特点。

3. 代码流程图

4. 完整代码

(1)Bfs求八数码的源代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <string.h>
#include <stack>
using namespace std;

int ex_num;
int out_num;
int min_step;
bool flag = true;
stack<string> record;

string bfs(string start) {
    int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
    char op[4] = { 'u', 'r', 'd', 'l' };

    string end = "12345678x";
    unordered_map<string, int> dist; //该状态到起点的步数
    unordered_map<string, pair<string, char>> prev; //存储一个元素由哪种状态,经过哪种操作得来

    queue<string> open;
    queue<string> closed;

    open.push(start);
    dist[start] = 0;

    while (!open.empty()) {
        auto t = open.front();
        closed.push(t);
        open.pop();

        string state = t;
        int step = dist[state];

        if (state == end) {
            ex_num = open.size();
            out_num = closed.size(); min_step = step;
            break;
        }

        int x, y;
        for (int i = 0; i < state.size(); i++)
            if (state[i] == 'x') {
                x = i / 3, y = i % 3; // x,y 存横纵坐标
                break;
            }
        string source = state; // 原状态
        for (int i = 0; i < 4; i++) { // 每个状态最多可扩展上下左右 4 个状态
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                // (x,y)和(a,b)交换位置(在一维数组中)
                swap(state[x * 3 + y], state[a * 3 + b]);
                // 如果此状态之前没被扩展过就扩展，如果之前被扩展过但距离比较大就优化
                if (!dist.count(state) || dist[state] > step + 1) {
                    dist[state] = step + 1;
                    prev[state] = { source, op[i] };
                    open.push(state);
                }
                swap(state[x * 3 + y], state[a * 3 + b]);
            }
        }
    }
    string res;
    while (end != start) {
        res += prev[end].second;
        record.push(end);
        end = prev[end].first;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    string start, c, seq;
    string s0;
    puts("请输入初始状态");
    while (1) {
        cin >> c; // 输入时两数之间需要加空格 start += c;
        if (c != "x") seq += c;
        char s = getchar();
        if (s == '\n') break;
    }
    s0 = start;
    int t = 0;
    for (int i = 0; i < seq.size(); i++)
        for (int j = i + 1; j < seq.size(); j++)
            if (seq[i] > seq[j])
                t++;

    if (t & 1) puts("无法从初始状态走到最终状态");
    else {
        clock_t begin_time, finish_time;
        begin_time = clock();
        cout << "最优解的操作为：" << bfs(start) << endl;
        finish_time = clock();
        cout << "其中最优解的操作是对空格'x'的操作：u 表示上,d 表示下,l 表示左,r 表示右" << endl;
        puts("");
        cout << "最小步数为" << min_step << endl;
        puts("");
        cout << "扩展节点数：" << ex_num << endl;
        cout << "生成节点数：" << out_num << endl;
        puts("");
        cout << "状态运行过程展示：" << endl;
        puts("");
        cout << "初始状态为：" << endl;
        for (int k = 0; k < 9; k++) {
            if (s0[k] == 'x') cout << 'x';
            else cout << s0[k] - '0';
            if ((k + 1) % 3 == 0) cout << endl;
        }
        puts("");
        for (int i = 0; i < min_step; i++) {
            cout << "第" << i + 1 << "步的迷宫状态为：" << endl;;
            string s = record.top();
            record.pop();
            for (int k = 0; k < 9; k++) {
                if (s[k] == 'x') cout << 'x';
                else cout << s[k] - '0';
                if ((k + 1) % 3 == 0) cout << endl;
            }
            puts("");
        }
        cout << "运行时间为：" << finish_time - begin_time << "毫秒" << endl;
    }
    return 0;
}

(2) A*算法求解八数码问题源代码

#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <time.h>
#include <string.h>
#include <stack>
using namespace std;

int ex_num;
int out_num;
int min_step;
bool flag = true;
stack<string> record;

/*
int f(string state) {
    if (flag) {
        puts("");
        puts("估价函数 1 的运行结果：");
    }
    flag = false;
    int res = 0;
    for (int i = 0; i < state.size(); i++)
        if (state[i] != 'x') {
            int t = state[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    return res;
}
*/

/*
int f(string state) {
    if (flag) {
        puts("");
        puts("估价函数 2 的运行结果：");
    }
    flag = false;
    int res = 0;
    string end = "12345678x";
    for (int i = 0; i < state.size(); i++)
        if (state[i] != end[i])
            res++;
    return res;
}
*/

int f(string state) {
    if (flag) {
        puts("");
        puts("估价函数 3 的运行结果：");
    }
    flag = false;
    int res = 0, p;
    p = state.find('x');
    while (1) {
        if (p != 8) {
            res++;
            for (int i = 0; i < 9; i++)
                if (state[i] == '1' + p) {
                    swap(state[i], state[p]);
                    p = i;
                    break;
                }
        } else {
            bool st = false;
            for (int i = 0; i < 8; i++) {
                if (state[i] == '1' + i) continue;
                st = true;
                swap(state[p], state[i]);
                p = i;
                res++;
            }
            if (!st) break;
        }
    }
    return res;
}

string bfs(string start) {
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
    char op[4] = {'u', 'r', 'd', 'l'};

    string end = "12345678x";
    unordered_map<string, int> dist;
    unordered_map<string, pair<string, char>> prev;
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> open;
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> closed;

    open.push({f(start), start});
    dist[start] = 0;

    while (open.size()) {
        auto t = open.top();
        closed.push(t);
        open.pop();

        string state = t.second;
        int step = dist[state];

        if (state == end) {
            ex_num = open.size();
            out_num = closed.size();
            min_step = step;
            break;
        }

        int x, y;
        for (int i = 0; i < state.size(); i++)
            if (state[i] == 'x') {
                x = i / 3, y = i % 3;
                break;
            }
        string source = state;
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < 3 && b >= 0 && b < 3) {
                if (!dist.count(state) || dist[state] > step + 1) {
                    dist[state] = step + 1;
                    prev[state] = {source, op[i]};
                    open.push({dist[state] + f(state), state});
                }
                swap(state[x * 3 + y], state[a * 3 + b]);
            }
        }
    }
    string res;
    while (end != start) {
        res += prev[end].second;
        record.push(end);
        end = prev[end].first;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    string start, c, seq;
    string s0;
    puts("请输入初始状态");
    while (1) {
        cin >> c;
        start += c;
        if (c != "x") seq += c;
        char s = getchar();
        if (s == '\n') break;
    }
    s0 = start;
    int t = 0;
    for (int i = 0; i < seq.size(); i++)
        for (int j = i + 1; j < seq.size(); j++)
            if (seq[i] > seq[j]) t++;

    if (t & 1)
        puts("无法从初始状态走到最终状态");
    else {
        clock_t begin_time, finish_time;
        begin_time = clock();
        cout << "最优解的操作为：" << bfs(start) << endl;
        finish_time = clock();
        cout << "其中最优解的操作是对空格'x'的操作：u 表示上,d 表示下,l 表示左,r 表示右" << endl;
        puts("");
        cout << "最小步数为" << min_step << endl;
        puts("");
        cout << "扩展节点数：" << ex_num << endl;
        cout << "生成节点数：" << out_num << endl;
        puts("");
        cout << "状态运行过程展示：" << endl;
        puts("");
        cout << "初始状态为：" << endl;
        for (int k = 0; k < 9; k++) {
            if (s0[k] == 'x') cout << 'x';
            else cout << s0[k] - '0';
            if ((k + 1) % 3 == 0) cout << endl;
        }
        puts("");
        for (int i = 0; i < min_step; i++) {
            cout << "第" << i + 1 << "步的迷宫状态为：" << endl;;
            string s = record.top();
            record.pop();
            for (int k = 0; k < 9; k++) {
                if (s[k] == 'x') cout << 'x';
                else cout << s[k] - '0';
                if ((k + 1) % 3 == 0) cout << endl;
            }
            puts("");
        }
        cout << "运行时间为：" << finish_time - begin_time << "毫秒" << endl;
    }
    return 0;
}

估价函数一的运行结果

估价函数二的运行结果

估价函数三的运行结果

(3) Bfs 求十五数码的源代码

#include <cstring> 
#include <iostream> 
#include <algorithm> 
#include <queue> 
#include <unordered_map> 
#include <time.h> 
#include <string.h> 
#include <stack> 

using namespace std; 

int ex_num; 
int out_num; 
int min_step; 
bool flag = true; 
stack<string> record; 

string bfs(string start) { 
    int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 }; 
    char op[4] = { 'u', 'r', 'd', 'l' }; 

    string end = "123456789abcdefx"; 
    unordered_map<string, int> dist; //该状态到起点的步数 
    unordered_map<string, pair<string, char>> prev; //存储一个元素由哪种状态,经过哪种操作得来 

    queue<string> open; 
    queue<string> closed; 
    open.push({ start }); 
    dist[start] = 0; 

    while (open.size()) { 
        auto t = open.front(); 
        closed.push(t); 
        open.pop(); 

        string state = t; 
        int step = dist[state]; 

        if (state == end) { 
            ex_num = open.size(); 
            out_num = closed.size(); 
            min_step = step; 
            break; 
        }  

        int x, y; 
        for (int i = 0; i < state.size(); i++) {
            if (state[i] == 'x') { 
                x = i / 4, y = i % 4; // x,y 存横纵坐标 
                break; 
            }
        }

        string source = state; // 原状态 
        for (int i = 0; i < 4; i++) { // 每个状态最多可扩展上下左右 4 个状态 
            int a = x + dx[i], b = y + dy[i]; 
            if (a >= 0 && a < 4 && b >= 0 && b < 4) { 
                // (x,y)和(a,b)交换位置(在一维数组中) 
                swap(state[x * 4 + y], state[a * 4 + b]); 
                // 如果此状态之前没被扩展过就扩展，如果之前被扩展过但距离比较大就优化 
                if (!dist.count(state) || dist[state] > step + 1) { 
                    dist[state] = step + 1; 
                    prev[state] = { source, op[i] }; 
                    open.push({ state }); 
                } 
                swap(state[x * 4 + y], state[a * 4 + b]); 
            } 
        } 
    } 

    string res; 
    while (end != start) { 
        res += prev[end].second; 
        record.push(end); 
        end = prev[end].first; 
    } 
    reverse(res.begin(), res.end()); 
    return res; 
} 

int main() { 
    string start = ""; 
    string c = ""; 
    string seq = ""; 

    string s0 = ""; 
    puts("请输入初始状态"); 
    while (1) {  
        cin >> c; // 输入时两数之间需要加空格 
        if (c == "10") c = 'a'; 
        else if (c == "11") c = 'b'; 
        else if (c == "12") c = 'c'; 
        else if (c == "13") c = 'd'; 
        else if (c == "14") c = 'e'; 
        else if (c == "15") c = 'f'; 
        else c = c; 
        start += c; 
        if (c != "x") seq += c; 
        char s = getchar(); 
        if (s == '\n') break; 
    } 
    s0 = start; 
    int t = 0; 
    for (int i = 0; i < seq.size(); i++) {
        for (int j = i + 1; j < seq.size(); j++) {
            if (seq[i] > seq[j]) {
                t++; 
            }
        }
    }

    if (t & 1) puts("无法从初始状态走到最终状态"); 
    else { 
        clock_t begin_time, finish_time; 
        begin_time = clock(); 
        cout << "最优解的操作为：" << bfs(start) << endl; 
        finish_time = clock(); 
        cout << "其中最优解的操作是对空格'x'的操作：u 表示上,d 表示下,l 表示左,r 表示右" << endl; 
        puts(""); 
        cout << "最小步数为" << min_step << endl; 
        puts(""); 
        cout << "扩展节点数：" << ex_num << endl; 
        cout << "生成节点数：" << out_num << endl; 
        puts(""); 
        cout << "状态运行过程展示：" << endl; 
        puts(""); 
        cout << "初始状态为：" << endl; 
        for (int k = 0; k < 16; k++) { 
            if (s0[k] == 'a') cout << " 10"; 
            else if (s0[k] == 'b') cout << " 11"; 
            else if (s0[k] == 'c') cout << " 12"; 
            else if (s0[k] == 'd') cout << " 13"; 
            else if (s0[k] == 'e') cout << " 14"; 
            else if (s0[k] == 'f') cout << " 15"; 
            else if (s0[k] == 'x') cout << " x"; 
            else cout << " " << s0[k] - '0'; 
            if ((k + 1) % 4 == 0) cout << endl;  
        } 
        puts(""); 
        for (int i = 0; i < min_step; i++) { 
            cout << "第" << i + 1 << "步的迷宫状态为：" << endl;; 
            string s = record.top(); 
            record.pop(); 
            for (int k = 0; k < 16; k++) { 
                if (s[k] == 'a') cout << " 10"; 
                else if (s[k] == 'b') cout << " 11"; 
                else if (s[k] == 'c') cout << " 12"; 
                else if (s[k] == 'd') cout << " 13"; 
                else if (s[k] == 'e') cout << " 14"; 
                else if (s[k] == 'f') cout << " 15"; 
                else if (s[k] == 'x') cout << " x"; 
                else cout << " " << s[k] - '0'; 
                if ((k + 1) % 4 == 0) cout << endl; 
            } 
            puts(""); 
        } 
        cout << "运行时间为：" << finish_time - begin_time << "毫秒" << endl; 
    } 
    return 0; 
} 

(4) A* 算法求十五数码的源代码

#include <cstring> 
#include <iostream> 
#include <algorithm> 
#include <queue> 
#include <unordered_map> 
#include <time.h> 
#include <string.h> 
#include <stack> 

using namespace std; 

int ex_num; 
int out_num; 
int min_step; 
bool flag = true; 
stack<string> record; 

int f(string state) { // 估价函数 2：当前状态不在最终状态的数字总数 
    if (flag) { 
        puts(""); 
        puts("估价函数 2 的运行结果："); 
    } 
    flag = false; 
    int res = 0; 
    string end = "123456789abcdefx"; 
    for (int i = 0; i < state.size();i++ ) {
        if (state[i] != end[i]) {
            res++; 
        }
    }
    return res; 
} 

string bfs(string start) { 
    int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 }; 
    char op[4] = { 'u', 'r', 'd', 'l' }; 

    string end = "123456789abcdefx"; 
    unordered_map<string, int> dist; //该状态到起点的步数 
    unordered_map<string, pair<string, char>> prev; //存储一个元素由哪种状态,经过哪种操作得来 

    //小根堆,将元素的估计终点距离从小到大排序 
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> open; 
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> closed; 

    open.push({ f(start), start }); 
    dist[start] = 0; 

    while (open.size()) { 
        auto t = open.top(); 
        closed.push(t); 
        open.pop(); 

        string state = t.second; 
        int step = dist[state]; 

        if (state == end) { 
            ex_num = open.size(); 
            out_num = closed.size(); 
            min_step = step; 
            break;  
        } 

        int x, y; 
        for (int i = 0; i < state.size(); i++) {
            if (state[i] == 'x') { 
                x = i / 4, y = i % 4; // x,y 存横纵坐标 
                break; 
            }
        }
        string source = state; // 原状态 
        for (int i = 0; i < 4; i++) { // 每个状态最多可扩展上下左右 4 个状态 
            int a = x + dx[i], b = y + dy[i]; 
            if (a >= 0 && a < 4 && b >= 0 && b < 4) { 
                swap(state[x * 4 + y], state[a * 4 + b]); // (x,y)和(a,b)交换位置(在一维数组中) 
                // 如果此状态之前没被扩展过就扩展，如果之前被扩展过但距离比较大就优化 
                if (!dist.count(state) || dist[state] > step + 1) { 
                    dist[state] = step + 1; 
                    prev[state] = { source, op[i] }; 
                    open.push({ dist[state] + f(state), state }); // 估价值为f(state)+dist[state] 
                } 
                swap(state[x * 4 + y], state[a * 4 + b]); 
            } 
        } 
    } 

    string res; 
    while (end != start) { 
        res += prev[end].second; 
        record.push(end); 
        end = prev[end].first; 
    } 
    reverse(res.begin(), res.end()); 
    return res; 
} 

int main() { 
    string start = ""; 
    string c = ""; 
    string seq = ""; 

    string s0 = "";  
    puts("请输入初始状态"); 
    while (1) { 
        cin >> c; // 输入时两数之间需要加空格 
        if (c == "10") c = 'a'; 
        else if (c == "11") c = 'b'; 
        else if (c == "12") c = 'c'; 
        else if (c == "13") c = 'd'; 
        else if (c == "14") c = 'e'; 
        else if (c == "15") c = 'f'; 
        else c = c; 
        start += c; 
        if (c != "x") seq += c; 
        char s = getchar(); 
        if (s == '\n') break; 
    } 
    s0 = start; 
    int t = 0; 
    for (int i = 0; i < seq.size(); i++) {
        for (int j = i + 1; j < seq.size(); j++) {
            if (seq[i] > seq[j]) {
                t++; 
            }
        }
    }

    if (t & 1) puts("无法从初始状态走到最终状态"); 
    else { 
        clock_t begin_time, finish_time; 
        begin_time = clock(); 
        cout << "最优解的操作为：" << bfs(start) << endl; 
        finish_time = clock(); 
        cout << "其中最优解的操作是对空格'x'的操作：u 表示上,d 表示下,l 表示左,r 表示右" << endl; 
        puts(""); 
        cout << "最小步数为" << min_step << endl; 
        puts(""); 
        cout << "扩展节点数：" << ex_num << endl; 
        cout << "生成节点数：" << out_num << endl; 
        puts(""); 
        cout << "状态运行过程展示：" << endl; 
        puts(""); 
        cout << "初始状态为：" << endl; 
        for (int k = 0; k < 16; k++) { 
            if (s0[k] == 'a') cout << " 10"; 
            else if (s0[k] == 'b') cout << " 11"; 
            else if (s0[k] == 'c') cout << " 12"; 
            else if (s0[k] == 'd') cout << " 13"; 
            else if (s0[k] == 'e') cout << " 14"; 
            else if (s0[k] == 'f') cout << " 15";  
            else if (s0[k] == 'x') cout <<" x"; 
            else cout <<" "<< s0[k] - '0'; 
            if ((k + 1) % 4 == 0) cout << endl; 
        } 
        puts(""); 
        for (int i = 0; i < min_step; i++) { 
            cout << "第" << i + 1 << "步的迷宫状态为：" << endl;; 
            string s = record.top(); 
            record.pop(); 
            for (int k = 0; k < 16; k++) { 
                if (s[k] == 'a') cout << " 10"; 
                else if (s[k] == 'b') cout << " 11"; 
                else if (s[k] == 'c') cout << " 12"; 
                else if (s[k] == 'd') cout << " 13"; 
                else if (s[k] == 'e') cout << " 14"; 
                else if (s[k] == 'f') cout << " 15"; 
                else if (s[k] == 'x') cout << " x"; 
                else cout <<" "<< s[k] - '0'; 
                if ((k + 1) % 4 == 0) cout << endl; 
            } 
            puts(""); 
        } 
        cout << "运行时间为：" << finish_time - begin_time << "毫秒" << endl; 
    } 
    return 0; 
} 

估价函数 1 运行结果：

估价函数 2 运行结果：