python - 找到从一种状态到另一种状态的最少函数调用的最快方法

Question

我的问题可以用每种编程语言解决，但我的示例将使用 python，我最希望得到包含 python 代码的答案。

我有一个状态，例如:

state = {"underline":0, "bold":0, "color":0}

而且我有“功能” 他们必须能够将字典“状态”的任何键设置为任何常量整数。函数可能如下所示:

functions = [{"color":0},                          # 0 color black
             {"color":1},                          # 1 color red
             {"color":2},                          # 2 color blue
             {"underline":1},                      # 3 underline
             {"bold":1},                           # 4 bold
             {"underline":0, "bold":0, "color":0}, # 5 reset all
             {"underlined":0, "bold":0}]           # 6 reset styles

我希望能够将函数应用于状态。这可能看起来像这样:

state.update(functions[2])
state.update(functions[4])

我的问题是，我想找到从一种状态到另一种状态所需的最少函数调用。我想要一个函数“get_functions”，它返回我必须在列表中以正确的顺序调用的函数的索引(或字典)，这样我就可以调用尽可能少的函数。

org = {"underline":1, "bold":0, "color":2}
dest = {"underline":0, "bold":1, "color":2}

calls = get_functions(org, dest, functions)

for i in calls:
  org.update(functions[i])

在这种情况下，“get_functions”的输出应该是:

>>> get_functions(org, dest, functions)
[6, 4]

提前致谢!

编辑:

我想用它来格式化带有 ANSI 转义序列的字符串。为了读取带有 ANSI 转义序列的字符串，我有一个状态变量，其中每个格式值都是 0。我逐个字母地检查要格式化的文本，然后将当前状态和当前字母保存在列表中。每次我遇到 ANSI 转义序列时，我都会更改状态。最后我有一个包含字母的列表，每个字母都有自己的状态，包括它的颜色以及是否加粗等等。

现在我用一些函数改变这个列表，让它看起来更漂亮。

为了从列表中生成一个字符串，我遍历列表，每次状态发生变化时，我都会调用“get_functions”，参数为旧状态、新状态和字典。然后我将“get_functions”的输出写入字符串。然后我也将当前字母写入字符串。

Answer 1

您的问题本质上是 to find the shortest route in a directed unweighted graph .执行此操作的算法是 Breadth-first search (“wave method”)或其更快但更复杂的替代方法，“double wave method”(奇怪的是，找不到英文来源，也许那里的称呼不同；你的图表很小，所以你真的不需要它) .

所以，你需要:

1. 构建状态转换图的表示
2. 在您的初始状态和目标状态之间实现搜索

然而，对于您声明的一组转换“将单个属性设置为给定值”，这基本上退化为“将所有属性设置为目标值，一次一个，但尚未达到目标值”。

如果是这种情况，我不明白为什么这甚至值得问一个问题。