問題タブ [recursive-backtracking]

バックトラッキングを利用して空白を表す NaN を持つ 9x9 配列で表される特定の数独パズルの解を再帰的に生成する機能に取り組んでいます。

返される cellSolutions は、存在する数に応じて 0、1、またはそれ以上の解を含むセル配列です。私が抱えている問題は、最初の呼び出しで返される cellSolution に表示されるソリューションを実際に取得することです。私が望んでいるのは：

確かに、disp 呼び出しで 1 つ以上のソリューションが見つかったことを確認できますが、セル配列を操作する方法がわかりません。問題は次の点にあると確信しています。

その他の情報: reject は、現在のパズルが数独のルールを満たしているかどうかを判断します。さらに、空きスペースがないことを確認します。firstChild は、与えられた数独パズルで NaN のインスタンスを見つけ、それを 1 に変更し、変更された線形インデックスと新しいパズルを返します。nextChild は数独パズルとインデックスを受け取り、そのインデックスの値が 9 でない場合、値を増やして新しいパズルを返します。ありがとう！

countBinaryJava の練習のために、整数nをパラメーターとして受け入れ、数字を持つすべての 2 進数をn昇順で出力し、各値を別の行に出力する方法に取り組み始めました。n が負ではなく 0 より大きいと仮定すると、出力例は次のようになります。

私はこれでほとんどどこにも行きません。a と類似のもののすべての可能な文字の組み合わせを見つけるプログラムを作成することはできますが、String2 進数と整数を使用してこの特定の問題をほとんど解決することはできませんでした。

どうやらこの問題に対処する最善の方法は、元のメソッドとは異なるパラメーターを受け入れるヘルパー メソッドを定義し、一連の文字を最終的な出力用の文字列として構築することです。

重要な注意: この演習では、for ループをまったく使用しないことになっています。

編集 - 重要な注意: すべての出力が同じ長さになるように、末尾に 0 を付ける必要があります。

これまでのところ、これは私が持っているものです:

コードを実行すると、出力は次のようになります。

私のメソッドが期待どおりに実行されない理由を誰かに説明してもらえますか?また、可能であれば、正しい出力が得られるように問題の解決策を教えてもらえますか? ありがとうございました！

迷路のパス検索ソリューションを作成しています [30][30] パス検索関数でバックトラッキングを使用しました。擬似コードは次のとおりです。

bool find_path(myMap,myVisited,myPath,v,h)

1. 開始点を見つけて、その点の関数を[v,h]実行しますfind_path
2. 部屋を訪問済みとしてマークする
3. 終了条件 1: の場合h=29、パスにマークを付けてから true を返す
4. 再帰部分: 西、北西、北、北東、東、南東、南、南西の 8 つの隣人を検索します。部屋にアクセスできるかどうかを確認し、find_path 関数を呼び出します。true が返された場合は、検索パスにマークを付けます。
5. 終了条件 2: false を返す。

実行すると、常にセグメンテーション違反が発生します。別の方法を試しましたが、すべて同じエラーが発生しますか? 出力は次の画像のようになります: http://postimg.org/image/cd8unwe5/ ここに私のコードがあります:

次のプログラムをコーディングして、4 色マップ定理 (簡単に言えば、隣接する領域が同じ色になることなく、マップを 4 色だけで色付けできます) を再帰的に実装しました。すべてがコンパイルされますが、私の出力には誤ったデータが表示されます (今のところ値 0-3 ではなく、各領域の色に対して -1)。私の最大の疑問は、出力が正しくない理由です。

疑問に思っている方のために説明すると、入力ファイルは次のような隣接行列です。

これが私のコードです：

従うべきルールは 1 つだけです。各グループの合計は、その右側のグループ以上でなければなりません。

私の推測では、パーティショニングのすべてのオプションが存在するツリーを構築してから、再帰的なバックトラックを構築することです。

たとえば、配列 14 13 2 11

結果: 3. 3 つのグループ ({14}、{13}、{2、11})

私の推測は正しいと思いますか？そうでない場合、問題に対する他の解決策はありますか？

バックトラッキング ソリューションが実際に何を意味するのかについて、いくつか質問があります。

1. たとえば、現在の状態から n 個のオプションがあり、バックトラッキング ソリューションとは、基本的にこれらの状態をすべて試して、サブ問題 (ソリューションに n-1 個の状態がある場合) に対して同じことを行うことを意味しますか? (n-1) 番目のフレームから n 番目のフレームまでの最適解を返します。

以下の問題を参照してください:長さ n のロープが与えられた場合、最大の積を得るために、長さ n[0]、n[1]、...、n[m-1] の m 個の部分にロープを切断する方法of n[0] n[1] ... *n[m-1] Soa ロープの長さは 2*3*3 にカットされ、18 の積が得られます。

