用C++实现旅行售货员问题的回溯算法和分支限界算法

旅行售货员问题（Traveling Salesman Problem，TSP）是一个经典的组合优化问题，其目标是在给定的一组城市和每对城市之间的距离下，找到一条经过每个城市恰好一次且最短的路线。

回溯算法：

回溯算法是一种暴力搜索算法，它通过枚举所有可能的路线来求解问题。在TSP问题中，我们可以从任意一个城市作为起点开始，依次尝试每个城市作为下一个访问的城市，直到所有城市都被访问过，然后返回起点。在尝试每个城市时，我们需要考虑已经访问过的城市，避免出现重复访问的情况。

下面是用C++实现TSP问题的回溯算法的示例代码：

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

const int INF = 1e9;

int n; // 城市数量
int start; // 起点城市
vector<vector<int>> dist; // 城市之间的距离矩阵
vector<int> path; // 当前路径
vector<bool> visited; // 记录每个城市是否已经访问过
int ans = INF; // 最短路线长度

void backtrack(int cur, int cost) {
    if (path.size() == n) { // 所有城市都已访问过，更新最短路线长度
        ans = min(ans, cost + dist[cur][start]);
        return;
    }
    for (int i = 0; i < n; i++) { // 枚举下一个访问的城市
        if (!visited[i]) { // 如果城市未访问过
            visited[i] = true;
            path.push_back(i);
            backtrack(i, cost + dist[cur][i]); // 继续访问下一个城市
            path.pop_back();
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> start;
    dist.resize(n, vector<int>(n));
    visited.resize(n, false);
    path.push_back(start);
    visited[start] = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }
    backtrack(start, 0);
    cout << ans << endl;
    return 0;
}

分支限界算法：

分支限界算法是一种剪枝搜索算法，它通过对搜索树的节点进行剪枝，来减少搜索的时间和空间复杂度。在TSP问题中，我们可以通过估算当前路径的下界来剪枝，避免搜索无效的路径。

下面是用C++实现TSP问题的分支限界算法的示例代码：

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

const int INF = 1e9;

int n; // 城市数量
int start; // 起点城市
vector<vector<int>> dist; // 城市之间的距离矩阵
vector<int> path; // 当前路径
vector<bool> visited; // 记录每个城市是否已经访问过
int ans = INF; // 最短路线长度

struct Node {
    int city; // 当前访问的城市
    int cost; // 当前路径的长度
    int lb; // 当前路径的下界
    vector<bool> visited; // 记录每个城市是否已经访问过
    vector<int> path; // 当前路径
    bool operator < (const Node& other) const { // 优先队列按照下界从小到大排序
        return lb > other.lb;
    }
};

int get_lb() { // 获取当前路径的下界
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) { // 如果城市未访问过
            int min_dist = INF;
            for (int j = 0; j < n; j++) {
                if (visited[j]) { // 如果城市已经访问过
                    min_dist = min(min_dist, dist[j][i]);
                }
            }
            sum += min_dist;
        }
    }
    return sum;
}

void branch_and_bound() {
    priority_queue<Node> pq;
    pq.push({start, 0, get_lb(), visited, path});
    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        int cur_city = cur.city;
        int cur_cost = cur.cost;
        int cur_lb = cur.lb;
        vector<bool> cur_visited = cur.visited;
        vector<int> cur_path = cur.path;
        if (cur_path.size() == n) { // 所有城市都已访问过，更新最短路线长度
            ans = min(ans, cur_cost + dist[cur_city][start]);
            continue;
        }
        for (int i = 0; i < n; i++) { // 枚举下一个访问的城市
            if (!cur_visited[i]) { // 如果城市未访问过
                vector<bool> next_visited = cur_visited;
                next_visited[i] = true;
                vector<int> next_path = cur_path;
                next_path.push_back(i);
                int next_cost = cur_cost + dist[cur_city][i];
                int next_lb = next_cost + get_lb();
                if (next_lb < ans) { // 如果当前路径的下界小于最短路线长度，继续搜索
                    pq.push({i, next_cost, next_lb, next_visited, next_path});
                }
            }
        }
    }
}

int main() {
    cin >> n >> start;
    dist.resize(n, vector<int>(n));
    visited.resize(n, false);
    path.push_back(start);
    visited[start] = true;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }
    branch_and_bound();
    cout << ans << endl;
    return 0;
}