algorithm - 字谜字符串编辑距离算法/代码？

Question

有两个变位字符串S和P，有两个基本操作:

1. 交换相邻的两个字母，例如交换 BCCAB 中的“A”和“C”，成本为 1。
2. 交换字符串中的第一个字母和最后一个字母，cost为1。

问题:设计一种有效的算法，使将 S 更改为 P 的成本最小化。

我尝试了一个贪心算法，但我发现了反例，我认为它是不正确的。我知道著名的 DP 问题编辑距离，但我没有得到这个问题的公式。

有人可以帮忙吗？一个想法和伪代码会很棒。

Answer 1

我想知道 http://en.wikipedia.org/wiki/A *_search_algorithm 算作有效吗？对于启发式算法，寻找每个字符必须经过的最小距离，将字符串视为一个圆，并将这些距离的总和除以二。在圆圈上，每个角色都需要参与足够多的交换才能将其移动到目的地，一次一步，每次交换只影响两个角色，所以这个启发式应该是所需交换次数的下限。