路由.cpp

是D算法的一个很好的例子

template 
T AdjacencyWDigraph::BBTSP(int v[]) 
{// 旅行商问题的最小耗费分枝定界算法 
// 定义一个最多可容纳1 0 0 0个活节点的最小堆 
MinHeap > H(1000); 
T *MinOut = new T [n+1]; 
// 计算MinOut = 离开顶点i的最小耗费边的耗费 
T MinSum = 0; // 离开顶点i的最小耗费边的数目 
for (int i = 1; i <= n; i++) { 
T Min = NoEdge; 
for (int j = 1; j <= n; j++) 
if (a[j] != NoEdge && 
(a[j] < Min || Min == NoEdge)) 
Min = a[j]; 
if (Min == NoEdge) return NoEdge; // 此路不通 
MinOut = Min; 
MinSum += Min; 
} 
// 把E-节点初始化为树根 
MinHeapNode E; 
E.x = new int [n]; 
for (i = 0; i < n; i++) 
E.x = i + 1; 
E.s = 0; // 局部旅行路径为x [ 1 : 0 ] 
E.cc = 0; // 其耗费为0 
E.rcost = MinSum; 
T bestc = NoEdge; // 目前没有找到旅行路径 
// 搜索排列树 
while (E.s < n - 1) {// 不是叶子 
if (E.s == n - 2) {// 叶子的父节点 
// 通过添加两条边来完成旅行 
// 检查新的旅行路径是不是更好 
if (a[E.x[n-2]][E.x[n-1]] != NoEdge && a[E.x[n-1]][1] != NoEdge && (E.cc + 
a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1] < bestc || bestc == NoEdge)) { 
// 找到更优的旅行路径 
bestc = E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1]; 
E.cc = bestc; 
E.lcost = bestc; 
E . s + + ; 
H . I n s e r t ( E ) ; } 
else delete [] E.x;} 
else {// 产生孩子 
for (int i = E.s + 1; i < n; i++) 
if (a[E.x[E.s]][E.x] != NoEdge) { 
// 可行的孩子, 限定了路径的耗费 
T cc = E.cc + a[E.x[E.s]][E.x]; 
T rcost = E.rcost - MinOut[E.x[E.s]]; 
T b = cc + rcost; //下限 
if (b < bestc || bestc == NoEdge) { 
// 子树可能有更好的叶子 
// 把根保存到最大堆中 
MinHeapNode N; 
N.x = new int [n]; 
for (int j = 0; j < n; j++) 
N.x[j] = E.x[j]; 
N.x[E.s+1] = E.x; 
N.x = E.x[E.s+1]; 
N.cc = cc; 
N.s = E.s + 1; 
N.lcost = b; 
N.rcost = rcost; 
H . I n s e r t ( N ) ; } 
} // 结束可行的孩子 
delete [] E.x;} // 对本节点的处理结束 
try {H.DeleteMin(E);} // 取下一个E-节点 
catch (OutOfBounds) {break;} // 没有未处理的节点 
} 
if (bestc == NoEdge) return NoEdge; // 没有旅行路径 
// 将最优路径复制到v[1:n] 中 
for (i = 0; i < n; i++) 
v[i+1] = E.x; 
while (true) {//释放最小堆中的所有节点 
delete [] E.x; 
try {H.DeleteMin(E);} 
catch (OutOfBounds) {break;} 
} 
return bestc; 
}