我在优化方面没有太多经验，但我用问题描述的二分算法为这个问题建立了一个解决方案。我认为有必要修复我的解决方案中的错误，因为它在某些情况下会计算两次根，但我认为这很简单，稍后会尝试。
编辑：我似乎是 的评论jpalecek，现在我明白我假设的一些前提是错误的，但这些方法在大多数情况下仍然有效。更具体地说，只有当两个函数在相反方向改变信号时才保证零，但需要处理顶点处为零的情况。我认为有可能为此建立一个合理且令人满意的启发式方法，但它有点复杂，现在我认为更有希望得到由给出的函数f_abs = abs(f, g)并建立一个启发式方法来找到局部最小值，着眼于梯度方向上的点边缘的中间。
介绍
考虑问题中的配置：
^
| C D
y2 -+ o-------o
| | |
| | |
| | |
y1 -+ o-------o
| A B
o--+------+---->
x1 x2
有很多方法可以做到这一点，但我选择只使用角点（A、B、C、D），而不是像问题所暗示的那样使用中间点或中心点。假设我有你描述的两个函数 f(x,y) 和 g(x,y) 。事实上，它通常是一个函数 (x,y) -> (f(x,y), g(x,y))。
步骤如下，最后有一份简历（带有 Python 代码）。
一步一步的解释
- 由它们自己在相邻点计算每个标量函数（f 和 g）的乘积。计算每个变化方向（轴、x 和 y）的最小乘积。
Fx = min(f(C)*f(B), f(D)*f(A))
Fy = min(f(A)*f(B), f(D)*f(C))
Gx = min(g(C)*g(B), g(D)*g(A))
Gy = min(g(A)*g(B), g(D)*g(C))
它通过矩形的两个相对边查看乘积并计算它们的最小值，如果其为负值，则表示存在信号变化。这有点冗余，但工作很好。或者，您可以尝试其他配置，例如使用点（问题中显示的 E、F、G 和 H），但我认为使用角点是有意义的，因为它可以更好地考虑矩形的整个区域，但这只是一个印象。
- 计算每个函数的拖轴的最小值。
F = min(Fx, Fy)
G = min(Gx, Gy)
这个值的它表示矩形内每个函数 f 和 g 的存在为零。
- 计算它们的最大值：
max(F, G)
如果 max(F, G) < 0，则矩形内有一个根。另外，如果 f(C) = 0 和 g(C) = 0，也有一个根，我们也这样做，但如果根在其他角落，我们忽略他，因为其他矩形会计算它（我想避免重复计算根）。下面的声明继续：
guaranteed_contain_zeros = max(F, G) < 0 or (f(C) == 0 and g(C) == 0)
在这种情况下，我们必须继续递归地破坏区域，直到矩形尽可能小。
否则，矩形内可能仍然存在根。正因为如此，我们必须使用一些标准来打破这个区域，直到我们有一个最小的粒度。我使用的标准是断言当前矩形的最大尺寸小于原始矩形的最小尺寸（delta在下面的代码示例中）。
恢复
此 Python 代码简历：
def balance_points(x_min, x_max, y_min, y_max, delta, eps=2e-32):
width = x_max - x_min
height = y_max - y_min
x_middle = (x_min + x_max)/2
y_middle = (y_min + y_max)/2
Fx = min(f(C)*f(B), f(D)*f(A))
Fy = min(f(A)*f(B), f(D)*f(C))
Gx = min(g(C)*g(B), g(D)*g(A))
Gy = min(g(A)*g(B), g(D)*g(C))
F = min(Fx, Fy)
G = min(Gx, Gy)
largest_dim = max(width, height)
guaranteed_contain_zeros = max(F, G) < 0 or (f(C) == 0 and g(C) == 0)
if guaranteed_contain_zeros and largest_dim <= eps:
return [(x_middle, y_middle)]
elif guaranteed_contain_zeros or largest_dim > delta:
if width >= height:
return balance_points(x_min, x_middle, y_min, y_max, delta) + balance_points(x_middle, x_max, y_min, y_max, delta)
else:
return balance_points(x_min, x_max, y_min, y_middle, delta) + balance_points(x_min, x_max, y_middle, y_max, delta)
else:
return []
结果
我在个人项目（此处为 GitHub ）中使用了类似的代码，它绘制了算法的矩形和根（系统在原点有一个平衡点）：
矩形
它运作良好。
改进
在某些情况下，该算法计算两次相同的零。我认为它可能有两个原因：
- 在这种情况下，函数在相邻矩形处给出的值为零（由于数字截断）。在这种情况下，补救措施是
eps增加（增加矩形）。我选择eps=2e-32，因为 32 位是精度的一半（在 64 位架构上），那么该函数很可能不会给出零……但这更像是一个猜测，我现在不知道更好的。但是，如果我们减少很多eps，它会推断 Python 解释器的递归限制。
- f（A），f（B）等的情况接近于零，并且产品被截断为零。我认为如果我们使用 f 和 g 信号的乘积代替函数的乘积，它可以减少。
- 我认为可以改进丢弃矩形的标准。可以考虑函数在矩形区域中变化的程度以及函数为零的距离。也许是角上函数值的平均值和方差之间的简单关系。以另一种方式（更复杂），我们可以使用堆栈来存储每个递归实例上的值，并保证这些值收敛以停止递归。
