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

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. 在我们只能交换两个相邻元素的简化问题中，如果字谜包含重复元素，我们如何获得最小交换次数。例如，

   小号:C 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 用于搜索。您的成本函数是从每个元素到可能到达那里的最近元素的最短距离总和的一半。一半的原因是绝对理想的一组交换将在所有点上使两个元素更接近他们想要去的地方。