序变换

Question

假设我有两个订单ABCDE和EDCBA，我想从一个改变到另一个。但是我一次只能换两组订单，每组都有相关的成本。

因此，在这种情况下，我可以从(A)(BCDE)到(BCDE)(A)到(CDE)(B)(A)到(C)(DE)BA到(DE)(C)(B)(A)，成本将是成本(A)*成本(BCDE)+成本(B)*成本(CDE)+成本(C)*成本(DE)+成本(D)*成本(E)

在另一种情况下，如果我想从ABCD转到CDBA，我可以将(AB)(CD)到(CD)(BA)与成本(AB)*成本(CD)一步到位。

我想问的是，我可以使用哪些算法来(1)最小化将一个订单转换成另一个订单所需的步骤，(2)如果我也希望将成本降到最低呢？(最小化成本并不一定意味着步骤最小化)

Answer 1

对我来说，这就像一个最短路径问题，类似于其他“如何从一种状态获得到另一种状态”，比如15-拼图。

当将其作为最短路径问题求解时，您可以将问题建模为一个图，其中所有有效状态(在您的例子中，所有字符的排列)都是顶点，所有有效的转换都是边。正式：

G = (V,E)
V = { p | p is a permutation of the start/end state }
E = { (u,v) | can transform u to become v in one step }

在加权版本(最小成本)中，也有一个权重函数：w(u,v)，这是进行转换的代价。

在建立了一个图形模型之后，这基本上是从一个源(起始状态)到一个目标(目标)的最短路径。

例如，可以通过以下方法解决这一问题：

未加权(最短距离)：

• BFS
• 双向BFS
• 搜索算法 (如果您可以拥有容许启发式)

加权(最小费用)：

• 迪克斯特拉算法
• 行李员-福特
• 一个*搜索算法(如果你有允许的启发式)

重要提示：

您不需要在开始之前生成图形，您可以有一个函数next:V->2^V，该函数给定某种状态-从它生成所有可能的转换。然后，您可以在这个next()函数中使用这些算法中的任何一个，并且只生成(动态)解决方案期间所需的图的部分。