b*******e
发帖数: 217 | 1 Two-Person Traversal of a Sequence of Cities. You are given an ordered
sequence of n cities, and the distances between every pair of cities. You
must partition the cities into two subsequences (not necessarily contiguous)
such that person A visits all cities in the first subsequence (in order),
person B visits all cities in the second subsequence (in order), and such
that the sum of the total distances travelled by A and B is minimized.
Assume that person A and person B start initially at the first city in their
respective subsequences. | t****a
发帖数: 1212 | | b*******e
发帖数: 217 | 3 my recursive function is
Xba(i) = Min { Xab(i-1) + D(i-2, i) ; Xba(i-1) + D(i-1, i);
Xaa(i-1) + D(i-1, i) ; Xab(i-2) + D(i-3, i) + D(i-2, i-1);
Xab(i-3) + D(i-4, i) + D(i-3, i-1),
....
Xab(1) + D(1, i) + D(1, i-1)}
Where ba indicates i-1 th city is visited by b and ith city is visited by a.
aa indicates i-1 th city visited by a and ith city also visited by a.
ab, and bb following the same.
Following same method,
We can have the recursive function for Xaa(i), Xab(i) and Xbb(i).
The final min is Min(Xba(n), Xaa(n), Xbb(n), Xab(n))
【在 t****a 的大作中提到】
: 很有趣的题目。有测试数据和答案吗？
|
|
