logo

TechCodeview

バックトラッキングアルゴリズム

バックトラッキングアルゴリズム 最適な解決策を見つけるためにさまざまなオプションを検討するのに役立つ問題解決戦略のようなものです。彼らはさまざまな方法を試し、もしうまくいかない場合は、正しい方法が見つかるまで後戻りして別の方法を試します。それは、さまざまなピースが完全に嵌まるまでテストすることでパズルを解くようなものです。

後戻り



目次

バックトラッキングアルゴリズムとは何ですか?

後戻り 問題解決のアルゴリズム手法であり、試行することで段階的に解決策を見つけることが含まれます。 さまざまなオプション そして 元に戻す 彼らが何かにつながるなら、 デッドエンド 。

これは、迷路で道を探したり、次のようなパズルを解くなど、問題を解決するために複数の可能性を探る必要がある状況でよく使用されます。 数独 。行き止まりに達すると、アルゴリズムは前の決定点に戻り、解決策が見つかるかすべての可能性がなくなるまで、別のパスを探索します。



バックトラッキングアルゴリズムはどのように機能するのでしょうか?

あ バックトラッキングアルゴリズム 問題に対して考えられるすべての解決策を再帰的に探索することによって機能します。まず最初のソリューションを選択し、次にそのソリューションの可能な拡張をすべて検討します。拡張が解決策につながる場合、アルゴリズムはその解決策を返します。拡張が解決策につながらない場合、アルゴリズムは前の解決策に戻り、別の拡張を試みます。

以下は、バックトラッキング アルゴリズムがどのように機能するかの概要です。

  1. 初期の解決策を選択します。
  2. 現在のソリューションの可能な拡張をすべて検討します。
  3. 拡張機能が解決策につながる場合は、その解決策を返します。
  4. 拡張機能が解決策につながらない場合は、前の解決策に戻り、別の拡張機能を試してください。
  5. 考えられる解決策をすべて検討するまで、手順 2 ～ 4 を繰り返します。

バックトラッキングアルゴリズムの例

例： 迷路を通る最短経路を見つける



入力： 2D 配列として表される迷路。 0 オープンスペースを表し、 1 壁を表します。

アルゴリズム：

  1. スタート地点からスタートします。
  2. 4 つの可能な方向 (上、下、左、右) のそれぞれについて、その方向に移動してみます。
  3. その方向に移動すると終点に到達する場合は、通った道を戻ります。
  4. その方向に移動しても終了点に到達できない場合は、前の位置に戻り、別の方向を試してください。
  5. 終了点に到達するか、すべての可能なパスが探索されるまで、手順 2 ～ 4 を繰り返します。

バックトラッキング アルゴリズムをいつ使用するか?

バックトラッキング アルゴリズムは、次の特性を持つ問題を解決するのに最適です。

  • この問題には複数の解決策が考えられます。
  • 問題は、より小さなサブ問題に分割できます。
  • 部分問題は独立して解決できます。

バックトラッキングアルゴリズムの応用

バックトラッキング アルゴリズムは、次のようなさまざまなアプリケーションで使用されます。

  • パズルを解く (例: 数独、クロスワード パズル)
  • 迷路を通る最短経路を見つける
  • スケジュールの問題
  • リソース割り当ての問題
  • ネットワーク最適化の問題

バックトラッキングアルゴリズムの基本:

  • バックトラッキングとブランチアンドバウンド手法の違い
  • バックトラッキングと再帰の違いは何ですか?

バックトラッキングアルゴリズムに関する標準的な問題:

  • 騎士のツアー問題
  • 迷路の中のネズミ
  • Nクイーン問題 |バックトラッキング-3
  • サブセットサム問題
  • m 色付けの問題
  • ハミルトニアンサイクル
  • 数独 |バックトラッキング-7
  • マグネットパズル
  • 無効な括弧を削除する
  • n ビットのグレイ コードを生成するためのバックトラッキング アプローチ
  • 指定された文字列のすべての順列を出力するプログラムを作成する

バックトラッキングアルゴリズムに関する簡単な問題:

  • すべてのサブセットを見つけるためのバックトラッキング
  • 指定された文字列が合計文字列であるかどうかを確認します
  • 2 つの頂点間の可能なパスをすべて数えます
  • 指定されたセットのすべての個別のサブセットを検索します
  • ソースから k を超える長さのパスがあるかどうかを調べる
  • 指定されたソースから宛先までのすべてのパスを出力します。
  • スペースを入れることで作成できるすべての文字列を出力します。

バックトラッキング アルゴリズムに関する中程度の問題:

  • 綱引き
  • 8クイーン問題
  • 組み合わせ合計
  • ナイトツアー問題に対するワーンズドルフのアルゴリズム
  • 迷路の隅のセルから中央のセルまでのパスを見つける
  • 最大 K 個のスワップを実行することで可能な最大数を求める
  • 複数のステップやジャンプが可能な迷路内のネズミ
  • O(n) 空間の N クイーン

バックトラッキングアルゴリズムに関する難しい問題:

  • 辞書順のパワーセット
  • バックトラッキングを使用した単語区切りの問題
  • 合計が等しい K 個のサブセットへのセットの分割
  • ハードルのあるマトリックス内の最長ルート
  • 地雷のある道で安全な最短ルートを見つける
  • 文字列のすべての回文パーティションを出力します。
  • N-Queen 問題のすべての解を出力する
  • すべての最も長い共通サブシーケンスを辞書順に出力します。

クイックリンク ：

  • データ構造とアルゴリズムを学ぶ | DSA チュートリアル
  • バックトラッキング アルゴリズムの面接での質問トップ 20
  • バックトラッキングの「ビデオ」