旅行售货员问题
template <class Type>
class Traveling {
friend void main(void);
public:
Type BBTSP(int v[]);
private:
int n;
Type **a, cc, bestc, NoEdge;
};
template <class Type>
class MinHeapNode {
friend Traveling<Type>;
public:
operator Type() const { return lcost; }
private:
Type lcost, cc, rcost;
int s, *x;
};
template <class Type>
Type Traveling<Type>::BBTSP(int v[]) {
MinHeap<MinHeapNode<Type>> H(1000);
Type *MinOut = new Type[n + 1];
Type MinSum = 0;
for (int i = 1; i <= n; i++) {
Type Min = NoEdge;
for (int j = 1; j <= n; j++) {
if (a[i][j] != NoEdge && (Min == NoEdge || Min > a[i][j]))
Min = a[i][j];
}
if (Min == NoEdge)
return NoEdge;
MinOut[i] = Min;
MinSum += Min;
}
MinHeapNode<Type> E;
E.x = new int[n];
for (int i = 0; i < n; i++)
E.x[i] = i;
E.s = 0;
E.cc = 0;
E.rcost = MinSum;
Type 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 && (bestc == NoEdge || bestc > E.cc + a[E.x[n-2]][E.x[n-1]] + a[E.x[n-1]][1])) {
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.Insert(E);
} else {
delete[] E.x;
}
} else {
for (int i = E.s + 1; i < n; i++) {
if (a[E.x[E.s]][E.x[i]] != NoEdge) {
Type cc = E.cc + a[E.x[E.s]][E.x[i]];
Type rcost = E.rcost - MinOut[E.x[E.s]];
Type b = cc + rcost;
if (bestc == NoEdge || bestc > b) {
MinHeapNode<Type> 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[i];
N.x[i] = E.x[E.s + 1];
N.s = E.s + 1;
N.cc = cc;
N.rcost = rcost;
N.lcost = b;
H.Insert(N);
}
}
}
delete[] E.x;
}
try {
H.DeleteMin(E);
} catch (OutOfBounds) {
break;
}
}
if (bestc == NoEdge)
return NoEdge;
for (int i = 0; i < n; i++)
v[i] = E.x[i];
while (true) {
delete[] E.x;
try {
H.DeleteMin(E);
} catch (OutOfBounds) {
break;
}
}
return bestc;
}
最后更新:
2024年1月14日 20:14:02
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42