首先，去年我们在一个项目中需要解决四个问题之一，但我找不到合适的算法，所以我们采用了暴力解决方案。
问题：这些数字在一个未排序的列表中，只支持一种操作。该操作定义如下：
给定位置i和位置j，操作将在位置i处的数字移动到位置j，而不改变其他数字的相对顺序。如果i>j，则介于位置j和i-1之间的数字的位置增加1；否则，如果i<j，则介于位置i+1和j之间的数字的位置减少1。此操作需要i步来查找要移动的数字，并需要j步来定位要移动到的位置。然后，将数字从位置i移动到位置j所需的步骤数为i+j。
我们需要设计一个算法，给定一组数字，确定重新排列序列的最佳（成本最低）移动序列。
尝试：我们的研究涉及NP完全性，将其作为决策问题，并尝试找到适当的转换来解决Garey和Johnson的书中列出的任何问题，但没有结果。 Donald E. Knuth的书：计算机程序设计艺术卷3排序和搜索中也没有直接参考（从我们的角度来看）这种变化。我们还分析了用于排序链表的算法，但它们中没有一个能够提供找到最佳移动序列的好方法。
请注意，我们的想法不是要找到对序列进行排序的算法，而是告诉我在成本方面最优的移动序列，以组织该序列。如果您愿意，可以复制并将其排序以分析元素的最终位置。实际上，我们可以假设列表包含从1到n的数字，因此我们知道要放置每个数字的位置，我们只关心最小化步骤的总成本。
我们尝试了几种贪心算法，但它们都失败了，分治排序算法不能使用，因为它们会无成本地交换列表的部分，而我们的动态编程方法必须考虑许多情况。
暴力递归算法采用所有可能的i到j的移动组合，然后再考虑其余元素的所有可能移动，最后返回按总成本排序的序列。正如您所想象的那样，这个算法的成本是巨大的，对于超过8个元素就不可行了。
我们的观察：
n个元素的移动不一定比n+1个元素的移动更便宜（与数组中的交换不同，数组中的交换是O(1)）。
基本上有两种方法将一个元素从位置i移动到位置j：一种是直接移动它，另一种是以某种方式移动i周围的其他元素，使其达到位置j。
最多只需进行n-1次移动（未触及的元素单独到达其位置）。
如果这是最优的移动序列，则您没有重复移动同一元素。
insert(remove(i),j)，因此该元素的位置将从i更改到j，其代价为abs(i-j)。 - ruslik