我正在阅读Introduction to design and analysis of algorithms中关于置换生成和旅行推销员问题的关系。
这里作者提到如下
我们可以在前面生成的置换中插入n
向右或从右向左事实证明，开始
把n插入12……（n-1）从右向左移动
然后每次{1，的新排列时切换方向。……，n-
需要处理1}这种生成顺序的优点
置换源于它满足最小变化的事实
要求：每个排列都可以从它的
只交换其中的两个元素。
如果这种置换是由最小变化算法生成的，那么
可以根据新巡演的长度
在常数时间而不是线性时间中的前导。
关于上面的问题：如果我们使用最小变化算法，我们如何在恒定时间内计算前件的长度？如果可能，请用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/