【旅行商问题的优化】

#include<bits/stdc++.h> // 包含标准库的头文件

using namespace std; // 使用标准命名空间

template <class Type> // 模板声明，Type为类型参数
class Traveling{ // 定义Traveling类
    friend Type Tsp(int **, int[],int, Type); // 声明友元函数Tsp
public:
    int predict(int j);
    void Backtrack(int i); // 声明Backtrack函数
    int n, *x, *bestx; // 声明成员变量n顶点数目, x存放当前解的结点编号, bestx存放最优解的结点编号
    Type **a, cc, bestc; // 声明成员变量a邻接矩阵, cc当前已经求得的费用, bestc最佳费用
};

template <class Type> // 模板声明，Type为类型参数
Type Tsp(Type **a, int v[], int n); // 声明Tsp函数

int min_edge = INT_MAX;

int main() // 主函数入口
{
    clock_t start = clock();
    int **a,*v, n,bestc; // 声明指针变量和整型变量
    cin>>n; // 输入n的值
    v= new int[n+1]; // 动态分配数组v的内存空间
    a=new int* [n+1]; // 动态分配数组a的内存空间
    for(int i=0;i<=n;i++) // 循环，初始化数组a的每一行
        a[i]=new int [n+1]; // 动态分配数组a的每一行的内存空间
    for(int i=1;i<=n;i++) // 循环，输入每一行的数据
        for(int j=i+1;j<=n;j++){ // 循环，输入每一行的数据
            cin>>a[i][j]; // 输入数据到数组a
            a[j][i]=a[i][j]; // 将对称位置的数据设为相同的值
            if(i == 1 && a[i][j] < min_edge) min_edge = a[i][j]; 
        }
        
    bestc=Tsp(a,v,n); // 调用Tsp函数计算最短路径长度

    cout << bestc << endl; // 输出最短路径长度

    clock_t end = clock();

    float duration = (float)(end - start) / CLOCKS_PER_SEC;
    cout << duration;

    return 0; // 返回0，表示程序正常结束
}

template <class Type>
int Traveling <Type>::predict(int j)
{
    int sum = 0;

    int *sign = new int[n+1];
    memset(sign, 0, sizeof(sign));
    for(int i = 1; i <= j; i++) sign[x[i]] = 1;

    for(int i = j; i <= n; i++)
    {
        int smallest = INT_MAX, small = INT_MAX;
        int vertex = x[i];
        for(int to = 1; to <= n; to++)
        {
            if(sign[to] || to == vertex) continue;
            if(a[vertex][to] < smallest) {
                small = smallest; // 将原来的最小值赋给次小值
                smallest = a[vertex][to]; // 更新最小值
            }
            else if(a[vertex][to] < small) {
                small = a[vertex][to]; // 更新次小值
            }
        }
        if(small != INT_MAX) sum += small, sum += smallest;
        else if(smallest != INT_MAX) sum += smallest*2;
    }

    return sum/2 + min_edge;
}

template <class Type> // 模板声明，Type为类型参数
void Traveling <Type>::Backtrack(int i) // 类Traveling成员函数Backtrack的实现
{
    cout << bestc;
    puts("");
    int temp; // 声明临时变量temp
    if(i==n){ // 如果i等于n
        if(a[x[n-1]][x[n]]!=0 && a[x[n]][x[1]]!=0 && // 如果路径形成一个环
           (cc+a[x[n-1]][x[n]]+a[x[n]][x[1]]<bestc || bestc ==0)){ // 并且路径长度小于最优长度或者最优长度为0
            for(int j=1;j<=n;j++) // 循环，复制当前路径到最优路径
                bestx[j]=x[j]; // 复制当前路径到最优路径
            bestc=cc+a[x[n-1]][x[n]]+a[x[n]][x[1]]; // 更新最优路径长度

        }
    }
    else{ // 否则
        for(int j=i;j<=n;j++) // 循环，尝试不同的下一个城市
            if(a[x[i-1]][x[j]]!=0 && // 如果下一个城市可达
               (cc+a[x[i-1]][x[j]]+predict(j)<bestc || bestc==0)){ // 并且路径长度小于最优长度或者最优长度为0
                temp=x[i]; // 交换城市顺序
                x[i]=x[j]; // 交换城市顺序
                x[j]=temp; // 交换城市顺序
                cc+=a[x[i-1]][x[i]]; // 更新路径长度
                Backtrack(i+1); // 递归调用Backtrack函数
                cc-=a[x[i-1]][x[i]]; // 恢复路径长度
                temp=x[i]; // 交换城市顺序
                x[i]=x[j]; // 交换城市顺序
                x[j]=temp; // 交换城市顺序
            }
    }
}

template <class Type> // 模板声明，Type为类型参数
Type Tsp(Type **a, int v[], int n) // 函数Tsp的实现
{
    Traveling <Type> Y; // 声明Traveling类的实例Y
    Y.x=new int[n+1]; // 动态分配数组Y.x的内存空间
    for(int i=1;i<=n;i++) // 循环，初始化Y.x数组
        Y.x[i]=i; // 初始化Y.x数组
    Y.a=a; // 将参数a赋值给Y.a
    Y.n=n; // 将参数n赋值给Y.n
    Y.bestc=0; // 将Y.bestc初始化为0
    Y.bestx=v; // 将参数v赋值给Y.bestx
    Y.cc=0; // 将Y.cc初始化为0
    Y.Backtrack(2); // 调用Backtrack函数计算最短路径
    
    delete [] Y.x; // 释放Y.x的内存空间
    return Y.bestc; // 返回最短路径长度
}

predict函数采用贪心策略，搜索剩余结点之间（可从x[j]开始，但不到x[j]，因为判断中已经把x[i-1]到x[j]的长度考虑了，不属于未知部分，所以这是约束不是预测）的最短和次短邻接边，然后取平均再分别求和，作为对到剩余结点的预测。也就是说原本的代码不存在限界函数，只有约束函数，我们加入了限界函数，进一步完成了剪枝。(注意加上返回1的最短边)