問題タブ [backtracking]

すべて同じサイズの文字列のベクトルがあります。
ソリューションとして、いくつかの条件を満たす文字列のリストを作成する必要があります。

擬似コードアルゴリズムは次のようになります。

実際にコードを書く方法に迷いました。

現在のソリューションを保存する方法、関数に渡すパラメータの種類がわかりません...

これは私が持っているものですが、それは完全に間違っていると思います：

}

問題は、ソリューションが制御なしで成長し続けることです。対処方法を教えてください。そして適切なバックトラックを行いますか？

再帰的なバックトラッキングの問題を解決する必要があるというこの問題があります。これはn-queenの問題によく似ていますが、非対称ボードでさまざまな候補を使用する方法が異なります。合計4つの異なる候補があり、それぞれが相互に依存しています。私は2つのエース、2つのキング、2つのクイーン、2つのジャックを持っています。各エースはキングの隣（水平または垂直）である必要があり、各キングはクイーンの隣である必要があり、各クイーンはジャックの隣である必要があり、どのピースもそれらの隣に複製を持つことができます。適切なソリューションを備えたボードは次のようになります。

今、私の問題は、ツリーを使用して、ツリーの親と子として候補を追跡したいということです。私はまだツリーを実装していませんが、この例に示されている方法がからツリーを作成するための良い方法であるかどうか疑問に思いました。そして、これがツリーを作成するための良い方法である場合、どのように開始すればよいですか、ツリーはどのようにして子のどちらの親にすべきかを認識し、ソリューションが適合しない場合に戻ることができますか？

よろしくお願いします。この状況について十分な情報を追加したと思います。

私は数独ソルバーを書いています。プロローグに触れてから長い時間が経ったので、統合、バックトラックなどに関するすべてを覚えているわけではありません。システムを永遠にバックトラックさせたと思います（ただし、スタック例外は発生しません-少なくともすぐに）。これは私がこれまでに持っているものです (パズルはhttp://en.wikipedia.org/wiki/File:Sudoku-by-L2G-20050714.svgにあります):

この行allunique(C1)が問題の原因です。システムは 1 列目の最初の空のボックスに 7 を入れ、それを変更しないようです (少なくとも近い将来には変更しません)。C1 リストの例は次のとおりです[5, 6, 7, 8, 4, 7, 9, 8, 6]。なぜこれが起こっているのか知りたいです。

「dictionary」と呼ばれる一連の文字列が与えられ、単語の辞書を表すフィールドとして格納されます。

String パラメーター ("phrase") を受け取り、指定されたフレーズ内の文字を並べ替えて作成できる辞書セット内のすべての単語を含むセットを返すメソッドを作成します。基本的に私はアナグラムの辞書を検索しています。

これが私のコードです：

したがって、私のアプローチは次のとおりです。 1. 変数「chosen」で表される、このスレッドで渡された可能性について辞書を確認します。

1. 辞書にその可能性が含まれている場合は、呼び出しの最後に返される「アナグラム」と呼ばれるセットに追加します。次に、可能性をもう一度渡し、そこから他の組み合わせを作成しようとします。

3.. 辞書にその可能性が含まれていない場合は、文字列を変更して他の可能性を試し、再帰的にテストします。

上記のコードは「スタック オーバーフロー エラー」を生成します。これは、私の調査によると、無限再帰を行っているか、同じ文字列を何度も何度も無限に渡していることを示しています。しかし、どこでこれを行っているのかわかりません。あなたはできる？

バックトラッキング関数に問題があり、特定のデータでループします。プログラムコード全体をここに書くことはできませんが、関数をここに置くことはできます。

ここに説明があります：

quantity - 値配列内の要素
の数 values -数値の配列
index - 再帰を制御する
変数 moneyA - 配列値の要素の合計を格納する変数half -
再帰が行われた後に moneyA が到達する必要がある数値
配列値を参照します

この関数は、長さの値の配列である要素の数量を取得します。値は、数値を含む配列を最高のものから最低のものに並べ替え、インデックスは再帰を制御し、デフォルトは 0 であるため、最初の要素から開始します。money からの数値を格納する変数値配列と、値配列から合計された数値の半分である半分に達する必要があり、ifChosen は選択された数値を格納します。

関数全体がこれを行い、values 配列の要素を合計し、半分未満の場合は半分に達したかどうかをチェックし、それを moneyA に追加し、ifChosen でマークしてから、合計が半分より大きい場合は次の要素に進みます戻り、ifChosen 配列でマークを外し、moneyA から減算します。常に最高の要素を取得する必要があります。

簡単な例を次に示します。

この結果は次のようになります。

もちろん、この単純な例では素晴らしい仕事をしますが、より多くの数字を持ち、1 つの数字が複数回出現するより複雑な例では、ループして再帰が停止しません。私は実際にこれに1.5週間取り組んでおり、すべての友人に尋ねましたが、何が問題なのか誰も知りません. ナップザックの問題と少し関係があることは知っていますが、まだそれを持っていないので、まだ勉強する必要があります.

役立つ回答をお待ちしております。

句読点で申し訳ありませんが、私は初めてここに来て、フォーマットに慣れていませんでした。

ここに1つの例があります：

今、私はそれが永遠にループすると思うもの: 43 要素:

@Karl Bielefeldtはい、非常に多くの組み合わせがあることを知っているので、速度を上げようとしています。今のところこれですべてですが、特定の入力に対して間違った結果が得られます。誰でもそれを修正できますか?以前よりもはるかに高速に動作しますか?

「Knight's Tour」と呼ばれる、チェス盤のすべての正方形 (サイズは実際には問題ではありませんが、今のところ 6x6 です) を通過するプログラムを作成しようとしています。

ツアーは閉鎖されているはずです。つまり、最後に訪れた広場の騎士は、開始した広場を「攻撃」できます。コードはいくつかの正方形でうまく機能します。たとえば、main の入力 'traverse(1,1,1)' は、彼がトラバースしているだけでなく、バ​​ックトラックしてゴールに向かってトラバースに戻ることを示す出力を生成します。ただし、代わりに「traverse(1,0,0)」を入力すると、StackOverflowErrorが発生します。バックトラックとトラバースが成功することもあるので、コードが機能することはわかっていますが、エラーを取り除く方法がわかりません。私はあまりにも多くの電話をかけていると思いますが、それを回避する方法がわかりません.訪問する広場がたくさんあります:) コードを編集しました。

