旅行商问题c++优先队列式分支限界法

旅行商问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题，目标是在给定的一组城市中找到一条最短的闭合路径，使得旅行商能够访问每个城市恰好一次并返回起点。优先队列式分支限界法是一种有效的求解TSP的方法。

### 优先队列式分支限界法

优先队列式分支限界法通过构建一棵搜索树来枚举所有可能的路径，并在搜索过程中使用优先队列来选择最有希望的节点进行扩展。优先队列根据每个节点的估计成本进行排序，估计成本通常通过下界（lower bound）来计算。

以下是优先队列式分支限界法的主要步骤：

1. **初始化**：
- 创建一个优先队列，将初始节点（起点）加入队列。
- 初始化一个变量来记录当前的最佳路径和对应的最短距离。

2. **节点扩展**：
- 从优先队列中取出估计成本最低的节点。
- 如果该节点表示一条完整的路径且其总距离小于当前的最佳路径，则更新最佳路径。
- 否则，生成该节点的所有子节点（即未访问的城市），并计算每个子节点的估计成本。

3. **剪枝**：
- 如果某个子节点的估计成本大于或等于当前的最佳路径，则剪枝（即不将该子节点加入优先队列）。

4. **重复**：
- 重复上述步骤，直到优先队列为空。

### C++实现示例

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <cmath>

using namespace std;

struct Node {
    vector<int> path;
    vector<bool> visited;
    double cost;
    double lowerBound;

    bool operator<(const Node& other) const {
        return lowerBound > other.lowerBound;
    }
};

double distanceMatrix[100][100];
int numCities;

double calculateLowerBound(const Node& node) {
    double lowerBound = node.cost;
    vector<bool> visited = node.visited;
    int lastCity = node.path.back();

    for (int i = 0; i < numCities; ++i) {
        if (!visited[i]) {
            double minDist = INT_MAX;
            for (int j = 0; j < numCities; ++j) {
                if (!visited[j] && distanceMatrix[i][j] < minDist) {
                    minDist = distanceMatrix[i][j];
                }
            }
            lowerBound += minDist;
        }
    }

    return lowerBound;
}

void branchAndBound() {
    priority_queue<Node> pq;
    Node initialNode;
    initialNode.path.push_back(0);
    initialNode.visited.assign(numCities, false);
    initialNode.visited[0] = true;
    initialNode.cost = 0;
    initialNode.lowerBound = calculateLowerBound(initialNode);
    pq.push(initialNode);

    double minCost = INT_MAX;
    vector<int> bestPath;

    while (!pq.empty()) {
        Node currentNode = pq.top();
        pq.pop();

        if (currentNode.lowerBound >= minCost) {
            continue;
        }

        if (currentNode.path.size() == numCities) {
            double totalCost = currentNode.cost + distanceMatrix[currentNode.path.back()][0];
            if (totalCost < minCost) {
                minCost = totalCost;
                bestPath = currentNode.path;
            }
            continue;
        }

        for (int i = 0; i < numCities; ++i) {
            if (!currentNode.visited[i]) {
                Node newNode = currentNode;
                newNode.path.push_back(i);
                newNode.visited[i] = true;
                newNode.cost += distanceMatrix[newNode.path[newNode.path.size() - 2]][i];
                newNode.lowerBound = calculateLowerBound(newNode);
                pq.push(newNode);
            }
        }
    }

    cout << "最短路径: ";
    for (int i = 0; i < bestPath.size(); ++i) {
        cout << bestPath[i] << " ";
    }
    cout << "0" << endl;
    cout << "最短距离: " << minCost << endl;
}

int main() {
    cout << "请输入城市数量: ";
    cin >> numCities;

    cout << "请输入距离矩阵:" << endl;
    for (int i = 0; i < numCities; ++i) {
        for (int j = 0; j < numCities; ++j) {
            cin >> distanceMatrix[i][j];
        }
    }

    branchAndBound();

    return 0;
}

###