algorithm - 订单转换

Question

假设我有两个订单 ABCDE 和 EDCBA，我想从一个更改为另一个。但是我一次只能交换两组订单，每组都有相关费用。

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

在其他情况下，如果我想从 ABCD 转到 CDBA，我可以通过成本(AB)*成本(CD)一步将 (AB)(CD) 到 (CD)(BA)。

我想问一下我可以使用什么算法来 (1) 最小化将一个订单转换为另一个订单所需的步骤，以及 (2) 如果我还想最小化成本怎么办？(最小化成本并不一定意味着最小化步骤)

Answer 1

这感觉像是 shortest path problem对我来说，类似于其他“如何从一个状态到另一个状态”，比如15-puzzle .

将其作为最短路径问题求解时，您将问题建模为图形，其中所有有效状态(在您的情况下，字符的所有排列)都是顶点，所有有效转换都是边。正式地:

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
• Bi-directional BFS
• A* search algorithm (如果你有 admissible heuristic )

加权(最小成本):

• Dijkstra's Algorithm
• Bellman-Ford
• A* 搜索算法(如果您可以采用启发式算法)

重要提示:

您不需要在开始之前生成图形，您可以有一个函数 next:V->2^V，给定一些状态 - 从它生成所有可能的转换。然后，您可以将这些算法中的任何一个与此 next() 函数结合使用，并仅(即时)生成求解过程中所需的图形部分。