こんにちは、迷路を生成するプログラムを作成しているので、後でパスをグラフィカル パーツに変換できます。私はそれのほとんどを機能させていますが、東と南のルートをたどることができれば、最後まで行くことができます. 幅を 64 に設定しても、迷路は 64*64 になりますが、これら 2 つのオプションを選択して、毎回最後まで到達することができます。なぜそれがそうしているのか、私には本当にわかりません。コードは以下のとおりです。かなり理解しやすいです。

ご覧のとおり、問題は迷路を生成するポイントにあると思いますが、現在のポイントが最後になるまでそのままにしておくと、すべての迷路がいっぱいになるわけではなく、通常は 1 つの直線的なパスになります。 . 助けてくれてありがとう。

更新: 迷路を生成する for ループを単純な while ループに変更したところ、はるかにうまく機能するようです。for ループが実行されたときは再帰的に実行されなかったようですが、while ループではまったく問題ありません。ただし、すべてのマスが埋まらないようになりました。

迷路を解くためのバックトラッキングアルゴリズムを実装しようとしている部屋検索アルゴリズムを誰かが手伝ってくれるかどうかを探しています。すでに訪れた部屋を覚えておかなければならない場所で立ち往生しています。
迷路は部屋で構成されており、各部屋には北、東、南、西の4つの側面があります。各部屋は、希望する側にドアを作成することで次の部屋にリンクされます。つまり、room1.createNorth(roomName) 北に新しい部屋が作成され、新しい部屋には、私の部屋のクラスでわかるように、最初の部屋にリンクする南のドアがあります。

これが私の刻んだ部屋のクラスで、迷路の中の各部屋を表しています。北側を扱う方法と同じ南、西、東の方向を削除しました。

