1

バックトラッキングアルゴリズムの設計手法について読んでいます。それは次のように述べられています。

バックトラッキングはブルートフォースアプローチの改良版であり、利用可能なすべてのオプションの中から問題の解決策を体系的に検索します。これは、解が値のベクトル(v1、v2、...、vm)で表されると仮定し、解が見つかるまで深さ優先の方法でベクトルのドメインをトラバースすることによって行われます。

上記のテキストに関する私の質問は次のとおりです。

  1. ソリューションがベクトルで表されるとは、作者はどういう意味ですか?

  2. ベクトルのドメインとは、作者とはどういう意味ですか?

明確にしていただきありがとうございます。

4

1 に答える 1

3

エイトクイーンの問題を例にとってみましょう。

解は、各女王に1つずつ、8つの位置のベクトルです。ベクトルはスペースに属します:([0,7]x[0,7])^8。これは非常に大きなスペースであるため、バックトラッキングアルゴリズムは次の条件を使用します。「クイーンは別のクイーンをチェックしない」([0,7]x[0,7])^8、解ベクトルが存在する小さな「ドメイン」(のサブスペース)に制限します。

この場合、アルゴリズムは、最初の女王に許可された値の1つを試して、ベクトルを与えることにより、解のベクトルを作成します[ (0,0), X, X, X ...]。次に、条件を使用して、2番目の位置を検索する部分空間を制限し、適切なベクトルが見つかるまでこれを続けます。

深さ優先とは、解のドメインに移動する前に[ (0,1), X, X, X ...]、アルゴリズムがによって定義されたドメインからすべての潜在的なベクトルを使い果たすことを意味します。[ (0,0), X, X, X ...]

于 2012-05-02T12:04:02.503 に答える