2. では、すべてのバックトラッキング ソリューションは、時間の複雑さにおいて指数関数的ですか?
3. これは再帰に非常によく似ているため、他の再帰によってこのようなことが達成されるとは想像できません。再帰なしで達成されたバックトラッキング ソリューションの例を教えてください
4. ブルートフォースとどう違うの？n まで足し合わせる方法のすべての可能な組み合わせを試すことは、この問題の強引な解決策です。上記のバックトラッキング ソリューションは、ほとんど同じことを行っていることがわかりました。

JAVA を使用して、次のような n 行 n 列のテーブルを含むテキスト ファイルを読み込む必要があります (ただし、サイズは異なる場合があります)。

0110
1000
1001
0010

n を人数とします。この表は、人物 (行) と別の人物 (列) の関係を示しています。テーブルの値が 1 の場合、2 つは友達です。0 の場合、それらは友達ではありません。たとえば、(0,1) は 1 です。したがって、1 と 2 は友達です。テーブル内の各人に、指定された数の文字 (この特定のテーブルの場合: 2) から文字を割り当てる必要があります。2 人が友達である場合、別の手紙を受け取る必要があります。人々は自分自身と友達とは見なされません。RECURSIVE BACKTRACKING を使用して、このパズルの解決策を見つけて印刷するか、解決策がないと判断する必要があります。

編集: 表に明示的に記載されていない限り、友達の友達は友達とは見なされません。たとえば、この表では、1 は 2 および 3 と友達です。ただし、2 と 3 は友達ではありません。1 と 3 は友達、3 と 4 は友達ですが、1 と 4 は友達ではありません。ここでの番号付けは自然ですが、実際にはテーブルのインデックスは 0 から始まります。

この問題をどこから始めればよいかわかりません。テーブルには (0,0) から (n,n) までの対称線があることに気付きます。なぜなら、(1,2) が友達である場合、(2,1) も友達であり、誰も自分自身の友達ではないからです ( n,n) は常に 0 になります。

編集:視覚的に表示するには、問題を解決するには太字の情報のみが必要なようです。

0 110
10 00
100 1
0010

常に人 1 に文字 A を割り当て、行を調べて値 1 の場所に別の文字を割り当てることはもっともらしいようです。これを正確に行う方法がわかりません。2 と 3 の異なる文字を割り当てる必要はありません。この時点で文字を入力します (バックトラックで後で処理します)。

編集:次を使用して、人に乱数を割り当てることができます(後で文字に変換されます)。次に、その番号を除外リストに追加して、これらの番号が値 1 (友人) を持つ行内の人に割り当てられないようにします。

編集：

これまでのところ、このコードがあります。ただし、バックトラッキングを使用してそれを行う方法を見つけることができないようです。また、これがより大きなテーブルで機能するかどうかはわかりません。除外の実装を修正する必要があるようです。

私を正しい道に導くのに役立つ提案はありますか?

ありがとうございました！

そこで最近、英国の GCHQ が投稿した次のパズルを見ました。

25x25 のノノグラムを解く必要があります。

ノノグラムは、隠された絵を明らかにするために、グリッドの横の数字に応じてグリッド内のセルを色付けするか空白のままにする必要がある絵論理パズルです。このタイプのパズルでは、数字は離散トモグラフィーの形式であり、特定の行または列に塗りつぶされた正方形の途切れのない行がいくつあるかを測定します。たとえば、「4 8 3」の手がかりは、4 つ、8 つ、3 つの塗りつぶされた正方形のセットがこの順序であり、連続するグループの間に少なくとも 1 つの空白の正方形があることを意味します。

当然のことながら、私はそれを解決するプログラムを作成しようとする傾向がありました。行0から始まる再帰的なバックトラッキングアルゴリズムを考えていました.行の手がかりからの情報を与えられたその行の可能な配置ごとに、次の行の可能な組み合わせを配置し、列が与えられた有効な配置であるかどうかを検証します.手がかり。そうである場合は、すべての行が有効な構成に配置されるか、すべての可能な行の組み合わせが使い尽くされるまで、バックトラックを続けます。

いくつかの 5x5 パズルでテストしましたが、完璧に動作します。問題は、25x25 GCHQ パズルの計算に時間がかかりすぎることです。このアルゴリズムをより効率的にする方法が必要です - 上にリンクされたパズルを解くのに十分です. 何か案は？

これは、各行の行の可能性のセットとソルバーのコードを生成するための私のコードです (注* いくつかの非標準ライブラリを使用していますが、これは要点を損なうものではありません):

さて、私はこのグラフを持っています：

Branch and Bound に基づいて、バックトラッキングを使用して、グラフのノードを一致させる最適な方法を示すコードを作成する必要があります。したがって、この例では、最適解は である必要があります>> [(1,4),(2,3)]。しかし、私のアルゴリズムは、最適解ではないこの可能な解解を示しています>> [(1,2),(3,4)]。問題はおそらく「元に戻す」行にあると思いますが、よくわかりません...誰かがこれを解決するのを手伝ってくれたら、とても感謝しています!

これが私のコードです：