解决关系集的算法

Question

我正在编写一个程序来处理各种方程式。我有一个方程列表，以及一个可以求解给定方程的未知值的函数。

例如：a + b + c = 0 -> 可以求解任何变量，给定其他 2。

我现在需要编写一个算法，该算法采用关系列表、已知值列表和目标，然后找到为找到未知值而必须采取的一系列步骤。

例如：(a = b, b = c) a = 1, 求c:
结果将显示您首先将 a -> b 转换为“a = b”，然后将 b -> c 转换为“b = c”

如果能帮助我研究算法或搜索词，我们将不胜感激

Answer 1

假设我们有：

方程式列表 eqs;
初始变量列表xs；
一个函数 f(eq, xs)，给定方程 eq 和变量名称列表 xs，returns 变量列表 ys，其值如果我们知道 xs;

eq

一个目标变量target.

那么你的问题有点像“最短路径”问题，试图找到从初始变量列表到包含目标变量的列表的路径。

我们可以执行 breadth-first-search，尝试扩展已知变量列表，直到它包含目标。

eqs = '''3 * a + 2 * b + c == 0
a + b = 12
c + 4 * b = 4'''.split('\n')

def f(eq, xs, all_variables='abc'):
    ys = set(eq).intersection(all_variables).difference(xs)
    return ys.pop() if len(ys) == 1 else None

target = 'c'

xs = ['a']

def find_steps(eqs, xs, f, target):
    if target in xs:
        return (('', xs),)
    paths = [(('', frozenset(xs)),)]
    for _ in range(len(eqs)):
        new_paths = []
        for path in paths:
            _,xs = path[-1]
            for eq in eqs:
                y = f(eq, xs)
                if y is not None:
                    new_path = path + ((eq, xs.union({y})),)
                    if y == target:
                        return new_path
                    new_paths.append(new_path)
        paths = new_paths
    return None

print( find_steps(eqs, xs, f, target) )
# (('', {'a'}),
#  ('a + b = 12', {'b', 'a'}),
#  ('3 * a + 2 * b + c == 0', {'b', 'c', 'a'}))

一些解释。外循环 for _ in range(len(eqs)): 在概念上不是 for 循环。这是一个运行s 的循环，直到找到目标（在这种情况下循环被 return new_path 打破）或者直到循环运行太久而没有找到目标：最长路径不能长于方程的数量。或者可以吗？如果可以，则需要修改停止条件。

我们实现了 breadth-first-search。在外循环的迭代 i 处，paths 是长度为 i 的所有路径的列表。对于每个长度为 i 的路径，我们尝试以所有可能的方式将其扩展为长度为 i+1 的路径，并将这些新路径添加到 new_paths.

路径是一系列步骤。一步是一对 (equation, known_variables)。初始步骤始终是 ('', initial_known_variables)。如果新步骤包含新的已知变量，我们只会扩展路径。

Answer 2

你构建了一个依赖图。然后你填写给定的变量，计算取决于什么，计算什么取决于你刚刚计算的等等

这当然并不总是奏效，您可能会立即或在执行某些此类步骤后陷入死胡同。最简单的例子是方程组：

a + b + c + 3 = 0
a - b + c - 5 = 0

你得到的是 c = 42，a 是多少？或者更糟的是，依赖于 a 的其他变量是什么（并且可能是其他方程组的一部分）？您可以在此处执行高斯消去法来计算 a，但是如果您有一个 non-linear 系统或您无法分析的方程怎么办？然后你需要将一堆方程式发送给求解器。

所以现在您没有依赖于其他变量的变量，而是组依赖于其他组的变量。在上面的例子中，{a, b} 依赖于 c（并且 {a, c} 依赖于 b，而 {b, c} 依赖于 a）。

人们可能会想在 组变量 的图表上运行某种 shortest-path 算法。然而，在一个包含 50 个方程和 50 个变量的系统中，依赖于其他集合的集合的数量超出了我们的计算能力。然而，一次用数值求解整个系统是可行的。

所以有一个解决这个问题的通用方法。只需将其作为一个大方程组全部提供给求解器即可。你得到一堆变量赋值，没有任何明确的解决步骤序列（除非你考虑 Newton-Raphson 的迭代或任何“解决步骤”）。然后有特定的方法来解决特定的受限类型的系统，为您提供清晰的解决方案步骤（线性系统、single-variable 方程组及其组合）。当然，你可以有一些明确定义的求解步骤，然后一次求解一大组方程，因为你没有其他方法可以求解它们，然后有一些更明确的步骤，然后求解一个不同的方程组，等等。

因此，您可以尝试遍历依赖关系图并生成解决方案步骤，但您总是有可能会卡在某个只能一次解决所有问题的大型系统中。更糟糕的是，可能有不同的解决方案，所有这些都是通过求解不同的方程组，当然有些系统表现不佳（具有不稳定的解决方案，或者难以猜测合适的近似值的解决方案，等等） .

还不如省去所有这些麻烦，把你所有的东西都扔给数值求解器，让它来解决这个问题。

（方程式是指任何看起来像 'f(x, y, ...) = 0' 的对象，其中 f 是某个函数。有时你会知道函数是什么，即它是象征性地给你的，有时你不知道t，即它是由对您不透明的外部算法计算得出的）。

解决关系集的算法

An algorithm to solve sets of relations

algorithm

solver

equation-solving