CODEWITHSUNDEEP
algorithmpermutationtraveling-salesman
venkysmarty
venkysmarty

Reputation: 11441

Travelling Salesman with minimum change permutation

I am reading about permutation generation and relationship with Travelling Salesman Problem in Introduction to design and analysis of algorithms.

Here author mentioned as below

We can insert n in the previously generated permutations either left to right or right to left. It turns out that it is beneficial to start with inserting n into 12 . . . (n − 1) by moving right to left and then switch direction every time a new permutation of {1, . . . , n − 1} needs to be processed. The advantage of this order of generating permutations stems from the fact that it satisfies the minimal-change requirement: each permutation can be obtained from its immediate predecessor by exchanging just two elements in it.

If such permutations are generated by a minimal-change algorithm, we can compute the length of a new tour from the length of its predecessor in constant rather than linear time.

My question on above text: How can we calculate length form predecessor in constant time if we use minimum change algorithm? If possible, please give a simple example with n=3.

Upvotes: 0

Views: 478

Answers (1)

user555045
user555045

Reputation: 64933

Let's say you swap element b with element e, oddly chosen letters because we suppose b is the middle element of a path a->b->c and e is the middle element of a path d->e->f.

4 edges disappear, they are replaced by 4 new edges. The ones that disappear are the ones that connect b and e to their old neighbours. The new ones are a->e, e->c, d->b and b->f.

So the new total length is

old - d(a, b) - d(b, c) - d(d, e) - d(e, f) + d(a, e) + d(e, c) + d(d, b) + d(b, f)

Upvotes: 1

Related Questions