首先,这是我们去年在一个项目中必须解决的四个问题之一,我找不到合适的算法,所以我们处理暴力解决方案.
问题:数字位于未排序的列表中,仅支持一种操作.操作定义如下:
给定位置i和位置j,操作将位置i处的数字移动到位置j而不改变其他数字的相对顺序.如果i> j,位置j和i-1之间的数字的位置增加1,否则如果i <j,位置i + 1和j之间的数字的位置减1.此操作需要我的步骤来找到要移动的数字和要定位要移动它的位置的j步.然后,将多个位置i移动到位置j所需的步数是i + j.
我们需要设计一种给出数字列表的算法,确定重新排列序列的最佳(按成本计算)移动顺序.
尝试: 我们的部分调查是围绕NP完全性,我们将其作为一个决策问题,并尝试找到适当的转换,以解决Garey和Johnson的书中列出的任何问题:计算机和难以处理,没有结果.在唐纳德·E·克努特(Donald E. Knuth)的着作"计算机编程艺术"中,也没有直接参考(从我们的观点来看)这种变化.3排序和搜索.我们还分析了对链接列表进行排序的算法,但没有一个能够找到最佳的运动序列.
请注意,这个想法不是要找到一个对序列进行排序的算法,而是要告诉我组织序列的成本方面的最佳运动顺序,您可以复制并对其进行排序以分析元素的最终位置如果你愿意,事实上我们可以假设列表包含从1到n的数字,所以我们知道我们想要把每个数字放在哪里,我们只关心最小化步骤的总成本.
我们测试了几种贪婪的方法,但它们都失败了,分而治之的排序算法无法使用,因为它们与列表中没有成本部分交换,我们的动态编程方法必须考虑很多情况.
蛮力递归算法采用从i到j的所有可能的运动组合,然后是元素其余部分的所有可能时刻,最后它返回序列的总体成本较低的序列,如您所能想象的那样这种算法的成本是残酷的,并使其超过8个元素是不切实际的.
观察:
n运动不一定比n + 1运动便宜(与O(1)的数组中的交换不同).
基本上有两种方法可以将一个元素从位置i移动到j:一个是直接移动它,另一个是以其到达位置j的方式移动i周围的其他元素.
最多可以进行n-1次移动(未触动的元素单独到达其位置).
如果它是最佳的运动顺序,那么你没有移动相同的元素两次.
我正在尝试使用C#中的CodeContracts看起来更像语句,所以我需要一个工具,允许我在编译器看到之前替换一些代码,如果没有办法,我猜Visual Studio插件也会有帮助.