分支限界法解TSP问题

#include<iostream>
#include<queue>
#define INF 1e7
#define MAX 100
using namespace std;

int m[MAX][MAX]; //存储城市间的代价
int bestPath[MAX]; //存储最优路径
int bestCost = 1e7; //存储最小代价
int cityNumber; //城市数目

//排列树的节点定义
struct Node {
    int count; //处理的第几个城市
    int currentCost; //记录目前走过的路径代价之和
    int currentPath[MAX]; //在此节点处的走过的路径记录
    Node() {} //默认构造函数，即普通的定义一个结构体的用法
    Node(int count_, int currentCost_) {
        count = count_;
        currentCost = currentCost_;
        memset(currentPath, 0, sizeof(currentPath));
    }
};

//构建最小堆的比较函数
struct pathCost_cmp {
    bool operator()(Node n1, Node n2){
        return n1.currentCost > n2.currentCost;
    }
};

void branchTSP() {
    //定义最小堆, 即待处理节点的PT表
    priority_queue<Node, vector<Node>, pathCost_cmp> q;
    //初始化一个节点，因为默认从城市1开始探索，所以这个初始化节点的编号是2
    Node initNode(2, 0);
    //初始化解向量(路径记录)
    for (int i = 0; i <= cityNumber; i++) {
        initNode.currentPath[i] = i; //顺序走完所有城市
    }
    q.push(initNode);
    Node currentNode; //每次选择的扩展节点
    while (!q.empty()) {
        // 每次选取堆顶元素作为当前的扩展节点
        currentNode = q.top();
        // 已经选择一次，就从PT表（优先队列中移除），因为不会再选择已经选择过的节点作为扩展节点
        q.pop();
        int c = currentNode.count;//用t记录当前节点是处理的第几个城市
        if (c == cityNumber) {//如果排列树已经来到了第cityNumber层,即叶子节点处
            //检查currentNode是否满足约束条件：1. 从上一个点有办法来到当前节点 2. 当前节点有路回到起点 
            if (m[currentNode.currentPath[c - 1]][currentNode.currentPath[c]] != INF
                && m[currentNode.currentPath[c]][1] != INF) {
                if (currentNode.currentCost + m[currentNode.currentPath[c - 1]][currentNode.currentPath[c]]
                    + m[currentNode.currentPath[c]][1] < bestCost) { //如果当前叶子节点的代价更小，做更新
                    bestCost = currentNode.currentCost + m[currentNode.currentPath[c - 1]][currentNode.currentPath[c]]
                        + m[currentNode.currentPath[c]][1];
                    for (int i = 1; i <= cityNumber; i++) {
                        bestPath[i] = currentNode.currentPath[i]; //更新最优路径为当前叶子节点的currentPath
                    }
                }
            }
            //continue; //既然已经到了叶子节点（无法再扩展），那就进入下一层循环
        }
        else {
            if (currentNode.currentCost <= bestCost) { //现在的代价已经大于最小代价了，没必要做任何处理
                                                       // 如果既不是叶子节点，又没有被剪枝，那么会走到这里
            // 从当前节点开始，搜索下一个可能选取的节点，作为要走往的下一个城市
                for (int i = c; i <= cityNumber; i++) {//如果第j个节点满足约束条件也满足限界条件
                    if (m[currentNode.currentPath[c - 1]][currentNode.currentPath[i]] != INF && currentNode.currentCost
                        + m[currentNode.currentPath[c - 1]][currentNode.currentPath[i]] < bestCost) {
                        Node temp = Node(c + 1, currentNode.currentCost
                            + m[currentNode.currentPath[c - 1]][currentNode.currentPath[i]]); //初始化下一个节点
                        for (int j = 1; j <= cityNumber; j++) {
                            temp.currentPath[j] = currentNode.currentPath[j];
                        }
                        swap(temp.currentPath[c], temp.currentPath[i]); //当前位置c要放第i个城市
                        q.push(temp);
                    }
                }
            }
        }
    }
}

int main() {
    cout << "请输入城市数目" << endl;
    cin >> cityNumber;
    //初始化路径数组，所有的路径代价都是INF
    for (int i = 1; i <= cityNumber; i++) {
        for (int j = 1; j <= cityNumber; j++) {
            m[i][j] = INF;
        }
    }
    memset(bestPath, 0, cityNumber); //初始化bestPath数组
    for (int i = 1; i <= cityNumber; i++) {
        cout << "请输入第" << i << "座城市的路径信息(不通请输入-1)" << endl;
        for (int j = 1; j <= cityNumber; j++) {
            int temp;
            cin >> temp;
            if (temp != -1) {
                m[i][j] = temp;
            }
        }
    }
    branchTSP();
    cout << "最优值为：" << bestCost<<endl;
    cout << "最优解为：" << endl;
    for (int i = 1; i <= cityNumber; i++) {
        cout << bestPath[i] << " ";
    }
    cout << bestPath[1] << endl;
    system("pause");
    return 0;
}

/*输入1:
4
-1 30 6 4
30 -1 5 10
6 5 -1 20
4 10 20 -1
*/

/*输入2：
4
-1 3 6 7
12 -1 2 8
8 6 -1 2
3 7 6 -1
*/