目次:
定義-バックトラッキングとはどういう意味ですか？
バックトラッキングは、特定の計算問題、特に制約充足問題の一部またはすべてのソリューションをキャプチャするためのアルゴリズムです。 このアルゴリズムは、「部分的な候補解」の概念を受け入れることができる問題に対してのみ使用でき、候補解が完全な解になり得るかどうかをすばやくテストできます。 バックトラッキングは、制約充足の問題とパズルを解決するための重要な手法と考えられています。 また、解析のための優れた手法と見なされ、多くのロジックプログラミング言語の基礎を形成します。
Techopediaはバックトラッキングを説明します
バックトラッキングは、最初のサブ問題の解決策を見つけ、最初の問題の解決策に基づいて他のサブ問題を再帰的に解決することにより、全体的な問題を解決するのに役立ちます。 現在の問題を解決できない場合、ステップはバックトラックされ、次の可能な解決策が前のステップに適用され、さらに先に進みます。 実際、バックトラッキングで重要なことの1つは再帰です。 また、分割統治を使用した網羅的検索の方法としても考えられています。 バックトラッキングアルゴリズムは、最初のサブ問題に対する解決策がなくなると終了します。
バックトラッキングは、非決定性の実装を実現するのに役立つアルゴリズムです。 特定の発行スペースの深さ優先検索を行います。 Prologのようなロジックプログラミング言語で主に使用されます。 バックトラッキングを適用できる場合は、1回のテストで多数の候補を排除するため、ブルートフォーステクニックよりも高速です。
