12

動的計画法を使用して 8-queen 問題を実装するという考えにかなり混乱しています。問題が一連の部分問題に分割され、各部分問題の最適解が見つかった場合、結果として得られる解は、これらの部分問題の解によって実現されます。この構造を持たないものは、動的計画法では解くことができません」(リファレンス)。これを考慮すると、7x7 ボードの最適なソリューションは、8x8 ボードには最適ではない (正しくない) 場合もあります。そのため、サブ問題の最適解によって問題の結果が実現しない場合があります。

一方、DP はバックトラッキング問題の最適化です... もしそうなら、8-queen 問題はバックトラッキングで解決できます... 行き止まりだけを保存することで、バックトラッキング解を DP に変換できるということですか? その場合、2,1 は親 1,1 には実行可能ではありませんが、1,2 には実行可能である可能性があります。

アップデート

動的計画法を使用して 8-queen または n-queen の問題を解決できるかどうか、誰もが考えていますか? もしそうなら、上記の観察に対するあなたのコメントは何ですか?

4

2 に答える 2

5

7x7 ボードに最適なソリューションは、8x8 には最適ではない (正しくない) 場合もあります。

はい。それで合っています。しかし、これは問題を分割する良い方法ではありません。彼の答え、定理 2.4 に投稿された論文 yi_Hを調べ、アルゴリズムの説明を見てください。彼らは、閉じた線 (つまり、女王によって脅かされている線) のセットに従って、解を等価クラスに分割します。定理 2.4は、閉じた線の特定のセットでサブ問題を解決すると、残りを個別に解決し、結果を組み合わせることができることを保証します! 非常に賢い。

于 2011-08-15T11:39:44.360 に答える
2

明らかなGoogleヒットを投稿するだけです：

n-queens 問題に対する動的計画法ソリューション

注: これは、大きな n の O ( f(n)*8^n) に対しては依然として非常に遅いため、他のアルゴリズムを使用することをお勧めします。

N クイーン問題の多項式時間アルゴリズム

于 2011-08-14T15:20:20.083 に答える