旅行者售货员问题回溯法

旅行者售货员问题回溯法"/>

旅行者售货员问题回溯法

不赘述题目了。思路是回溯法，具体如下：
假设城市=4，出发地=1城市，那么所有可能如下：
1->2->3->4->1
1->2->4->3->1
1->3->2->4->1
1->3->4->2->1
1->4->3->2->1
1->4->2->3->1
可见，本质是对中间三个城市全排列。剪枝方案如下：
先初始化一个最低成本。回溯时计算每一步的成本，如果当前成本比最低成本高，则剪枝。否则，更新最低成本，保存当前路线。

代码如下：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <assert.h>
#include <vector>
#include <iomanip>
using namespace std;
//旅行者售货员问题
class Question
{
public:Question(){cout << "请输入城市数量:";cin >> number;assert(number > 1);weight.resize(number+1);for (size_t i = 0; i < weight.size(); ++i)weight[i].resize(number+1, 0);cout << "请输入各边长" << endl;int from, to, height;for (int i = 0; i < (number*number-number)/2; ++i)//完全图的边个数{//格式：从那个城市到哪个城市成本多少，例如：1 2 10cin >> from >> to >> height;weight[from][to] = height;weight[to][from] = height;}result = INT_MAX;lines = new int[number+1]();}~Question(){delete[] lines;}void display()//打印信息{cout << "********成本/权重***********" << endl;for (int i = 1; i <= number; ++i){for (int j = 1; j <= number; ++j){cout << setw(3) << weight[i][j] << " ";}cout << endl;}cout << "min cost = " << result << endl;for (int i = 0; i < number; ++i)cout << lines[i] << " -> ";cout << lines[number] << endl;}void resolve(){cout << "请输出出发地：";int startCity = 0;cin >> startCity;//创建旅游顺序数组，0和最后一个下标放出发地。//比如city=4，start=2，数组=[2,1,3,4,2]。要全排列中间三个城市int *middleCity = new int[number+1]();for (int i = 0; i < number; ++i)middleCity[i] = i+1;for (int i = 0; i < number; ++i){if (middleCity[i] == startCity){swap(middleCity[i], middleCity[0]);break;}}middleCity[number] = startCity;look_back(middleCity, 1, number-1, 0);//回溯delete[] middleCity;}
private:vector<vector<int>> weight;//权重矩阵，0下标占位不用int number;//城市数量int result;//最低成本int *lines;//最佳路线void look_back(int middleCity[], int start, int end, int currentResult)//回溯{if (currentResult >= result)//剪枝return;if (start > end)//找到一个当前最佳方案，保存结果{result = currentResult;memmove(lines, middleCity, 4*(number+1));return;}for (int i = start; i <= end; ++i)//全排列number-1个城市{//深入一步swap(middleCity[start], middleCity[i]);int tmp = weight[middleCity[start-1]][middleCity[start]];currentResult += tmp;look_back(middleCity, start+1, end, currentResult);//撤回一步currentResult -= tmp;swap(middleCity[start], middleCity[i]);}}
};
int main()
{Question quest;quest.resolve();quest.display();return 0;
}

结果如下：