我正在阅读 Introduction to design and analysis of algorithms 中关于排列生成和与旅行商问题的关系的内容.
这里提到的作者如下
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.
我对以上文本的问题:如果我们使用最小变化算法，我们如何在恒定时间内计算前导的长度？如果可能，请用n=3给出一个简单的例子。
最佳答案
假设您将元素 b 与元素 e 交换，奇怪地选择了字母，因为我们假设 b 是路径 a->b->c 的中间元素，而 e 是路径 d->e->f 的中间元素.
4条边消失了，它们被4条新边代替。那些消失的是那些将 b 和 e 连接到他们的老邻居的人。新的是 a->e、e->c、d->b 和 b->f。
所以新的总长度是
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)
关于algorithm - 具有最小找零排列的旅行商，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27855179/