回溯法求解TSP问题（C++）

    #include <iostream>
    using namespace std;
    
    void clear(int *flag){ //清空flag表
    for (int i = 0; i < 4; ++i) {
        flag[i] = 0;
    }
    }
    void calculate(int value[4][4]) {
    int length = 0; //记录当前路径长度
    int min = 100; //记录最小路径长度
    int flag[4]; //记录每个城市是否去过
    int num1,num2,num3,num4; //记录选择情况
    int n1,n2,n3,n4; //最终的最短路径。
    for (int i = 0; i < 4; ++i) { //第一个选择，从哪个城市开始
        num1 = i+1; //记录一下路线
        clear(flag); //每一次从头循环都清空记录
        flag[i] = 1;
        cout<<"1选择了第"<<i+1<<"个城市"<<endl;
        for (int j = 0; j < 4; ++j) { //第二个选择
            if (flag[j] == 0) { //如果尚未去过该城市
                num2 = j+1; //记录一下路线
                length = length + value[i][j];
                flag[j] = 1;
                for (int k = 0; k < 4; ++k) { //第三个选择
                    if(flag[k]==0){  //如果尚未去过该城市
                        num3 = k+1; //记录一下路线
                        length = length + value[j][k];
                        flag[k] = 1;
                        for (int l = 0; l < 4; ++l) { //第四个选择
                            if(flag[l]==0){
                                num4 = l+1; //记录一下路线
                                length = length + value[l][i];
                                if(min>length){
                                    min = length;
                                    n1 = num1;
                                    n2 = num2;
                                    n3 = num3;
                                    n4 = num4;
                                }
                                cout<<"一次搜索结束"<<endl;
                                cout<<"路径为："<<num1<<"->"<<num2<<"->"<<num3<<"->"<<num4<<endl;
                                cout<<"距离为："<<length<<endl;
                                cout<<"=================="<<endl;
                                length = 0;
                            }
                        }
                        flag[k] = 0;//消除此次的影响
                    }
                }
                flag[j] = 0;
            }
        }
    }
    cout<<"搜索完毕："<<endl;
    cout<<"路径为："<<n1<<"->"<<n2<<"->"<<n3<<"->"<<n4<<endl;
    cout<<"距离为："<<min<<endl;
    }
    int main() {
    int value[4][4] = {0,3,6,7,5,0,2,3,6,4,0,2,3,7,5,0}; //赋初值
    calculate(value); //计算，开始遍历
    }

    1选择了第1个城市
    一次搜索结束
    路径为：1->2->3->4
    距离为：8
    ==================
    一次搜索结束
    路径为：1->2->4->3
    距离为：9
    ==================
    一次搜索结束
    路径为：1->3->2->4
    距离为：13
    ==================
    一次搜索结束
    路径为：1->3->4->2
    距离为：7
    ==================
    一次搜索结束
    路径为：1->4->2->3
    距离为：20
    ==================
    一次搜索结束
    路径为：1->4->3->2
    距离为：10
    ==================
    1选择了第2个城市
    一次搜索结束
    路径为：2->1->3->4
    距离为：18
    ==================
    一次搜索结束
    路径为：2->1->4->3
    距离为：11
    ==================
    一次搜索结束
    路径为：2->3->1->4
    距离为：15
    ==================
    一次搜索结束
    路径为：2->3->4->1
    距离为：5
    ==================
    一次搜索结束
    路径为：2->4->1->3
    距离为：10
    ==================
    一次搜索结束
    路径为：2->4->3->1
    距离为：8
    ==================
    1选择了第3个城市
    一次搜索结束
    路径为：3->1->2->4
    距离为：14
    ==================
    一次搜索结束
    路径为：3->1->4->2
    距离为：9
    ==================
    一次搜索结束
    路径为：3->2->1->4
    距离为：14
    ==================
    一次搜索结束
    路径为：3->2->4->1
    距离为：9
    ==================
    一次搜索结束
    路径为：3->4->1->2
    距离为：7
    ==================
    一次搜索结束
    路径为：3->4->2->1
    距离为：13
    ==================
    1选择了第4个城市
    一次搜索结束
    路径为：4->1->2->3
    距离为：8
    ==================
    一次搜索结束
    路径为：4->1->3->2
    距离为：9
    ==================
    一次搜索结束
    路径为：4->2->1->3
    距离为：14
    ==================
    一次搜索结束
    路径为：4->2->3->1
    距离为：9
    ==================
    一次搜索结束
    路径为：4->3->1->2
    距离为：14
    ==================
    一次搜索结束
    路径为：4->3->2->1
    距离为：11
    ==================
    搜索完毕：
    路径为：2->3->4->1
    距离为：5