最小编辑距离给出了两个交换操作

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进行搜索。您的成本函数是从每个元素到最近的元素的最短距离之和的一半，这些元素可能会到达那里。原因之一在于，绝对理想的掉期组合将在所有时刻将这两个要素更接近他们想要去的地方。