旅行售货员问题
template <class Type>
class Traveling {
friend Type TSP(int**, int[], int, Type);
private:
void Backtrack(int i);
int n, *x, *bestx;
Type **a, cc, bestc, NoEdge;
};
template <class Type>
void Traveling<Type>::Backtrack(int i) {
if (i == n) {
if (a[x[n - 1]][x[n]] != NoEdge && a[x[n]][1] != NoEdge && (cc + a[x[n - 1]][x[n]] + a[x[n]][1] < bestc || bestc == NoEdge)) {
for (int j = 1; j <= n; j++) {
bestx[j] = x[j];
}
bestc = cc + a[x[n - 1]][x[n]] + a[x[n]][1];
}
} else {
for (int j = i; j <= n; j++) {
if (a[x[i - 1]][x[j]] != NoEdge && (cc + a[x[i - 1]][x[j]] < bestc || bestc == NoEdge)) {
Swap(x[i], x[j]);
cc += a[x[i - 1]][x[i]];
Backtrack(i + 1);
cc -= a[x[i - 1]][x[i]];
Swap(x[i], x[j]);
}
}
}
}
template <class Type>
Type TSP(int **a, int v[], int n, Type noEdge) {
Traveling<Type> Y;
Y.x = new int[n + 1];
for (int i = 1; i <= n; i++) {
Y.x[i] = i;
}
Y.a = a;
Y.n = n;
Y.bestc = noEdge;
Y.bestx = v;
Y.cc = 0;
Y.NoEdge = noEdge;
Y.Backtrack(2);
delete [] Y.x;
return Y.bestc;
}
最后更新:
2024年1月14日 18:59:58
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42