問題タブ [recursive-backtracking]

現在、ペグ ソリティアのゲームを解決するための再帰アルゴリズムをプログラミングしています。

アルゴリズムは、ボードを解決するために「バックトラッキング」アプローチを使用する必要があります。私は正しい解決策に非常に近いものを得ることができたと思います。私のコードは、解決可能なすべてのボードのボードを正しく解決しているようです。また、ボードが解決できない場合も正しく判断しているようですが、ペグの数が多すぎない場合に限られます。

私の再帰的な方法は次のようになります。

ボードは標準的なペグ ソリティア ボードです。私の isSolved() メソッドが、ボードが解決されたかどうかを正しく判断していると確信しています。私の makeMove 関数は、行、列、方向 (i、j、k) を取ります。それらの座標でペグを見つけ、要求された方向にペグを移動できるかどうかを確認します。可能であれば、移動を行い、その移動を移動の配列に追加して、true を返します。そうでない場合は false を返します。

私の元に戻すメソッドは、最後の移動を配列からポップし、ボードを以前のレイアウト (ポップされた移動が行われる前) に戻します。

約 25 個以上のペグを持つランダム ボードの場合、プログラムは単純に終了しないようです。無期限に処理を続けます。解決可能なボードと、ペグの少ないさまざまな解決不可能なボードは、正しい結果で一貫して 10 秒以内に終了するようです。

何か案は？

状態空間グラフの深さ優先反復深化検索を実装しようとしています。3 つの頂点を持つグラフがあり、それらは 2 つの活性化エッジと 2 つの抑制エッジです。各ノードにはバイナリ値があり、集合的にこれがグラフの状態です。グラフは、ノードの 1 つがしきい値を超えているか、しきい値を下回っているか (すべての受信ノードの合計から計算) を確認することで、新しい状態に遷移できます。各遷移で最大 1 つのノードが変更されます。それらは 3 つのノードであるため、状態遷移グラフ内の各状態を離れる 3 つの状態遷移エッジがあります。

たとえば、次のクエリを実行できます。

そして、それは私に3つの正しい答えを与えます:

Bratkos Prolog for AI book で与えられた述語 id_path を使用しようとしていますが、質問 11.3 の解決策ですが、使用/適応に問題があります。 ループに入らずに、開始ノードから他のノードへのパスを作成したい - 繰り返し要素を持たせたり、パスが存在しないときに立ち往生したりしたくない. 開始状態と、開始状態からアクセスできる一連の状態を示すパスが必要です。自己ループがある場合は、そこに到達するすべての方法でこれを 1 回含める必要があります。つまり、状態空間に到達した方法を追跡し、状態空間がパスで一意であるだけでなく、これを一意にしたいのです。

たとえば、011 から、長さ 1 の 3 つのパスすべてが円弧で見つかるようにします。

次のレベルでは、ノードに到達するために必要な 2 つのアークを示す 3 つのノードを持つすべてのパスが表示され、次のレベルでは、必要な 3 つのアークを示す 4 つのノードを持つすべてのパスが表示されます。

これが役立つ場合、コードを SWISH に入れましたか? （初めてみる？！）

http://pengines.swi-prolog.org/apps/swish/p/HxBzEwLb.pl#&togetherjs=xydMBkFjQR

タスクの完了に非常に近づいていますが、findChange()正しく呼び出す方法がわかりません。私の推測では、それはメインメソッドにある必要があります。しかし、findChange(); の場合。それを呼び出すと、int, List<Integer>, List<Integer>いわば「正しく」これを行うにはどうすればよいかを尋ねられます。

コード

このプログラムは、特定の金額、つまり 143 ($1.43) の変化を示すさまざまな方法をすべて計算します。私がしなければならないのはfindChange()、メインを呼び出すことだけです。それは機能するはずです。何が欠けていますか?

EDITメソッド呼び出しを指定していないことに気づきました。助けが必要です。不明な点がありましたらお詫び申し上げます

入力ファイル

電流出力

欲しいです

私のプログラムの目的は、可能なすべての変更ソリューションを特定の金額に出力することです。たとえば、

望ましい出力

(with 9 = $0.09) ただし、出力は少し異なります。出力は次のようになります。

私の出力

ご覧のとおり、文字通りすべての可能な解決策を提供してくれます。私は上位2つの答えだけを気にします。より多くの金額が要求された場合、これが大きな問題になることは明らかです。ここに私の質問があります:私のコードに基づいて、それぞれ1つの組み合わせのみを表示するように修正するにはどうすればよいですか?

コード

すべての回答に感謝します。他の間違いを見逃すようにしてください。最初にこの質問に対処したいと思います。ありがとう！！

私は現在、ユーザーが単語を入力するプログラミングの割り当てに取り組んでいます

つまり「あれ」

プログラムは、指定された文字列から作成できるすべての有効な単語を返す必要があります

すなわち[それ、帽子、で]

私が抱えている問題は、プレフィックスが有効かどうかを確認する再帰的な方法を使用して、結果の単語を作成する必要があることです。

つまり、指定された単語が「kevin」の場合、プログラムが「kv」の組み合わせを試行すると、kv で始まる単語がないことを認識し、時間を節約するために次の組み合わせを試行します。

現在、私のコードはすべての順列を作成するだけで、入力が8文字を超えると比較的時間がかかります。

誰かがこれを理解するのを手伝ってくれるなら、私は大歓迎です。また、AVL ツリーを使用して、必要な場合に備えて検証用の辞書の単語を保存しています。

最近、C++ で数独ソルバーを作成しました。バックトラッキング アルゴリズムを使用して解決しましたが、問題があります。場合によっては、5 行目までしか解決できません。

作業ケース : [6][6] = 2、[4][5] = 1

行 5 の後に失敗するケース: [1][1] = 1

一部のケースでスドコを部分的に解決している理由がわかりませんが、そのケースには解決策があります

宿題の一環として、指定された配列に「適切な」サブグループが存在する場合に true を返す関数を作成する必要があります。「適切なサブグループ」とは、各グループ メンバーの特定のフィールド (整数) の合計が、指定されたターゲット (具体的には、配列の元の長さの半分) よりも大きいサブグループであり、各メンバーのグループは、グループの他のすべてのメンバーと「仲良く」しています。2人のメンバーが「仲良し」の場合(abs(m1->f1 - m2->f1) + abs(m1->f2 - m2-f2)) <= given_hatred。これは私がこれまでに試したことですが、うまくいかないようです：

また、 Member は、 で始まるすべての関数を実装する抽象データ型であり、正常member....に動作する (テスト済み) ことにも言及します。

編集： すぐに投稿する回避策を見つけましたが、他の解決策に非常に興味があるので、お気軽に:)

単純な六方格子の有限領域にすべての閉曲線を生成しようとしています。これはあまり重要ではありません。互いに 1 の距離だけ離れた点の有限集合です。しかし、私のコードはしばらく閉じた曲線を生成し、その後私のプログラムは動作を停止し、無限ループに陥りますか? コマンドでJavaにガベージコレクションを強制しようとしましたが、同じコードが異なるポイントで停止します。私の知る限り、止まる場所はランダムです。Sphere は、検討中の領域内のすべての点を格納する配列です