0

この質問は特定されていないかもしれませんが、非常に重要だと思います。最適化問題を解きたいが、dynamic programming方法にあまり詳しくない場合、それが最初に頭に浮かぶアイデアです。

私はいくつかの簡単な例をあげることができます：

  • リストの最小要素を取得します（非常に単純です）
  • セットのすべての順列を一覧表示します
  • セットのすべてのサブセットを一覧表示します

これらの問題はすべて成熟した方法を持っています。しかし、あまり明確ではない問題があります。

  • 2つの文字列すべてをリストしedit distanceます（つまり、編集操作の最短のものではありません）
  • common subsequence2つのシーケンスすべてをリストする
  • 括弧でくくることのすべての可能性をリストしてくださいmatrix chain multiplication

力ずくの方法でこれらの問題を解決することについて私は知りません。私の質問は：

ブルートフォースアルゴリズムですべての可能性をリストするための体系的な一般的な方法はありますか？

4

1 に答える 1

2

バックトラッキングは、問題のすべての解決策を見つけるための最も一般的な方法の1つです。ウィキペディアごとに、

バックトラッキングは、計算問題のすべて（または一部）のソリューションを見つけるための一般的なアルゴリズムであり、ソリューションの候補を段階的に構築し、cが完了できない可能性があると判断するとすぐに各部分候補c（「バックトラック」）を破棄します。有効なソリューション。

バックトラックの使用の古典的な教科書の例は、8つの女王のパズルです。これは、女王が他の人を攻撃しないように、標準のチェス盤に8つのチェスの女王のすべての配置を要求します。

あなたが言及する問題の2つ、
•2つのシーケンスのすべての一般的なサブシーケンスを
リストする•行列の連鎖乗積を括弧で囲むすべての可能性をリストする
ことは、バックトラッキングを使用して簡単に処理できます。編集距離の質問についてはよくわかりません。

于 2013-03-25T07:28:35.630 に答える