3

再帰的なバックトラッキングの問題を解決する必要があるというこの問題があります。これはn-queenの問題によく似ていますが、非対称ボードでさまざまな候補を使用する方法が異なります。合計4つの異なる候補があり、それぞれが相互に依存しています。私は2つのエース、2つのキング、2つのクイーン、2つのジャックを持っています。各エースはキングの隣（水平または垂直）である必要があり、各キングはクイーンの隣である必要があり、各クイーンはジャックの隣である必要があり、どのピースもそれらの隣に複製を持つことができます。適切なソリューションを備えたボードは次のようになります。

Grid (y, x)(only the positions between *y,x* are available for candidates): 
4,1 4,2 *4,3* 4,4
3,1 *3,2* *3,3* *3,4*
*2,1* *2,2* *2,3* 2,4
1,1 1,2 *1,3* 1,4

Possible Solution
. . K . 
Q J Q .
. A K A
. . J .

今、私の問題は、ツリーを使用して、ツリーの親と子として候補を追跡したいということです。私はまだツリーを実装していませんが、この例に示されている方法がからツリーを作成するための良い方法であるかどうか疑問に思いました。そして、これがツリーを作成するための良い方法である場合、どのように開始すればよいですか、ツリーはどのようにして子のどちらの親にすべきかを認識し、ソリューションが適合しない場合に戻ることができますか？

よろしくお願いします。この状況について十分な情報を追加したと思います。

4

1 に答える 1

1

ここでは間違っているかもしれませんが、この場合、再帰検索アルゴリズムがどのように機能するかを完全に理解しているようには見えません。構築するツリー構造は通常、明示的に実装されていません。代わりに、検索ツリーのように見える再帰呼び出しの構造です。ここhttp://en.wikipedia.org/wiki/Backtrackingで擬似コードの実装を見ると、ツリー構造が含まれておらず、バックトラッキング（rejectがtrueを返したときに実行）が返されるだけで実行されることがわかります。現在の呼び出しから。

あなたの場合、コピーするのではなく、単一のデータ構造で検索を実行したい場合があるため、バックトラックとは、置いたばかりの候補部分を削除してから戻ることを意味します。

于 2011-02-12T15:58:44.063 に答える