algorithm - 確率的アルゴリズムとヒューリスティック アルゴリズムの違い

Question

streetparadeの問題を拡張して、確率的アルゴリズムとヒューリスティック アルゴリズムの違いがあるとすれば、それは何かを尋ねたいと思います。

確率的アルゴリズムは実際にはヒューリスティックの一種であると言うのは正しいでしょうか?

Answer 1

TTBOMK、「確率的アルゴリズム」は標準的な用語ではありません。ただし、「ランダム化されたアルゴリズム」は、おそらくここで意味されているものです。

Randomized:何らかの方法でランダム性を使用します。モンテカルロアルゴリズムは常に制限時間内に終了しますが、最適解を保証しません。一方、ラスベガスアルゴリズムは、必ずしも有限時間内に終了するとは限りませんが、最適解を見つけることを約束します。(通常、予測実行時間も有限である必要があります。) 一般的なモンテカルロ アルゴリズムの例: MCMC、シミュレートされたアニーリング、および Miller-Rabin 素数テスト。ランダム化されたピボット選択によるクイックソートは、常に有限時間内に終了するラスベガスのアルゴリズムです。ランダム性を使用しないアルゴリズムは決定論的です。

ヒューリスティック:正しい答えが見つかる保証はありません。ヒューリスティックではないアルゴリズムは正確です。

多くのヒューリスティックは、ビン パッキング問題の First-Fit ヒューリスティックで注文項目が考慮されるなど、真の解に影響を与えない入力の「偶発的な」プロパティに敏感です。この場合、それらはモンテカルロのランダム化されたアルゴリズムと考えることができます。入力をランダムに並べ替えて再実行し、見つけた最良の答えを常に維持することができます。OTOH、他のヒューリスティックにはこのプロパティがありません。たとえば、First-Fit-Decreising ヒューリスティックは、常に最初にアイテムをサイズの小さい順にソートするため、決定論的です。

特定のランダム化されたアルゴリズムの可能な出力のセットが有限であり、真の答えが含まれている場合、最終的にそれを見つけるのに十分な時間実行することが「実質的に保証」されます (それを見つけられない確率を任意に小さくすることができるという意味で、しかし、決して 0 ではありません)。ヒューリスティックへの入力の置換によって正確な答えが得られるとは限らないことに注意してください。First-Fit の場合、これが正しいことが判明しましたが、これは2009 年に証明されたばかりです。

ランダム化されたアルゴリズムの収束について、より強力なステートメントを作成できる場合があります。これらは通常、「任意の小さなしきい値 d について、t ステップ後、確率 f(t, d) で最適解から d 以内になる」という行に沿っています。 f(t, d) t と d の増加関数。