最小編輯距離給出了兩個交換操作

Question

給定兩個字謎S和P，什麼是最小編輯距離選自S爲P時，只有兩種操作：

1. 交換兩個相鄰元件
2. 交換第一和

如果對這一問題被簡化成僅具有所述第一操作的最後一個元素（即，交換兩個相鄰元件），那麼這問題是「類似於」經典算法問題的「的互換的排序號碼的陣列的最小數目」（溶液鏈路在下面給出）

Sorting a sequence by swapping adjacent elements using minimum swaps

我的意思是「相似的」，因爲當兩個字謎都明顯不同的字符：

S: A B C D 
P : B C A D 

然後我們就可以P中定義的排序是這樣

P: B C A D 
    1 2 3 4 

然後根據這個訂購字符串S變成

S: A B C D 
    3 1 2 4 

然後我們可以使用鏈接中給出的解決方案來解決這個問題。

不過，我有兩個問題：

1. 在簡化的問題，我們只能調換相鄰元素，我們怎麼能得到交換的最小數目，如果字謎包含重複的元素。例如，

   S：çd B C d A A

   ，P：A A C d B C d

2. 如何解決兩個交換操作的完整的問題嗎？

Answer 1

一種方法是使用http://en.wikipedia.org/wiki/A * _search_algorithm進行搜索。您的成本函數是從每個元素到最近的元素的最短距離之和的一半，這些元素可能會到達那裏。原因之一在於，絕對理想的掉期組合將在所有時刻將這兩個要素更接近他們想要去的地方。