给定两个交换操作的两个字谜的最小编辑距离

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: C D B C D D A A、C、D、B、C、D
2. 如何解决两个交换操作的完整问题？

Answer 1

一种方法是使用http://en.wikipedia.org/wiki/A*_search_algorithm进行搜索。您的成本函数是从每个元素到可能到达那里的最近元素的最短距离之和的一半。一半的原因是，绝对理想的掉期组合在任何时候都会使两个要素都更接近它们想要达到的目标。