三分探索を楽しむ

今年は Advent of Code チャレンジに参加する初めての年で、今日 (2021 年 7 日目) のチャレンジは楽しいものです。

詳細には触れませんが、問題は関数の最小値を見つけることです。この関数は整数を取り、別の整数を返します。この関数の興味深い特性は、1 つの「谷」があることです。大域的極小点の左側にあるものはすべて単調減少します。グローバル極小点の右側にあるものはすべて単調増加します。

関数の出力は、

のような整数の集まりと考えることができます。
100, 81, 56, 32, 16, 33, 44, 78, 129

そして、値 16 を見つけたいと思います。

単純に、ドメイン内のすべてのポイントで関数を評価してから最小値を見つけることができます。また、結果が増加し始める場所が見つかるまで関数を評価するのが少し良い方法です。どちらの方法でも O(n) が必要です。 時間はかかりますが、データが適切に「並べ替えられている」ため、より良い結果が得られます。

二分探索に似た三分探索は、データのパターンを活用し、O(log n) を達成できます。 漸近時間。ウィキペディアでは、これを「ユニモーダル関数の最小値または最大値を見つける」ための手法として説明しています。これは、まさに解決したい関数です。基本的な考え方は単純です:ドメインを 2 つのポイントで 3 つのセグメントに分割すると:leftright 、それから left で関数を評価できます および right いくつかのケースを取得します:

  • f(left) < f(right)
  • f(left) > f(right)
  • f(left) == f(right)

f(left) < f(right) の場合 、これは両方の left を意味します と right ポイントが極小値の位置、または left より大きい 極小値および right の位置よりも小さい は極小値の位置よりも大きいです。どちらの場合も、極小値が right の右側にないことがわかっています。 であるため、ドメインのその部分を破棄できます。

f(left) > f(right) の場合 、同様に left の左側を破棄できます . f(left) == f(right) の場合 、両側を破棄して範囲 [left, right] のみを保持できます .

ドメインを left に等分できます と right 、その後、上記のプロセスを再帰的または反復的に実行して、問題を解決できます。まだ終了条件が必要です:left 以来 と right right - left <= 2 の場合はスタックする可能性があります 、そこで停止し、線形検索に戻ります。そして、次の疑似コードを使用できます:

var left = domain.min
var right = domain.max
while (right - left) > 3 {
  let left_third = left + (right - left) / 3
  let right_third = right - (right - left) / 3

  if f(left_third) < f(right_third) {
    right = right_third
  } else {
    left = left_third
  }
}

for i in left until right get the smallest f(i)

これはエレガントで楽しいアルゴリズムであり、今日初めて聞いたことに驚いています。また、このアルゴリズムをいつ、どのように使用するかについても理解していただければ幸いです。