5

三項探索アルゴリズムは、増加してから減少する関数、または減少してから増加する関数である単峰関数の最小値または最大値を見つけるための高速アルゴリズムです。減少してから増加する関数を扱っており、値の最小値を見つけたいと仮定します。三項検索は、次の再帰を使用して機能します。

  • ウィンドウのサイズが「十分に小さい」場合は、その中間点を返します。
  • さもないと：
    • 左右の境界で関数を評価します。値を l および r と呼びます。
    • 1/3 点と 2/3 点で関数を評価します。値を m 1および m 2と呼びます
    • m 1 < m 2の場合、関数の増加領域にあり、最小値は m 2と rの間にありません。
    • m 1 > m 2の場合、関数の減少領域にあり、最小値が l と m 1の間にあることはできません
    • 破棄されなかった 2/3 を再帰的に検索します。

このアルゴリズムは、反復ごとに 1/3 の値を捨て続けることができるため、迅速に機能します。

ただし、このアルゴリズムをより高速に実行できると信じているため、何かが欠けているように感じます。特に、境界とプローブ ポイントの 1 つとの間の範囲の 3 分の 1 を常に除外していることに注意してください。これは、プローブ ポイントと他の境界の間の領域を保持することを意味します。三分探索は 1/3 ポイントでプローブ ポイントを選択するため、これは、各ポイントで値の 2/3 を保持することを意味します。1/3 と 2/3 のポイントでプローブする代わりに、1/2 - ε と 1/2 + ε のポイントでプローブして、非常に小さい ε を求めたらどうなるでしょうか? これは、各ステップで範囲の 1/2 - ε を破棄することを意味します。これは、毎回要素の 1/3 を単に破棄する場合よりも、範囲のサイズがはるかに速く減少することを意味します。

例として、ε = 1/1000 を選択すると、各反復で検索する範囲の 999/2000 を破棄することになります。いくつかの反復の後に残っている部分がここに示されています (三項探索は左側にあり、私のアルゴリズムは右側にあります:)

 1 :                1.0  >=                1.0
 2 :     0.666666666667  >=             0.5005
 3 :     0.444444444444  >=         0.25050025
 4 :     0.296296296296  >=     0.125375375125
 5 :     0.197530864198  >=    0.0627503752501
 6 :     0.131687242798  >=    0.0314065628127
 7 :    0.0877914951989  >=    0.0157189846877
 8 :    0.0585276634659  >=   0.00786735183621
 9 :    0.0390184423106  >=   0.00393760959402
10 :    0.0260122948737  >=   0.00197077360181
11 :    0.0173415299158  >=  0.000986372187705
12 :    0.0115610199439  >=  0.000493679279947
13 :   0.00770734662926  >=  0.000247086479613
14 :   0.00513823108617  >=  0.000123666783046
15 :   0.00342548739078  >=  6.18952249147e-05
16 :   0.00228365826052  >=  3.09785600698e-05
17 :   0.00152243884035  >=  1.55047693149e-05
18 :   0.00101495922690  >=  7.76013704213e-06
19 :  0.000676639484599  >=  3.88394858959e-06

この修正版のアルゴリズムは、元のバージョンよりも「優れている」だけですか? それとも、プローブ ポイントを選択するために変更された戦略を使用すべきではないことを意味する、ここで欠けているものはありますか?

4

2 に答える 2

3

このバージョンは確実に収束が速くなりますが、浮動小数点の精度の問題が発生しやすくなる可能性があります。たとえば、m + eps = m の場合はどうなるでしょうか。たとえば、m が大きい場合、それは現実的な可能性です。したがって、精度と収束率の間にはトレードオフがあります。このクラスで最も優れたアルゴリズムは、間違いなく高速で正確な黄金分割検索です。

于 2011-12-14T10:15:10.803 に答える
1

関数が単峰性である場合、g(y) = F(y+ε) - F(y) は、y を左から右の境界に増加させるときに 1 回だけゼロを交差します。

基本的に、2 番目の改善されたアルゴリズムで提案するのは、g(y) のゼロクロッシング (ルート) のバイナリ検索です。最小化を行っていると仮定すると、F(y) には最小値が 1 つあります。その後、G(y) はしばらく負になり、その後正になります。したがって、g(x) <0 の場合、根は x (より正確には x+ε) よりも大きく、g(x)>0 の場合、根は x よりも小さくなります。

これは、最初の/元のアルゴリズムよりも高速です (最悪の場合)。これは、最小値が配置されている領域が 2/3 倍されるのではなく、各ステップで半分になるためです。

于 2011-12-14T14:01:57.890 に答える