Problem: Determine an optimal tour in a weighted, directed graph. The weights are nonnegative numbers.
Inputs: a weighted, directed graph, and n, the number of vertices in the graph. The graph is represented by a two-dimensional array W, which has both its rows and columns indexed from 1 to n, where W [i] [j] is the weight on the edge from ith vertex to the jth vertex.
Outputs: a variable minlength, whose value is the length of an optimal tour, and a two-dimensional array P from which an optimal tour can be constructed. P has its rows indexed from 1 to n and its columns indexed by all subsets of V − {v1}. P [i] [A] is the index of the first vertex after vi on a shortest path from vi to v1 that passes through all the vertices in A exactly once.
void travel (int n,
const number W [] [],
index P [] [],
number & minlength)
{
index i, j, k;
number D [1 .. n] [subset of V - {v1}];
for (i = 2; i <= n; i++)
D [i] [⊘] = W[i] [1];
for (k = 1; k <= n - 2; k++)
for (all subsets A ⊆ V - {v1} containing k vertices)
for (i such that i ≠ 1 and vi is not in A){
D [i] [A] = minimum (W [i] [j] + D [j [A - {vj}]);
j: [vj ∊ A
P[i] [A] = value of j that gave the minimum;
}
D [1] [V - {v1}] = minimum (W[1] [j] + D[j] [V - {v1, vj}]);
2 ≤ j ≤ n
P[1] [V - {v1}] = value of j that gave the minimum;
minlength = D[1] [V - {v1
}
}
فروشنده دوره گرد
قوانین ایجاد تاپیک در تالار
پاسخ با نقل قول