Dav*_*ias 5 sorting algorithm optimization
首先,这是我们去年在一个项目中必须解决的四个问题之一,我找不到合适的算法,所以我们处理暴力解决方案.
问题:数字位于未排序的列表中,仅支持一种操作.操作定义如下:
给定位置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次移动(未触动的元素单独到达其位置).
如果它是最佳的运动顺序,那么你没有移动相同的元素两次.
这个问题看起来像是近似算法的一个很好的候选者，但这只能给我们一个足够好的答案。既然你想要最佳答案，这就是我改进暴力方法的方法。
我不会盲目地尝试每种排列，而是使用回溯方法来维护找到的最佳解决方案，并修剪超出最佳解决方案成本的任何分支。我还会添加一个换位表，以避免对使用不同移动排列的先前分支达到的状态进行重做搜索。
我还会添加一些启发式方法来探索那些更有可能在任何其他举措之前取得良好结果的举措。例如，优先选择成本较小的动作。我需要先进行实验，然后才能判断哪种启发式方法最有效（如果有的话）。
我还会尝试找到原始数组中最长的数字递增子序列。这将为我们提供一个不需要移动的数字序列，这将大大减少我们需要探索的分支数量。这也大大加快了对几乎已排序的列表的搜索速度。
我希望这些改进能够处理远大于 8 的列表，但在处理大型随机数列表时，我更喜欢近似算法。
根据大众的要求（1 人），这就是我用遗传算法（我最熟悉的元启发式算法）来解决这个问题的方法。
首先，我首先计算最长的递增数字子序列（见上文）。不属于该集合的所有项目都必须移动。我们现在需要知道的是按什么顺序。
用作遗传算法输入的基因组只是一个数组，其中每个元素代表要移动的项目。项目在数组中显示的顺序表示它们必须移动的顺序。适应度函数将是原始问题中描述的成本计算。
我们现在拥有将问题插入标准遗传算法所需的所有元素。剩下的只是调整。很多很多的调整。