algorithm - 将给定字谜转换为另一个字谜所需的最小交换次数

Question

给定两个字谜 S1 和 S2，我们想将 S1 字谜转换为 S2 字谜。我们需要找出为此所需的最小邻接交换次数。

例如：S1:CAT 和 S2:ACT。这里最小交换次数仅为 1。将 C 交换到 A 以获得 S2。

我们如何使用动态编程来做到这一点。可能吗？

Answer 1

获得最优解的一种方法是将问题简化为最短路径问题。

在这里，每个顶点都是使用给定字母的一个可能的字谜。当且仅当您可以通过一次交换从一个顶点移动到另一个顶点时，才存在两个顶点（字谜）之间的边。

找到从输入字谜到所需字谜的最短路径将为您提供最佳路径数。

未加权图的最短路径问题可以用BFS、双向BFS 或A* 算法来解决。