数据结构与算法分析 ——回溯算法之收费公路重建问题
数据结构与算法分析第十章回溯算法之收费公路重建问题
一、 问题描述：
设给定N个点p1, p2,…,pn,它们位于x-轴上。xi是pi点的x坐标。这N个点确定了N(N-1)/2个点间距离。显然，如果给定点集，那么容易以O(N2)事件构造距离集合。收费公路重建问题是从这些距离重新构造出点集。
二、解题思路：
回溯算法：
对于大多数的回溯算法，最方便的实现方法是使用递归，该算法一直沿某条可能路线执行，直至得到确定结果，如果结果是正确的，则成功返回；否则回溯到该路线的上一步，尝试另外一条可能路线。如此程序要么找到正确路线，返回路线；要么不断回溯，尝试所有路线，发现任何路线均不可行，返回失败。
收费公路重建：
1、若给定该问题的一个解，则可以通过对所有的点加上一个偏移量而构建无穷多其他的解，因此将第一个点置于0处；
2、由于距离集合D中最大值为max，因此max处存在一个点，从D中删除max，现在点集X中有两个点位置已确定，起点x，终点max；
3、取D中的最大值m，则新点横坐标只存在两种可能，位于m处，或者(max-m)处；
4、先假定新点位于m处，则该点与X中已确定点的点距d也确定了，如果d中的每个值均在D中，那么说明该位置可能合适，更新D和X，执行步骤3（如果步骤3返回true,执行结束，否则还原D和X，执行步骤5）；否则执行步骤5；
5、假定新点位于(max-m)处，重新判断点距，如果点距均在D中，更新D和X，执行步骤3（如果步骤3返回true,执行结束，否则还原D和X，返回false）；否则无适合点集满足所需，返回false。
简要总结：
每次取集合D中的最大值，则新点位置只存在两种可能。每假定新点位置，则该点与集合X中其他点的距离便确定了，首先判断这些距离是否位于D中，如果不都在，则新点位置不合适；否则确定新点在此位置，继续向下执行。新点位置在两处均不合适，说明上一个新点位置选取失败，回溯。
三、编程实现：
1、代码（注：传入的参数dList必须已按从小到大排序，得到的点的横坐标未排序）：
public class RebuildRoad {
protected static int maxLen;
public void start(LinkedList<Integer>dList, int[] pArray) {
maxLen =dList.removeLast();
pArray[0] = 0;
pArray[1] = maxLen;
build(dList, pArray, 2);
}
private boolean build(LinkedList<Integer> dList, int[] pArray, int left) {
if (dList.isEmpty()) {//说明已经找到点集，返回
return true;
}
LinkedList<Integer>dCopy = new LinkedList<Integer>();
dCopy.addAll(dList); // 创建dList的副本，便于恢复dList
int max =dList.getLast();
boolean res = false;
res = takeStep(dList,dCopy, pArray, left, max);
if (res)
return true;
int lmax = maxLen - max;// max和lmax总是成对出现的
res = takeStep(dList,dCopy, pArray, left, lmax);
return res;
}
private boolean takeStep(LinkedList<Integer> dList,
LinkedList<Integer>dCopy, int[] pArray, int left, int max) {
int[] dists = newint[left]; // 存放新点与其他个点的距离
boolean find = true;
boolean flag = true;
for (int i = 0; i <left; i++) {
dists[i] =Math.abs(max - pArray[i]);
if(!dList.contains(dists[i])) {
flag =false;
break;
}
}
if (flag) { // 如果新点放置在max处，与其他各点的距离均在dList中
for (int i = 0; i< left; i++) { // 从dList中移除各个距离
if(!dList.remove(new Integer(dists[i]))) {
find= false;
break;
}
}
if (find) {
pArray[left++]= max;
find =build(dList, pArray, left);
if (find)
returntrue;
else //撤销对数组的操作
left--;
}
}
if (flag) { // 执行到这里，说明此路不通，且dList已改变，需要恢复
dList.removeAll(dList);
dList.addAll(dCopy);
}
return false;
}
}
2、结果：