界限剪枝法的应用及其理解

Question

用界限剪枝法求出从南昌出发，经过10个城市，（仅经历一次），然后回到南昌的最短路程，并输出路径。

Answer 1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 11;
const int inf = 0x3f3f3f3f;

int dist[N][N]; // 存储城市之间的距离矩阵
int ans = inf; // 存储最短路径长度
vector<int> path; // 存储最短路径

void dfs(int cur, int step, vector<int> &vis, int dis)
{
    if (step == 11 && cur == 0) // 已经经过10个城市并回到南昌
    {
        ans = min(ans, dis); // 更新最短路径长度
        path.push_back(0);
        return;
    }
    if (dis + dist[cur][0] + (10 - step + 1) * 50 >= ans) // 界限函数，剪枝
        return;
    for (int i = 1; i < N; i++)
    {
        if (vis[i] || dist[cur][i] == inf) continue; // 访问过或者不连通
        vis[i] = 1;
        path.push_back(i);
        dfs(i, step + 1, vis, dis + dist[cur][i]);
        path.pop_back();
        vis[i] = 0;
    }
}

int main()
{
    // 读入城市之间的距离矩阵
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == j) dist[i][j] = 0;
            else dist[i][j] = inf;
        }
    }
    // 将城市之间的距离存入dist数组
    // ...

    vector<int> vis(N, 0); // 标记数组，标记城市是否已经经过
    vis[0] = 1; // 从南昌出发
    path.push_back(0); // 加入南昌到路径中

    dfs(0, 1, vis, 0); // 深度优先搜索

    // 输出最短路径
    cout << "最短路径长度为：" << ans << endl;
    cout << "最短路径为：";
    for (int i = 0; i < path.size(); i++)
        cout << path[i] << " ";
    cout << endl;

    return 0;
}