25

深さ優先検索に関するウィキペディア:

深さ優先検索 (DFS) は、ツリー、ツリー構造、またはグラフをトラバースまたは検索するためのアルゴリズムです。1 つはルート (グラフの場合はルートとしていくつかのノードを選択) から開始し、バックトラックする前に各ブランチに沿って可能な限り探索し ます。

幅優先探索とは

「開始ノードを選択し、すべてのノードのバックトラックをチェックし、最短パスを選択し、隣接ノードのバックトラックを選択し、最短パスを選択し、連続的なバックトラックにより各パスをトラバースするため、最終的に最適なパスを見つけるアルゴリズム。

Regexfindのプルーニング -- バックトラッキング?

バックトラッキングという用語は、そのさまざまな用途のために混乱を招きます。UNIX のfindSO ユーザーの剪定は、バックトラッキングで説明されました。Regex Buddy は、正規表現の範囲を制限しない場合、「壊滅的なバックトラッキング」という用語を使用します。あまりにも広く使われている包括的な用語のようです。そう：

  1. グラフ理論で特に「バックトラッキング」をどのように定義しますか?
  2. 幅優先検索と深さ優先検索の「バックトラック」とは何ですか?

[追加した]

バックトラックに関する適切な定義と例

  1. ブルートフォース法
  2. ストールマン (?) が発明した用語「依存性指向のバックトラッキング」
  3. バックトラッキングと正規表現の例
  4. 深さ優先検索の定義。
4

1 に答える 1

39

バックトラッキングは検索中に発生するものであるため、混乱が生じますが、多くのバックトラッキングが行われる特定の問題解決手法も指します。このようなプログラムはバックトラッカーと呼ばれます。

近所に車で入り、行き止まりにぶつかるまで常に最初の曲がり角 (ループがないと仮定します) を取り、行き止まりになったら次の未踏の通りの交差点に戻ります。これは「最初の」種類のバックトラッキングであり、この単語の口語的な用法とほぼ同じです。

より具体的な使用法は、深さ優先検索に似た問題解決戦略を指しますが、一部のサブツリーを続行する価値がないことに気付いたときにバックトラックします。

別の言い方をすれば、ナイーブな DFS は、ゴールに到達するまで盲目的に各ノードを訪問します。はい、リーフノードで「バックトラック」します。しかし、バックトラッカーは、役に立たないブランチでもバックトラックします。1 つの例は、Boggle ボードで単語を検索することです。各タイルは 8 つの他のタイルに囲まれているため、ツリーが巨大になり、単純な DFS では時間がかかりすぎます。しかし、「ZZQ」のような組み合わせが表示された場合は、文字を追加しても単語にならないため、この時点から安全に検索を停止できます。

ジュリー・ゼレンスキー教授の講義が大好きです。彼女は 8 つのクイーン、数独パズル、およびバックトラッキングを使用した数字置換パズルを解決し、すべてがうまくアニメーション化されています。 プログラミングの抽象化、講義 10 プログラミングの抽象化、講義 11

ツリーは、任意の 2 つの頂点間にパスが 1 つしかないグラフです。これにより、サイクルの可能性がなくなります。グラフを検索しているときは、通常、とにかく循環を排除する何らかのロジックがあるため、動作は同じです。また、有向グラフでは、「間違った」方向にエッジをたどることはできません。

私が知る限り、彼らはストールマンの論文で、クエリに対して「はい」または「いいえ」と言うだけでなく、最小限の変更を行うことで、実際に誤ったクエリの修正を提案するロジック システムを開発しました。バックトラッキングの最初の定義がどこで機能するかがわかります。

于 2010-07-01T08:41:54.290 に答える