問題タブ [knights-tour]

同様のスレッドがいくつかあることは知っていますが、SOの外でも解決策が見つかりませんでした。ここに私の問題があります: Knight's Tour 問題http://en.wikipedia.org/wiki/Knight%27s_tourに対して Warnsdorff のアルゴリズムを実装しましたが、場合によっては解決策が得られません。私が読んだいくつかの場所では、いくつかの変更によりはるかにうまく機能する可能性がありますが、どの変更がそれらであるかを誰も指定していません. 誰かが解決策を知っていますか？私は他のアルゴリズムを知っていますが、それらははるかに複雑です。

8x8 のチェス盤であっても、適切な解が得られないことがあります。これは古典的な Warnsdorff のコードなので、コードを読んでも意味がないと思います。次のステップで可能な動きをチェックし、可能な動きが最も少ないものを選択します。

深さ優先探索アルゴリズムを使用してナイト ツアー問題を解こうとしています。両方とも行き止まりになる 2 つの選択肢がある場合、アルゴリズムは常にループしているように見えます。これは、行き止まりが見つかるたびにアルゴリズムが「wasVisited」ブール値を再び false にリセットするために発生することを理解していますが、それを修正する方法がわかりません。

これが私がこれまでに持っているコードです:

前もって感謝します ：）。

編集：

更新されたコードと出力は次のとおりです。

5x5 ボードでこれを解決しようとしているので、25 個の頂点 (0 - 24) があります。現在の問題がより明確になる出力の一部を次に示します。

もちろん、出力の最後のループは発生しないはずです。

学年度の最後のプロジェクト（CS学生としての最初の年）のコードでバグを見つけるのに問題があります。ナイトツアーの問題の実装で再帰に固執しています。問題のファイルは次のとおりです：https ：//github.com/sheagunther/tsp161knightstour/blob/master/KnightsTourRecursiveSearch.java

具体的には、私の問題はコードのこのセクション（265行目から）にあります。

