使用回溯算法解决收费公路重建问题，JavaScript算法设计 _收费公路重建问题

从左到右排列，可设x1=0，di=|xi – xj|，其中i不等于j，di表示每一个点对对应一个距离值，这样n个点一共有k=n(n-1)/2个距离值。需要求解的问题是：已知k个距离值，反求出n个x坐标值（x1可设为0）。
回溯算法：使用回溯算法首先是找出并构建解的状态空间树，在状态空间树上执行DFS，并进行适当的剪枝操作。其中回溯算法一个比较明显的想法是，一个个试，也就是每种情况都需要考虑，基于这个想法，可得到如下使用回溯算法解决收费公路重建问题的步骤：

给定距离集D（不妨设D已排序），求解坐标集P，x1可确定为0，xn可确定为D中的最大值。
接下来确定xn-1，如何确定呢？取出D中未使用的最大值m，将m与P中已知的坐标求解距离d，若D中存在d，则可得到xn-1的值为m。
确定xn-2也是类似的2中的步骤，但是当在确定xn-2的时候，取出的m不符合要求的话，则需要取下一个最大值进行尝试。
如果在确定xi的时候尝试D中的所有未使用值都不符合要求，那么需要回退到上一层，例如，确定xn-2的时候，使用D中的所有未使用值都不行，那么需要回退到xn-1，此时将xn-1的值从P中删除，尝试下一个最大值。

【使用回溯算法解决收费公路重建问题，JavaScript算法设计】下面是使用JavaScript实现的回溯算法解决收费公路重建问题的代码：

// 回溯算法：收费公路重建问题 function setValueState(D, T, dist, state){ for(var i = 0; i < D.length; i++) if(state){ if(D[i] == dist & & !T[i]){ T[i] = state; break; } } else{ if(D[i] == dist & & T[i]){ T[i] = state; break; } } }function isContainInD(D, T, dist){ var result = false; for(var i = 0; i < D.length; i++) if(D[i] == dist & & !T[i]){ result = true; break; } return result; }function PisFull(P){ for(var i = 0; i < P.length; i++) if(P[i] == -1) return false; return true; }function DisEmpty(T){ for(var i = 0; i < T.length; i++){ if(!T[i]) return false; } return true; }function dfs(D, P, T, index){ if(PisFull(P) & & DisEmpty(T)) return true; var dist = 0; var flag = true; for(var k = D.length - 1; k >= 0; k--){ if(T[k] || D[k] >= P[index + 1] || D[k] == dist) continue; dist = D[k]; for(var i = 0; i < P.length; i++){ if(P[i] != -1){ var point = P[i]; var dp = Math.abs(point - dist); if(isContainInD(D, T, dp)){ setValueState(D, T, dp, true); } else{ flag = false; break; } } } if(!flag){ for(var j = i - 1; j >= 0; j--){ if(P[j] != -1){ var point = P[j]; var dp = Math.abs(point - dist); setValueState(D, T, dp, false); } } flag = true; continue; // 剪枝：当前发现不符合马上跳过 }P[index] = dist; var result = dfs(D, P, T, index - 1); // DFSif(!result){ // 回溯处理：继续尝试下一个路径 P[index] = -1; for(var i = 0; i < P.length; i++){ if(P[i] != -1){ var point = P[i]; var dp = Math.abs(point - dist); setValueState(D, T, dp, false); } } } else return true; // 有一个解立即返回 } return false; }function turnpike(D, P){ var T = new Array(D.length); for(var i = 0; i < T.length; i++) T[i] = false; P[0] = 0; P[P.length - 1] = D[D.length - 1]; T[D.length - 1] = true; return dfs(D, P, T, P.length - 2); }// 例子1：自定义距离集 var n = 6; var D = [1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 10]; var P = new Array(6); for(var i = 0; i < P.length; i++) P[i] = -1; var r = turnpike(D, P); function print(r, P){ if(r){ var str = ""; for(var i = 0; i < P.length; i++) str += "[" + i + " " + P[i] + "]"; console.log(str); } else console.log("the problem has no solution."); }print(r, P); console.log(""); function compare(a, b){ if(a > b) return 1; else if(a < b) return -1; else return 0; }// 例子2：根据存在的点集生成距离集 function generate(set, D){ D.length = 0; var k = 0; for(var i = 0; i < set.length; i++){ for(var j = i+1; j < set.length; j++) D[k++] = Math.abs(set[i] - set[j]); } D.sort(compare); console.log("D length: " + D.length); var str = ""; for(var i = 0; i < D.length; i++){ str += D[i] + " "; } console.log(str); }n = 8; var set = [0, 2, 8, 16, 23, 31, 33, 39]; generate(set, D); console.log(""); // 使用正确的距离集进行测试：结果可能和预定的点集不一样，表示一个距离集可能有多个解 var NP = new Array(n); for(var i = 0; i < NP.length; i++) NP[i] = -1; var r = turnpike(D, NP); print(r, NP);