私は最適化の経験があまりありませんが、質問で説明されているような二分アルゴリズムを使用して、この問題の解決策を構築しました。場合によってはルートの2倍を計算するため、ソリューションのバグを修正する必要があると思いますが、これは単純で、後で試す予定です。
編集：私はのコメントのようですjpalecek、そして今私は私が仮定したいくつかの前提が間違っていることを理解していますが、方法はまだほとんどの場合に機能します。より具体的には、ゼロは、2つの関数が反対方向で信号を変化させる場合にのみ保証されますが、頂点でゼロの場合を処理する必要があります。それに対して正当で満足のいくヒューリスティックを構築することは可能だと思いますが、それは少し複雑であり、今ではより有望な関数を取得しf_abs = abs(f, g)、ローカル最小値を見つけるためのヒューリスティックを構築して、エッジの中央。
序章
質問の構成を検討してください。
^
| C D
y2 -+ o-------o
| | |
| | |
| | |
y1 -+ o-------o
| A B
o--+------+---->
x1 x2
これを行うには多くの方法がありますが、私はコーナーポイント（A、B、C、D）のみを使用し、質問が示唆する中間点や中心点は使用しないことを選択しました。あなたが説明するように、私が2つの関数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))
長方形の2つの反対側から製品を調べ、それらの最小値を計算します。これは、信号が負の場合に変化する信号の存在を表します。少し冗長ですが、うまく機能します。代わりに、ポイントを使用するなどの他の構成を試すこともできます（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 ）で同様のコードを使用し、アルゴリズムとルートの長方形を描画します（システムには原点にバランスポイントがあります）：
Rectangles
それはうまくいきます。
改善
場合によっては、アルゴリズムは同じゼロの2倍を計算します。私はそれが2つの理由を持っている可能性があります：
- 私の場合、関数は隣接する長方形で非常にゼロになります（数値の切り捨てのため）。この場合の解決策は、増やす
eps（長方形を増やす）ことです。私が選んだeps=2e-32のは、32ビットが（64ビットアーキテクチャの）精度の半分であるため、関数がゼロを与えない可能性が高いからです...しかし、それは推測のようでした。より良い。ただし、を大幅に減らすとeps、Pythonインタープリターの再帰制限が推定されます。
- 魔女の場合、f（A）、f（B）などはゼロに近く、積はゼロに切り捨てられます。関数の積の代わりにfとgの信号の積を使うと減らすことができると思います。
- 長方形を破棄する基準を改善することは可能だと思います。これは、長方形の領域で関数がどれだけ変化しているか、および関数がゼロからどれだけ離れているかを考慮して作成できます。おそらく、コーナーの関数値の平均と分散の間の単純な関係です。別の方法（およびより複雑な方法）では、スタックを使用して各再帰インスタンスの値を格納し、この値が収束して再帰を停止することを保証できます。
