从有限的现有函数集合中组成目标函数的最快方法是什么

Question

给定一组有限的函数和两个数字a和B，确定满足f(A) = B的复合函数的最快方法是什么？

例如，如果我们有：

functions = {
f1(x) = x - 1,
f2(x) = x + 1,
f3(x) = x * x
}

以及A = 1, B = 9

则最优解为：CCD_ 3。因为f(A) = B和函数是由尽可能少的函数组成的。

要解决的最快的解决方案可能不是最佳的解决方案——任何一方面的建议都将不胜感激。

Answer 1

广度优先搜索

在您的示例中，从A=1开始计算f1(1) = 0、f2(1) = 2和f3(1) = 1。然后从那里继续(f1(0), f2(0), f3(0), f1(2), ...)，直到到达B。忽略以前计算过的数字。如果存在最优解，这将产生最优解。

如果A和B都是整数，则总是存在形式为f1(f1(...f1(A)...)或f2(f2(...f2(A)...)的解，因此搜索不是无限的。