algorithm - 按升序对数组进行排序，同时最小化 "cost"

Question

我下学期要参加 comp 2210(数据结构)，我一直在做在线发布的夏季学期的作业。到目前为止，我在做作业时没有遇到任何问题。看看下面的作业 4，看看你是否能给我一个关于如何处理它的提示。请不要提供完整的算法，只是一种方法。谢谢!

“成本排序”是一种算法，其中一系列值必须按升序排列。排序是通过一次一个地交换两个值的位置来执行，直到序列处于正确的顺序。每个交换会产生成本，计算为交换中涉及的两个值的总和。总数排序的成本是交换成本的总和。

For example, suppose the starting sequence were {3, 2, 1}. One possible series of interchanges is

Interchange 1: {3, 1, 2} interchange cost = 0 
Interchange 2: {1, 3, 2} interchange cost = 4 
Interchange 3: {1, 2, 3} interchange cost = 5, 
given a total cost of 9

你要编写一个程序来确定排列特定数字序列的最小成本。

编辑:教授不允许暴力破解。

Answer 1

如果你想给你的教授一个惊喜，你可以使用 Simulated Annealing .话又说回来，如果你做到了，你可能可以跳过几门类(class):)。请注意，该算法只会给出一个大概的答案。

否则:尝试 Backtracking算法，或 Branch and Bound .这些都会找到最佳答案。