按升序排序数组,同时最小化"成本"

Question

我下学期参加comp 2210(数据结构),我一直在网上发布夏季学期的作业.到现在为止,我在完成作业时没有遇到任何问题.看一下下面的作业4,看看你是否可以给我一个如何处理它的提示.请不要提供完整的算法,只是一种方法.谢谢!

"成本排序"是一种算法,其中值序列必须按升序排列.通过一次一个地交换两个值的位置来执行排序,直到序列处于正确的顺序.每个交换产生一个成本,该成本计算为交换中涉及的两个值的总和.该类别的总成本是交换成本的总和.

例如,假设起始序列是{3,2,1}.一系列可能的交换是

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

如果你想让教授大吃一惊,你可以使用模拟退火.然后,如果你管理它,你可以跳过一些课程:).请注意,此算法仅提供近似答案.

否则:尝试回溯算法或分支定界.这些都将找到最佳答案.