回溯法——旅行售货员问题
//回溯法
//旅行售货员问题
class TraveLing
{
private:
int n; // 顶点个数
vector<vector<int>> a; // 图的邻接矩阵
int* x; // 记录当前路径
int* bestx; // 最优解路径
int cc; // 当前费用
int bestc; // 最优解费用
void BackTrack(int i)//排列组合
{
if (i == n)//递归出口
{
if (a[x[n - 1]][x[n]] != INT_MAX &&
a[x[n][x[1]] != INT_MAX &&
(cc + a[x[n - 1]][x[n]] + a[x[n]][x[1]] < bestc))//当前路径比之前路径费用少
{
for (int j = 1; j < n+1; ++j)
{
bestx[j] = x[j];//更新目前最优路径 ，注意bestx和x都是从下标1开始用的，下标0我们实际不用
}
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[i]] != INT_MAX &&
cc + a[x[i - 1]][x[i]] < bestc ||
bestc == INT_MAX)
{
swap(x[i], x[j]);
cc += a[x[i - 1]][x[i]];
BackTrack(i + 1);
cc -= a[x[i - 1]][x[i]];//递归回退就回溯
swap(x[i], x[j]);
}
}
}
}
public:
TraveLing(int sum) :n(sum), cc(0), bestc(INT_MAX)
{
x = new int[n + 1];//多申请一个空间，我们从下标1开始用，下标0实际不用
bestx = new int[n + 1];//多申请一个空间，我们从下标1开始用，下标0实际不用
for (int i = 1; i < n+1 ; i++)
{
x[i] = i;//当前路径初始化为1,2,3...n，注意x的0下标我们实际不用
bestx[i] = 1;//当前最优解路径初始化为11111...
}
a.resize(n + 1);//初始化邻接矩阵，并且每个路径都初始化为最大值，为了逻辑清晰一点，下标0没有实际用
for (int i = 0; i < n + 1; i++)
{
a[i].resize(n + 1);
}
for (int i = 0; i < n + 1; i++)
{
for (int j = 0; j < n + 1; j++)
{
a[i][j] = INT_MAX;
}
}
//输入每两个地点和这两个地点消耗的费用
cout << "please input 'way1' to 'way1' and
'cost'，if way1 < 1 or way2 < 1 or cost < 0
end:\n";
int u = 1;
int v = 1;
int w = 0;
while (u >= 1 && v >= 1 && w >= 0)
{
cin >> u >> v >> w;
a[u][v] = w;
a[v][u] = w;
}
BackTrack(2);//传入2 是因为我们从起点1出发，只需要对地点2开始到n这些地点进行排列组合
}
~TraveLing()
{
delete[] x;
delete[] bestx;
}
void PrintBestx()//打印最优解路径
{
for (int i = 1; i < n+1; i++)
{
cout << bestx[i] << " ";
}
cout << "1";//路径结束后肯定回到起点1
cout << endl;
}
int GetBestc()//获取最优解路径下的费用
{
return bestc;
}
};
int main()
{
TraveLing tra(4);
tra.PrintBestx();
cout << tra.GetBestc() << endl;
return 0;
}