algorithm - 当你只有一大组输入/输出对时，你如何找到函数的定义？

Question

假设您得到了一个输入/输出对列表:

f 0 = 0
f 1 = 2
f 2 = 1
f 3 = -1
f 4 = 0
f 5 = 0
f 6 = -76
f 7 = -3
f 8 = 3
f 9 = -1
f 10 = -1
f 11 = -6
f 12 = -1
f 13 = -1
f 14 = 4
f 15 = -2
f 16 = -10
f 17 = 0
f 18 = 0
f 19 = -1
f 20 = 2
f 21 = 3
f 22 = 0
f 23 = 4
f 24 = 2
f 25 = -1
f 26 = 0
f 27 = 0
f 28 = -4
f 29 = -2
f 30 = -14

现在假设您被要求使用一个适当的小数学公式而不是值的枚举来找到 f 的定义。也就是说，答案应该是 f x = floor(tan(x*x-3))(或类似的)，因为这是一个对每个输入都正确的小公式。你会怎么做？

Answer 1

所以让我们简化一下。你想要这样的功能

f 1 = 10
f 2 = 3
f 3 = 8

存在 a formula立即找到满足这些要求的多项式函数。特别是

f x = 6 * x * x - 25 * x + 29

有效。事实证明，如果你有任何函数的图形

{ (x_1, y_1), (x_2, y_2), ..., (x_i, y_i) }

您可以立即构建一个与这些输入和输出完全匹配的多项式。

---

因此，鉴于存在这样的多项式，您永远无法在不强制执行更多约束的情况下解决您的问题(找到特定的解决方案，如 floor(tan(x*x-3)))。特别是，如果您不以某种方式取缔或惩罚多项式，那么我将始终将它们提供给您。

一般来说，您想要做的是 (a) 定义搜索空间和 (b) 定义适应度指标，也称为损失函数。如果您的搜索空间是有限的，那么您会立即找到自己的解决方案:根据您的损失函数对搜索空间的每个元素进行排序，然后从一组解决方案中随机选择最佳的解决方案。

虽然听起来您要求的要难得多 — 如果您正在查看所有可能程序 的空间，那么这个空间大得令人难以置信。除非我们严格限制自己或接受近似值，否则不可能穷尽地搜索它。其次，我们必须非常了解您的损失函数及其与搜索空间的交互方式，因为我们希望做出明智的猜测以在这个广阔的空间中前进。

您提到了遗传算法——它们经常因这类工作而受到称赞，实际上它们可以成为一种在具有不确定损失函数的大空间中驱动搜索的方法，但它们失败的次数也和成功的次数一样多。真正擅长使用遗传算法解决问题的人会花费所有时间来设计搜索空间和损失函数，以引导算法找到有意义的答案。

---

如果您小心的话，现在可以对一般程序执行此操作。事实上，这是 the subject of last year's ICFP programming contest .特别是搜索 this page “2013 年 ICFP 竞赛规则”查看设置。