算法设计技巧五：回溯算法（backTracing）
回溯算法相当于穷举搜索的巧妙实现，即排除一定条件的穷举情况，从而不必完全穷举。相对于蛮力穷举，回溯算法能显著减轻工作量。在许多情况下，回溯算法的性能不是很理想。但性能是相对的：对于排序算法，的算法相当糟糕，但对于旅行商（或任意NP完全）问题，算法则是里程碑式的突破。
公路收费点重建问题行为描述：
设给定个点,他们位于上，是的坐标，并设 = 0，这些点从左到右递增排列。公路收费点重建问题要求根据对距离重建并确定的位置。
公路收费点重建问题图形描述：
设距离集合为:distSet = {1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10},共15对距离，则N= 6；
1) 初始条件：x_1 = 0, 选取最大距离dmax = 10,放置在x[N]处；
2）选取次最大值8，则x_5 = 8 或者x_2 = 2, 二者互补对称，插入坐标轴判断剩余距离是否满足；此时有（1,5）= 8，（5,6）= 2；
3）选取次最大值7，插入坐标轴判断剩余距离是否满足；此时有x_4 = 7 或者 x_2 = 3;如果x_4=7，则(6,4) = 3, (5,4) = 1如果置x_2=3,则(2,1) = 3且(5, 2) = 5;分别考虑两种情况：
1、x_4 = 7 时的情况，剩余点对最大值为6，此时有x_3 = 6 或者x_2 = 4，当x_3 = 6时，（6,7） = 1， 而（7,8） = 1，所 以不满足；若x_2 = 4，（2， 0） = 4， （2， 5） = 4不满足；
2、x_2 = 3时的情况,(2,1) = 3, (2, 5) = 5，剩余点对最大值为6，x_4 = 6或者x_3 = 4，当x_3 = 4时，（1，3）= 4，（3, 5）= 4 不满足；当x_4 = 6时，为可能情况；
4）通过3）分析可知，可能的位置为x_2 = 3, x_4 = 6,接下来需要确定的只剩下x_5 = 5,带入验证可知此时刚好填满坐标轴且满足距离点集；
整个过程的决策树结构如图所示：
公路收费点重建问题编程实现：
//main.cpp #include<iostream> #include<vector> #include<cmath> #include<set> using namespace std; const int N = 6; bool place(vector<int> &x, multiset<int> distSet, int N, int left, int right){ int dmax; bool found = false; //when all distSet elements have been checked, return if(distSet.empty()){ return true; } //copy of distSet multiset<int> dSet = distSet; dmax = *distSet.rbegin(); //place dmax to x[right] x[right] = dmax; bool flag = true; //find the difference in left part for(int i = 1; i < left; i++){ if(dSet.find(abs(dmax - x[i])) == dSet.end()){ flag = false; break; } //take off the distance from left part(right part complement) dSet.erase(dSet.find(abs(x[i] - x[right]))); } //find the difference in right part for(int i = right + 1; i <= N; i++){ if(dSet.find(abs(dmax - x[i])) == dSet.end()){ flag = false; break; } //take off the distance from right part dSet.erase(dSet.find(abs(x[i] - x[right]))); } //iterative recall place method when flag = true if(flag){ distSet = dSet; found = place(x, distSet, N, left, right - 1); //if not, reinsert the distance into distSet [backTracing] if(!found){ for(int i = 1; i < left; i++){ distSet.insert(abs(x[i] - x[right])); } for(int i = right + 1; i <= N; i++){ distSet.insert(abs(x[i] - x[right])); } } } flag = true; dSet = distSet; //if not found suitable place in right, try the left if(!found){ x[left] = x[N] - dmax; for(int i = 1; i < left; i++){ if(dSet.find(abs(x[i] - x[left])) == dSet.end()){ flag = false; break; } dSet.erase(dSet.find(abs(x[i] - x[left]))); } for(int i = right + 1; i <= N; i++){ if(dSet.find(abs(x[i] - x[left])) == dSet.end()){ flag = false; break; } dSet.erase(dSet.find(abs(x[i] - x[left]))); } //iterative recall place method when flag = true if(flag){ distSet = dSet; found = place(x, distSet, N, left + 1, right); //if not, reinsert the distance into distSet [backTracing] if(!found){ for(int i = 1; i < left; i++){ distSet.insert(abs(x[N] - dmax - x[i])); } for(int i = right + 1; i <= N; i++){ distSet.insert(abs(x[N] - dmax - x[i])); } } } } return found; } int main(){ vector<int> x(N + 1); multiset<int> distSet; int dist[] = {1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10}; int len = sizeof(dist) / sizeof(dist[0]); for(int i = 0; i < len; i++){ distSet.insert(dist[i]); } //x_1 = 0 x[1] = 0; //x_n = max, rebegin() reverse iterator x[N] = *distSet.rbegin(); //take out the max distance distSet.erase(*distSet.rbegin()); //traceBacking algorithm bool found = place(x, distSet, N, 2, N - 1); vector<int>::iterator itr; for(itr = x.begin() + 1; itr != x.end(); itr++){ cout << *itr << " . "; } cout << endl; cout << " done." << endl; return 0; }practice makes perfect ！
实验结果：
0 . 3 . 5 . 6 . 8 . 10 . done.
