排列成本

我給出了集{1,2，...，n}的排列組合。我必須通過以最低總成本交換位於連續職位上的數字來排序此排列。交換位於連續位置的元素x，y的成本是min（x，y）。排列成本

例如，如果我有置換3,1,2,4的總成本最小爲3。因爲我做這些步驟（（X，Y）指其中y交換X）：

總成本爲3。

我試圖蠻力，通過SW應用最低成本未排序對，直到沒有未排序的對，但這種方法顯然不夠快。

我的問題是，如何根據我的條件找到排序的最小成本？

2012-05-11 altair1000

這裏沒有問題。你告訴我們你在做什麼。你想做什麼與你正在做的不同？順便說一句，你的英語+1 ......這是非常好的。 :) –

@JonathanM，這個問題很明顯：什麼是最優化的解決方案？ – Shahbaz

@ user1385303，你可以舉一個例子，說明冒泡排序給出的結果不是最優的嗎？在我看來，如果你貪婪地交換你得到的最低成本（但我需要證明它）。 – Shahbaz

這個算法聽起來像insertion sort。插入排序基於排除排列中的倒置。而你的任務是消除插入排序中的反轉。正如你已經知道排序數組沒有任何反轉。

插入排序算法的時間複雜度爲O（n + d），其中n是元素的數量，d - 是反轉次數。

在排列反轉的最大數量爲n *（N-1）/ 2，最小爲0

您可以使用改性殼聚糖merge sort找到爲O在陣列反轉的數目（n * LG N）。

2012-05-11 15:01:35 Alexander

插入排序允許您一次移動多於1個索引的元素。這只是一個泡沫排序。 http://en.wikipedia.org/wiki/Bubble_sort –

@Jonathan M，這取決於實現。通常我們使用交換來移動。交換次數取決於這個元素i的倒數d（i）。如果您甚至使用鏈接列表，則需要d（i）時間來查找插入位置。 – Alexander

排序順序的順序號交換次數等於按相反順序排列的對數。

例如

6 1 3 2 4 5

雙相反的順序如下：

(6,1) (6,3) (6,2) (6,4) (6,5) (3,2)

所以

的操作順序排序是：

swap(6,1) 1 6 3 2 4 5 
swap(6,3) 1 3 6 2 4 5 
swap(6,2) 1 3 2 6 4 5 
swap(6,4) 1 3 2 4 6 5 
swap(6,5) 1 3 2 4 5 6 
swap(3,2) 1 2 3 4 5 6

所以該操作是確定的（除非你做一些無用的操作）。

您只需要按逆序對所有對（x，y）進行計數，然後將min（x，y）相加即可。

2012-05-11 15:06:30 konjac

是的，這些對被稱爲倒位。而你剛剛展示了插入排序。 – Alexander

是的，我認爲你是對的。謝謝！ – altair1000

並檢查所有對是一個蠻力n方解決方案 – Alexander

回答