問題タブ [backtracking]

次の配列があります。

この配列は、2 点間の接続がどこにあるかを記述します。たとえば、1 から 7 には 1->2->7 という方法があります。

JavaScript では、たとえば 1 から 9 までの最短経路をどのように生成できますか?

更新しました

これは私が今まで行ったことです。私の質問は、どうすればパスを保存できますか?

backtrackingを使用して問題 (例: N-Queen) を解決しているとします。すべてではなく、1 つだけ (1 番目) のソリューションを見つけたい場合はどうすればよいでしょうか。

私はそれを命令的に行うことができると思います（たとえば、可変ブール値フラグを使用して）。どうすれば機能的にできるのだろうか。

チェス盤のすべてのマスにナイトを 1 回だけ移動させるコードを作成しました。この (以下の) コードの問題は、7x7 までは機能し、8x8 以降は何もしないことです。コードはこちら chessBoardSize はサイズを定義します(8=> 8x8)

最初の可能なソリューションのみを返す数独ソルバーを作成しようとしています。void メソッドを使用してすべての可能なソリューションを印刷することができましたが、最初の検索で停止することはできません。

trueブール値のメソッドに切り替えてツリーに戻ることが望ましい方法であることはわかっていますが、それを記述する正しい方法が見つかりません。

とにかく私が試した方法では、常にコンパイルエラーが発生します（method must return boolean）。

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

だから私はcsの学生であり、無向の重み付けされていない（リフトなし）グラフの隣接行列を取得し、そのグラフの完全一致の数を返すc（ループなし再帰のみ）でバックトラッキングプログラムを構築するように依頼されましたそれ以外の場合はゼロ。pfaffian方向を使用するfktアルゴリズムを使用することを考えましたが、これまでのところ、その方法がわかりません。あなたがとても親切で、この質問を正しい本や正しい見方に導いてくれるなら、私はとても感謝しています。私がバックトラックを試みたのは初めてであり、そのようなことをどのように実装するかについてのいくつかの基本的な概念が欠けていると思います。

どうしたの？
私はPrologでいくつかの本当に奇妙な問題を抱えています。
特定のインデックスでリスト内の要素を置き換える再帰ルールが常に機能するとは限りません。
私のルールは次のようになります。

プログラム内からデバッガーを使用すると、インデックスが何であっても常に2番目のルールが呼び出されますが、プログラムの外部でまったく同じコマンドを実行すると、完全に機能します。インデックス1に到達しますが、2番目のルールを呼び出し、最初のルールをバックトラックして試行せず、最後まで失敗します...

replaceAtIndexを呼び出すルールは次のようになります。

インデックスを111として呼び出しをデバッグしているとき。定数111に
置き換えているときは、機能します。_index_in_list

なぜそれが起こるのか、誰かが手がかりを持っているかもしれませんか？

だから私はこのフォーマットのテキストファイルからロードされたCの不等式パズルを解くはずのこのプログラムを持っています：

ここで、5は行列のサイズであり、演算子に隣接する数値、、、は、それら<によって>課せられる条件を満たす必要があります。ファイルから、行のすべての文字がスペースで分割されます。ファイル、それが数学演算子の条件を満たしているかどうかを確認するために、しかし私は再帰関数で立ち往生しています^v0 |

私が知りたいこと：

行列を格納する正しい方法を選択しましたか、それとも論理演算子から数値を除算する必要がありましたか？

マトリックスに対して再帰的な展開を実行するにはどうすればよいですか？また、特定のステップで使用された数を追跡するにはどうすればよいですか（バックトラックする必要がある場合）？

例えば。index[j][j]（行列のサイズ）の場所に到達したとしましょう。j<nそこから始めて、数値のみをデクリメントj（「タッチ」）して、部分行列が条件を満たすかどうかを確認する必要があります。

これが私がこれまでにコーディングできたものです。

どこ ：

char **readmat(int *n); //ファイルから行列を読み取り、文字間のスペースを削除します

void print(char **mat,int n);//保存された行列を出力します

int check(char **mat,int n); //サイズnの行列の項目が数学演算子を満たすかどうかをチェックします

int expand (char **mat,int n,int i);//これは、一度に要素を取得し、満たす必要のある条件があるかどうかをチェックする再帰関数である必要があります。満たす必要がある場合は、それをインクリメントします

例の解決策：論理条件領域が明確に満たされていることがわかります。

コードを投稿する場合よりもおそらく短いので、これを簡単な言葉で説明しようと思います。私は、正しい「移動順序」を選択してゲームを完了する必要がある再帰的なソリューションの一部を作成しました。それが行き詰まりに陥った場合、バックトラックする必要があります。私の現在のシステムは、新しいパス/移動順序が見つかるまで、バックトラック中に再度使用できないように、機能していない移動に識別子を設定することで機能します。

しかし、問題が発生しました。ゲームは、残りの手が 2 つしかなく、どちらもゲームを解決できない状態に達する可能性があります。私の現在のシステムは基本的に、これら 2 つの動きを継続的に交換します。これは、ソリューションが動きを試み、それが機能しないことを確認してから、次の動きを試みるためです。私の問題は、移動が行われるたびにソリューションに移動を使用しないように指示する識別子をリセットすることだと思いますが、他にどのように設定するかわかりません。

さらに情報が必要な場合、または洞察が必要な場合はお知らせください。ありがとう！

グローバル変数と C のバリエーションのいくつかのメソッド宣言を処理する文法があるとします。

次のようなものを与えると：

文法は int MAX を読み取ります。正しく、しかし、宣言ルールを2行目にも適用したいのですが、(に達すると失敗します。この時点で、バックトラックして次のルールである手続き用のルールを適用することを期待しています。誰か教えてください。なぜこれが起こっていないのですか？

n と k の 2 つの int を受け取るアルゴリズムを実装しようとしています。ここで、n は列の座席数、k はその列に座ろうとする学生の数です。問題は、各生徒が両側で少なくとも2席離れている必要があるということです。私が持っているのは、すべてのサブセット (0 または 1 の配列、1 は誰かがそこに座っていることを意味する) を生成する関数であり、これを関数に送信して、有効なサブセットであるかどうかを確認します。これは私がその機能のために持っているコードです

コードは k と n の小さな入力に対して機能しますが、より高い値を取得すると、何らかの理由でインデックスからリストエラーが発生します。
どんな助けにも感謝します。

O 入力 a は、次のようなリストです

編集：

プロセスを呼び出すコード:

これらの数値を使用すると発生するエラーは次のとおりです。