计算一系列变换的最优阶数

Question

不确定我应该在这里询问还是其他堆栈交换。

基本上，我想知道在给定许多潜在变换的情况下，是否有一种已知的方法可以找到两个值之间的最短路径？

python 中的Brute force解决方案/示例

from itertools import permutations, groupby
start = ["A", "B", "C", "D"]
goal = ["A", "X", "C", "Y"]
Transforms = [
(None,None,"B","D"),
("F",None,None,"Y"),
(None,"X","C",None),
(None,None,"G","Y"),
("D","X",None,None),
(None,"X",None,None)
]
def apply_transform(value, transform):
for x in range(4):
if transform[x] is None: continue
value[x] = transform[x]
perms = permutations(range(len(Transforms)))
results = []
for order in perms:
value = start.copy()
moves = 0
for o in order:
moves += 1
apply_transform(value, Transforms[o])
if value == goal:
results.append([moves, order[0:moves]])
break
# just printing sorted unique in a formated way...I'd be just picking the first one not listing all potential ones
results.sort( key=lambda x: x[0])
results = list(k for k,_ in groupby(results))
print("n".join(f"moves {m} | {' -> '.join(str(s) for s in ms)}" for m,ms in results))

正确地将开始移动到目标的结果。

moves 2 | 3 -> 2
moves 3 | 0 -> 3 -> 2
moves 3 | 3 -> 5 -> 2
moves 3 | 5 -> 3 -> 2
moves 4 | 0 -> 3 -> 5 -> 2
moves 4 | 0 -> 5 -> 3 -> 2
moves 4 | 5 -> 0 -> 3 -> 2

因此，选择排序列表中的第一个项目作为转换次数最少的项目。(应用变换"3"，然后应用变换"2"(。

显然，这种确切的暴力"；算法"；如果排列已经开始变得比最低跳跃次数更长，则可以通过打破排列来改进。。。但对于我看不到的这个问题，有更好的解决方案吗？某种图形？排列并不是速度的最佳选择，但它可能是唯一的选择。有没有其他小的优化可以用它来完成？

Answer 1

一种可能的优化方法是找到必须是最后一个转换的转换，然后逆向工作。

所以，这里只有变换2和5可以是最后一个，5是2的子群，所以它可以被忽略(还有一个优化：忽略作为其他变换一部分的变换(，剩下的只有2。

现在，您将了解如何使用剩余的转换来达到状态(A，*，*，Y(。变换1和3是唯一的候选者，并且3->2构成了解决方案。

这个算法有点复杂，因为它需要递归和回溯(如果你用简单的方法，深度优先(，或者一些队列处理(如果你做得更好，广度优先(，但它会比尝试所有可能的排列更快。

Answer 2

将其视为一个图。每个值都是一个节点，变换是边。图中的最短路径有已知的算法，例如Dijkstra或a*。