11

プログラムのアルゴリズムの複雑さを見つける方法がわからないので、「どうやって見つけるのか」を探しています。

効率を考慮せずにJavaを使用して数独ソルバーを作成しました（再帰的に動作するようにしたかったので、成功しました！）

いくつかの背景：

私の戦略では、バックトラックを使用して、特定の数独パズルについて、パズルに固有の解決策が1つしかないかどうかを判断します。だから私は基本的に与えられたパズルを読んでそれを解きます。1つの解決策を見つけたら、必ずしも完了しているわけではありません。さらに解決策を探し続ける必要があります。最後に、考えられる3つの結果のいずれかが発生します。パズルがまったく解決できない、パズルに固有の解決策がある、またはパズルに複数の解決策がある。

私のプログラムは、行、列、および数字で構成される、指定された数字ごとに1行のファイルからパズルの座標を読み取ります。私自身の慣習により、7の左上の正方形は007と書かれています。

実装：

ファイルから値をロードし、2次元配列に格納します。空白（未入力の値）が見つかるまで配列を下に移動し、1に設定します。競合がないかどうかを確認します（値がiかどうか）。入力されたものは有効かどうか）。はいの場合、次の値に移動します。いいえの場合、機能する桁が見つかるまで値を1ずつインクリメントします。機能しない桁（1〜9）がない場合は、調整した最後の値に1ステップ戻り、その値をインクリメントします（再帰を使用）。 ）。81個​​の要素がすべて満たされたら、競合することなく解決が完了しました。解決策が見つかったら、端末に印刷します。それ以外の場合、最初に変更した最初の要素で「1ステップ戻る」ことを試みると、解決策がなかったことを意味します。

私のプログラムはどのように複雑さをアルゴリズム化できますか？線形かもしれないと思った[O（n）]が、配列に何度もアクセスしているので、よくわかりません:(

どんな助けでも大歓迎です

4

2 に答える 2

29

O( n ^ m ) ここで、nは各正方形の可能性の数 (つまり、従来の数独では 9) で、mは空白のスペースの数です。

これは、単一のブランクから逆方向に作業することで確認できます。空白が 1 つしかない場合は、最悪の場合に取り組まなければならない可能性がn 個あります。空白が 2 つある場合、最初の空白の可能性ごとに、最初の空白の可能性を n 個、2 番目の空白の可能性を n 個検討する必要があります。空白が 3 つある場合、最初の空白についてn 個の可能性を検討する必要があります。これらの可能性のそれぞれから、n ^2 の可能性を持つ 2 つの空白があるパズルが生成されます。

このアルゴリズムは、可能な解に対して深さ優先検索を実行します。グラフの各レベルは、1 つの正方形の選択肢を表します。グラフの深さは、塗りつぶす必要がある正方形の数です。nの分岐係数とmの深さを使用して、グラフ内で解を見つけると、最悪の場合のパフォーマンスは O( n ^ m ) になります。

于 2013-03-10T21:02:49.317 に答える
2

多くの数独には、少し考えて直接配置できる数字がいくつかあります。最初の空のセルに数字を入れることで、可能性を減らす多くの機会をあきらめることになります。最初の 10 個の空のセルに多くの可能性がある場合、指数関数的に増加します。私は質問をします：

最初の行のどこに数字の 1 を入れることができますか?

最初の行のどこに数字の 2 を入れることができますか?

...

最後の行のどこに数字の 9 を入れることができますか?

同じですが、9 つの列がありますか?

同じですが、9つのボックスで？

最初のセルに入る数字は?

81番目の枡に入る数字は？

324問です。答えが 1 つだけの質問がある場合は、その答えを選択します。質問にまったく答えがない場合は、後戻りします。すべての質問に 2 つ以上の回答がある場合は、回答の数が最も少ない質問を選択します。

指数関数的に増加する可能性がありますが、それは本当に難しい問題の場合のみです。

于 2014-03-28T22:20:34.450 に答える