問題タブ [backtracking]

バックトラッキングでのナイトツアーの問題を解決するには、SML コードを作成する必要があります。チェス ナイトはチェス盤 (サイズ: ) のいたるところを走らなければNxNならず、各マスを 1 回だけ訪れなければなりません (最後に最初のマスに戻る必要はありません)。

空のボードを作成する関数、ボード内の正方形を設定または取得する関数、騎士の次の動きのリストを取得する関数はすべて既に作成しています。しかし、再帰関数を SML で記述する方法がわかりません (このアルゴリズムを C で記述する方法は知っていますが、SML では記述できません)。

8x8 チェス盤の C のアルゴリズム

セットは以下のこのメソッドに渡され、バーの長さも渡されます。セットからの特定の数値がバーの長さから削除された場合、ソリューションはセットから最小量の無駄を与える数値を出力する必要があります。したがって、バーの長さは 10、セットには 6、1、4 が含まれているため、解は 6 と 4 であり、無駄は 0 です。セットをバックトラックする条件に問題があります。また、無駄な「グローバル」変数を使用してバックトラッキングの側面を支援しようとしましたが、役に立ちませんでした。

SetInt は手動で作成されたセットの実装であり、追加、削除、セットが空かどうかのチェック、およびセットから最小値を返すことができます。

皆さん、最近私のアルゴリズムの問​​題について投稿しました。

最小量の廃棄物を与える集合から数を見つける

コードを少し修正したので、ある程度バックトラックするようになりましたが、出力にはまだ欠陥があります。私はこれをかなりデバッグして、すべての変数値をチェックしましたが、問題を見つけられないようです。

ここでも、完全な解決策ではなく、アドバイスが非常に役立ちます。私のコードにはいくつかの問題があるだけだと思いますが、どこにあるのかわかりません。

//前回の投稿より:

基本的に、セットは以下のこのメソッドに渡され、バーの長さも渡されます。ソリューションは、セットからの特定の数値がバーの長さから削除された場合に最小量の無駄を与えるセットからの数値を出力する必要があります。したがって、バーの長さは 10、セットには 6、1、4 が含まれているため、解は 6 と 4 であり、無駄は 0 です。セットをバックトラックする条件に問題があります。また、無駄な「グローバル」変数を使用してバックトラッキングの側面を支援しようとしましたが、役に立ちませんでした。

SetInt は手動で作成されたセットの実装であり、追加、削除、セットが空かどうかのチェック、およびセットから最小値を返すことができます。

ねえ、私は正の数の配列をk個の部分に分割して、各部分が（ほぼ）同じ合計になるようにするアルゴリズムを見つけるための助けを探しています...

1,2,3,4,5,6,7,8,9 en k = 3アルゴリズムは、この1,2,3,4,5 | 6,7|8,9の順序で分割する必要があります。要素を変更することはできません...欲張りアルゴリズムを見つけるのは簡単ですが、常に最適なソリューションを返すバックトラックバージョンを探しています...

誰もが何かヒントを得ましたか？

次のような 2 次元配列があります。

横方向または下方向に連続する 1 の最長のチェーンを特定する方法を見つけようとしています。この場合、列 4、行 2 から始まり、その長さは 4 で下に向かっています。

再帰を使用することを考えていましたが、特に 0 に遭遇したときに、位置を追跡する際に問題が発生しています。

これまでのところ、私はこれに沿ったものを持っています（全体をチェックするためだけに）：

ここG[][]で、 は 1 と 0 を含む 2 次元配列n、 は行/列のi数、 は行番号、jは列番号です。

事前にご協力いただきありがとうございます。

ここでなぜUnmark vertex v必要なのですか？そして、なぜvが再び到達できなくなるような行を追加しても安全なのですか？それは再訪につながるのでしょうか？

関数を逆アセンブルすると、gdbはメモリアドレスを基数16で表示しますが、オフセットは基数10で表示します。

例：

関数オフセットは<+N>アドレスの隣にあり、ご覧のとおり、10進数になっています。

Linuxカーネルがクラッシュすると、ベース16を使用してバックトレースが表示されます。

目的の命令を見つけるために、バックトレースアドレスを基数16から基数10に変換する必要があるのは非常に面倒です。

gdbにベース16オフセットで逆アセンブル出力を表示するように指示できますか？

バックトラッキングを介して n を合計するすべての整数部分集合を見つけたい

たとえば、整数の場合:

n = 7

出力したい

引数として評価している整数配列内の位置を渡す必要があると思いますが、残りのロジックを書くのに行き詰まっています。

これまでの私のコード:

再帰的なバックトラッキングが必要な問題を解決しようとしていますが、私のソリューションではスタックオーバーフロー エラーが発生します。このエラーは多くの場合、不適切な終了条件を示していることは理解していますが、私の終了条件は正しいようです。スタックオーバーフローエラーを引き起こす可能性がある悪い終了条件以外に何かありますか? 問題が何であるかをどのように把握できますか？

編集:申し訳ありませんが、コードを投稿しようとしましたが、あまりにも醜い..

ラスベガスのアルゴリズムを使用して、ボード上でランダムなクイーン ポジションを生成しています。複数回実行してタイミングを計りたいのですがSystem.exit(0)、停止しない場合、解決策が見つかったときにバックトラックを停止するために使用しています。私のアルゴリズムは、私が望まない他の解決策を提供します。

ここ：

System.exit(0)ループ内で複数回呼び出すことができるように、それを変更してアルゴリズムを停止させるにはどうすればよいですか?