Sort array in ascending order while minimizing "cost"

Question

I'm taking comp 2210 (Data Structures) next semester and I've been doing the homework for the summer semester that is posted online. Until now, I've had no problems doing the assignments. Take a look at assignment 4 below, and see if you can give me a hint as to how to approach it. Please don't provide a complete algorithm, just an approach. Thanks!

A “costed sort” is an algorithm in which a sequence of values must be arranged in ascending order. The sort is carried out by interchanging the position of two values one at a time until the sequence is in the proper order. Each interchange incurs a cost, which is calculated as the sum of the two values involved in the interchange. The total cost of the sort is the sum of the cost of the interchanges.

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

You are to write a program that determines the minimal cost to arrange a specific sequence of numbers.

Edit: The professor does not allow brute forcing.

Answer 1

If you want to surprise your professor, you could use Simulated Annealing. Then again, if you manage that, you can probably skip a few courses :). Note that this algorithm will only give an approximate answer.

Otherwise: try a Backtracking algorithm, or Branch and Bound. These will both find the optimal answer.

Answer 2

What do you mean "brute forcing?" Do you mean "try all possible combinations and select the cheapest?" Just checking.

I think "branch and bound" is what you're looking for - check any source on algorithms. It is "like" brute force, except as you try a sequence of moves, as soon as that sequence of moves is less optimal than any other sequence of moves tried so far, you can abandon the sequence that got you to that point - the cost. This is one flavor of the "backtracking" mentioned above.

My preferred language for doing this would be Prolog but I'm weird.

Simulated Annealing is a PROBABLISTIC algorithm - if the solution space has local minima, then you may be trapped in one and get what you think is the right answer but isn't. There are ways around that and the literature all about that can be found but I don't agree that it's the tool you want.

You could try the related genetic algorithms too if that's the way you want to go.