これがfindTour（）の終わりです。これは、現在の正方形（別名セル）から可能なすべての移動をテストするプログラムの一部であり、新しく移動した正方形からツアーを完了できる場合はtrueを返します。広場からツアーを完了できない場合は、else {に入り、移動を元に戻します。ここが問題だと思います。

現在、上記のようにコードを設定すると、プログラムは無限の再帰ループに閉じ込められます。

else{ステートメントのこの部分に注意してください。

コードのこの部分は、chessBoardの正方形を-1に変更します。これは、訪問されていないことを意味します（1 =訪問済み）。上記のように、新しい移動のcurrentRowとcurrentColumnを使用して、正方形を未訪問に戻します。これらの値は、currentRowStorageとcurrentColumnStorageを使用して以前のジャンプ値にリセットされます。

コードをに変更した場合

移動の最後の1/3程度が、いくつかの正方形の間を行ったり来たりしているという誤ったツアーを正常に検出します。これは、リセット手順を正しく処理しないことを考えると予想されます。

私の問題は、変数を宣言している場所が原因であると思われます。これは私の最初の複雑な再帰的な問題であり、currentRow/ColumnとcurrentRow/ColumnStorageの間の切り替えを正しく処理しているかどうかはわかりません。私はそれらを多かれ少なかれローカルで宣言する必要がありますか？

プロジェクトを説明するページは次のとおりです。http：//cs.usm.maine.edu/~briggs/webPage/c161/projects/KnightsTour.html

要件の関連セクションは次のとおりです。

ツアーが完了していない場合、findTourは、騎士の現在のセルから到達可能な空のセルの（おそらく空の）リストを判別し、このリストをローカルで宣言されたリスト変数、candidateNextMovesに格納します。このリスト変数をメソッドに対してローカルに宣言することが重要です。このリストが空の場合、現在の部分ツアーを延長する方法がないため、findTourはfalseを返す必要があります。リストが空でない場合、findTourは、次のようにリストの移動ごとにツアーを延長しようとします。リストを繰り返し処理し、リストの各セルについて、そのセルに次の移動を行い、L（ツアー内の移動のリスト）、B（ボードの状態の2D配列（訪問済み、この動きを反映するために、訪問されていない））、currRow、およびcurrCol。次に、再帰的に自分自身を呼び出します。呼び出しの結果をローカルで宣言されたブール変数に割り当てます。これには「success」という名前を付けることができます。成功にtrueが割り当てられている場合、findTourはtrueを返します。成功が偽の場合、findTourは、実行したばかりの移動、つまり「バックトラック」を元に戻し、candidateNextMovesの次の移動を試みます。0に初期化され、移動を元に戻すたびにインクリメントされる静的int変数backtrackCountを維持します。

注-ブール値を「success」ではなく「tourFound」と呼びました。

8X8のチェス盤では、騎士だけを考慮して、チェス盤の任意の正方形から騎士を開始する場合、目的は、正方形を繰り返さずに、最大数の正方形をカバーすることです。これまでのところ、以下のコードで最も効率的な解決策を見つけました。

1で始まる数字は、騎士がたどる道を示しています。私の質問は、このコードを修正して、64（私の場合は60に達する）の完全な答えを得ることができるかということです。

DFSを使ってプログラムナイトツアーを作ろうとしていますが、このプログラムを解決できません..いつもこのようなメッセージエラーが出るからです.

スレッド「AWT-EventQueue-0」での例外.processKnightTour(KnightTour.java:82)

誰かが私を助けてくれることを願っています..

このサイトで指定されているように、バックトラッキングを使用してナイト ツアーの問題を解決しようとしています。

サイトで提供されている実装には、 ideone で約 0.49 秒かかります。

ほぼ同じ私が実装したものは、 ideone で制限時間を超えた（5秒以上）ことを示しています。

コードで長時間実行されているのは何ですか?

私は最近C++、特にSTLについて読んでいて、KnightsTourの問題をもう一度やり直すことにしました。私はこれを実装するための最良の方法を考えています、そして私はいくつかの助けを探しています。

楽しみと練習のために、「ナイト」クラスから継承できる「ピース」基本クラスから始めようと思いました。後で他のピースを追加してみることができるように、これを実行したいと思います（ほとんどのピースがボード全体をウォークオーバーして問題を完了することはできませんが）。

したがって、「ピースクラス」には、ボード上のピースの座標と、その特定のステップで行った移動の数を格納するための、ある種のコンテナが必要になります。

これを最も効率的に行うには、x、y、およびmovesを含む64（8 * 8）の場所を持つリンクリストが必要だと思います。

STLコンテナを見ると、複数のタイプを保持するマップ以外は見つかりません。

1つのコンテナに移動数の座標ペアとintを格納するにはどうすればよいですか？ベクトル、リスト、またはマップを使用するよりも効率的な方法はありますか？カスタムコンテナが必要ですか？

ありがとう！

Knight's Tour問題を解決しようとすることに基づいてプログラムを作成しました。私は適切な解決策を思いついたと信じており、すべてがうまくいっています。

私が興味を持っている小さな問題は、将来の可能な正方形を先取りすることに基づいて最善の動きを実装するコードの小さなセクションにあります。

このように実装すると (implementation1)–</p>

ソフトウェアがハングします。なぜですか?

このような小さな無害で一見些細な変更 (implementation2) を行う場合 –</p>

その後、すべて問題なく、コードは結論に達します。

私は自分のソフトウェアを書くために netbeans 7.1 を使用していますが、それは IDE と関係があるに違いないと思ったので、'javac' とコマンドラインのみを使用してコンパイルしようとしましたが、同じ結果が得られました。このような配列パラメータ内でこのメソッド呼び出しを行うことができない理由がわかりません – 垂直 [ HERE ] または水平 [ HERE ] 式で使用される結果を返します。以前は問題なくこのようにコーディングできました。

呼び出されるメソッドは次のとおりです。</p>

上記の return ステートメントで使用されるメソッド bestmove -

すべての場所が 1 回だけ訪れられるように、可能なナイト ツアーの 1 つを印刷するために、このコードを書きました。

このコードは機能していますが、次のコードは機能していません。X[] と Y[] を少し変更しましたが、アルゴリズムには影響しません。

私はちょうど変更しました

に

私は騎士ツアーの再帰アルゴリズムを書こうとしています:

どこで間違いを犯したか教えてもらえますか？どのプール アルゴリズムがリストに追加されているかを段階的に確認しました。4,3 プールを追加してから 6,4 プールを追加した後のビッグ サプライズ アルゴリズムは、実際の位置として 6,4 でそれ自体を呼び出す必要がありますが、実際の位置として 4,3 でそれ自体を呼び出す理由がわかりません。