迷路は次のようになります：http：//i.stack.imgur.com/2KePs.jpgここで、Sは開始点です

私の迷路のクラス

これが私のメインクラスのパブリッククラスですMain{

問題はfindPathTo(roomName)、部屋へのルートを見つける私の方法にあります。部屋D4に入ると、アルゴリズムは「A4」から「B4」の部屋に東に1回だけ移動し、そこで無限にループし、スタックは部屋「B4」だけで大きくなります。たとえば、隣の部屋「B3」や「C4」に進んでみませんか？

編集：ここに作業コードがあります

基本的に、私はこれを持っています：最初に、コードの束は、横断できない迷路を生成します。いくつかのパラメータに基づいて、2D配列の特定のスペースに壁をランダムに設定します。次に、バックトラッキングアルゴリズムを使用して、すべてが通過可能になるまで壁をノックアウトします。問題は、プログラムがスタックに戻っていないように見えることです。

これはかなり標準的なバックトラッキングコードです。アルゴリズムはランダムな場所から始まり、擬似コードで進行します。

move（x、y）{上に移動
でき、まだ行っていない場合：
move（x、y --1）
右に移動でき、まだ行っていない場合：
move（x + 1、y）
。 ..
}

他の方向についても同様です。移動するたびに、ブール値の2つの別々の2D配列（1つは一時的、もう1つは永続的）が座標に設定され、特定の要素にいることを示します。それ以上進むことができなくなると、永続的な2D配列をチェックして、どこにでもあるかどうかを確認します。そうでない場合は、訪問済みスペースと非訪問済みスペースの間にある壁をランダムに選択し（一時的な配列に従って）、それを削除します。このすべてがwhileループで呼び出されるため、迷路のチャンクを通過すると、一時的な2D配列がリセットされ、もう一方は保持され、永続的な2D配列が迷路全体にトラバースされました。moveメソッドのチェックは、永続的な配列ではなく、一時的な2D配列と比較されます。

これはほぼ機能しますが、最終的に生成された迷路の中で到達できない領域をいくつか見つけ続けました。そうでなければ、それは私が望むように迷路を生成するという素晴らしい仕事をしています。問題は、これの理由は、スタックに完全に戻らないことであることがわかりました。

永続的なものではなく一時的な2D配列の完了を確認するように変更すると（したがって、複数の反復にわたって完全な実行を行うのではなく、1回の実行で1回の完全なトラバーサルを実行して、完了をマークします）、継続しますと。私はそれを壊すためにカウンターを設定する必要があります。その結果、非常に多くの壁が削除された「迷路」ができあがります。アルゴリズムがたどるルートを確認すると、アルゴリズムが適切にバックトラックされておらず、スタック内で十分に遠くまで戻っておらず、理由もなく終了したと宣言する前に、単一の要素で数十回の再帰でスタックすることがよくあります。まったく、ゼロの壁を削除する必要があります。

以前のものを2回実行してみましたが、ノックアウトする必要のない壁をノックアウトし続け、迷路をまばらにしすぎています。なぜこれが起こっているのか私にはわかりません。

編集：私がばかである理由については、以下の私の答えを参照してください。これにはまだ答えたいなぞなぞがあります。

私はこれにあまりにも長い間立ち往生してきました。見栄えの良いグリッドで数独ソリューションを印刷しようとしています。

Prolog でパターン マッチングがどのように機能するかの重要な部分を理解していないため、問題が発生していると思います。

さらに苦労せずに、私のコード:

呼び出しは次のとおりです。

出力は次のとおりです。

問題は、true が返されないだけで、 を押す必要が;あり、その後 false が返されることです。これは、私のprettier_print/1ルールが正しく機能していないことを意味します。

私はこれが意味することを理解するのに十分知っていると思います:

Prolog は後戻りして、私のルールの別の解釈を試みています (私の用語を正しく理解していれば、統一できるものが他にないかどうかを調べます)。これはそれと統合する別のものを見つけますが、すぐに失敗します。そうですか？

可能な解釈は1つだけであってほしい。それを意味するように関数を修正するにはどうすればよいですか?

助けてくれてありがとう、これは私がそのようなばかのように感じています!