問題タブ [backtracking]

バックトラッキングアルゴリズムの計算コストに重みの順序はどのように影響しますか? ノード数と探索木の数は同じだけど、無秩序だともっと時間がかかるので何とかしている。

ありがとう！

Java で 9x9 グリッドの数独ソルバーをプログラミングしています。

次の方法があります。

• グリッドの印刷

• 指定された値でボードを初期化する

• 競合のテスト (同じ番号が同じ行または 3x3 サブグリッドにある場合)

• 数字を 1 つずつ配置する方法で、最も手間がかかります。

その方法について詳しく説明する前に、再帰とバックトラッキングを使用して解決する必要があることを覚えておいてください (例として、こちらのアプレットをご覧ください http://www.heimetli.ch/ffh/simplifiedsudoku.html ) 。

また、私はこの数独を、左上から始めて最初の列、次に 2 番目の列など、垂直に下に移動して解決しています。

これまでのところ、私は次のものを持っています：

BACKTRACKING とラベルを付けた場所は、コードの残りの部分を移動する必要があると思われる場所です。

私は次の行に沿って何かを考え出しました：

• 値が 10 の場合、その値を 0 に戻し、行を戻し、その値を 1 増やします

その後戻りの「戦略」は、いくつかの理由で正確には機能しません。

1. 前の行が指定された値だった場合 (つまり、インクリメントしたり触れたりすることは想定されていませんが、代わりに、そこに配置した最後の値に戻ります)

2. 前の値が 9 だった場合はどうなるでしょうか。それを 1 増やしたら、今度は 10 になり、うまくいきません。

誰かが私を助けてくれますか？

要素数と組み合わせのサイズを指定して、可能なすべての順序付けられていない n-タプルまたは組み合わせを生成するクラスを実装しようとしています。

言い換えれば、これを呼び出すとき：

print() は、コンストラクターで設定されたコールバック関数です。出力は次のようになります。

これは私がこれまでに持っているものです:

これは再帰関数の実装です。Start() は単なるキック スタート関数であり、よりクリーンなインターフェイスを備えています。add_element(0) のみを呼び出します。

一定の N サイズの可能なすべての組み合わせを生成したい場合、サイズ 3 の組み合わせを次のように言うことができます。

N が定数でない場合、それぞれの for ループを独自のフレームで実行することにより、上記の関数を模倣する再帰関数が必要です。for ループが終了すると、プログラムは前のフレームに戻ります。つまり、バックトラックです。

私は常に再帰に問題を抱えていましたが、今ではそれをバックトラッキングと組み合わせて、可能なすべての組み合わせを生成する必要があります。私が間違っていることの指針はありますか？私は何をすべきか、または見落としていますか？

PS: これは、順序付けられた n タプルに対して基本的に同じことを行うことも含む大学の課題です。

前もって感謝します！

/////////////////////////////////////////////// /////////////////////////////////////

他の誰かが同じことを疑問に思っている場合に備えて、正しいコードをフォローアップしたかっただけです。

順序付けられた n タプルの場合は、次のようになります。

丁寧な回答をありがとう、ジェイソン！

与えられたリストのすべてのサブリストを整数で出力したいこの関数を書いています。これらの整数の合計は、指定された数に等しくなければなりませんn。i値0で始まるヘルプ変数もあります。リストと各サブリストはどちらもArrayListです。したがって、メソッドは現在次のようになります。

もちろん、私はすでにメソッドを持っていますsum()。メソッドはこれを実行します。とするnumbers = [1, 3 , 4]とn == 4、メソッドは[4]and[1 ,3]を出力する必要がありますが、出力するのは[1, 3]？forループはそのトリックを正しく実行する必要があると思いますか？誰かが私を正しい軌道に乗せてくれれば幸いです。

更新：メソッドに与える値：

更新2：

再帰的にしたいと言うのを忘れました:)

地域のプログラミング コンテストのプログラミング問題を復習しています。

問題はこちら（pdf）からダウンロードできます。オランダ語ですが、写真がわかりやすいです。

入力として am*m グリッドを受け取りますが、いくつかのパイプといくつかの欠けているスポット (疑問符) があります。残りのパイプはグリッドに配置して、他のパイプと接続する必要があります。

各パイプは文字として表されます (2 ページの図を参照)。文字「A」の値は 1、「B」の値は 2、..

バックトラックで解決しようとしました（まだうまくいきません）。しかし、グリッドは 10x10 になる可能性があるため、これは遅すぎます。誰かがより良い（より速い）ソリューション/アプローチを提案できますか?

問題は、隣接する頂点が同じ色を持つことができないように、最小数の色で特定のグラフを色付けするために再帰を使用することです。その繰り返しと接頭辞は、各ノードの色で構成される文字列です (例: 3 つのノードがあり、ノード 0 は色 0 で色付けされ、ノード 1 は色 1 で色付けされ、ノード 2 は色 2 で色付けされます。次に、接頭辞012 になります）。すべてのノードが色付けされている場合、この関数は文字列プレフィックスを返します。最初の呼び出しは、パラメーター (0,"") を使用して行われます。これは、0 色で色付けしようとすることを意味します。これが私が書いたコードです。正常に動作し、34 個未満のノードでは正しい答えを返しますが、34 個を超えると、関数はメインに戻りません。コードを改善するためのアイデアをいただければ幸いです。さらに情報が必要な場合はお知らせください。

T(x,y) を次のような X × Y グリッド上のツアーの数とします。

1. ツアーは左上の四角から始まります
2. ツアーは、1 マス上、下、左、または右の移動で構成されます。
3. ツアーは各広場を 1 回だけ訪れます。
4. ツアーは左下の四角で終了します。

たとえば、T(2,2) = 1、T(3,3) = 2、T(4,3) = 0、T(3,4) = 4 は簡単にわかります。 T(10,4) を計算します。

• 私はこれに何時間も取り組んできました...グリッドの寸法を入力として取り、可能なツアーの数を返すプログラムが必要ですか? これを解決するにはどうすればよいですか？

T（x、y）を、次のようなX×Yグリッド上のツアーの数とします。

1. ツアーは左上の広場から始まります
2. ツアーは、1マス上、下、左、または右の動きで構成されます
3. ツアーは各広場を1回だけ訪問し、
4. ツアーは左下の四角で終わります。

たとえば、T（2,2）= 1、T（3,3）= 2、T（4,3）= 0、およびT（3,4）=4であることが簡単にわかります。 T（10,4）を計算します。

私はこれに何時間も取り組んできました...グリッドの寸法を入力として受け取り、可能なツアーの数を返すプログラムが必要ですか？

私はこれに何時間も取り組んできました...グリッドの寸法を入力として受け取り、可能なツアーの数を返すプログラムが必要ですか？

私は問題を解決するためにこのコードを書きました...私はすべての方向をチェックする方法を理解できないようです。

@KarolyHorvathによるアルゴリズムグリッド上のセルの状態（訪問済み/未訪問）を表すために、いくつかのデータ構造が必要です。

あなたのアルゴリズム：

step（0、0、sizex * sizey）で実行します

特定の単語がアルファベットの 2-D マトリックスに存在するかどうかを調べるためにバックトラッキングを使用できると聞いたことがありますが、それを実装する方法がわかりません。たとえば、次のような行列がある場合:

ルールは、任意の位置から水平、垂直、斜めに移動できるというもので、上記の行列に単語 "GONE" が含まれているかどうかを判断する必要があります。ここで、最初にすべての G の位置を保存し (>1 G が存在する場合)、その位置のそれぞれからチェックを開始できますが、バックトラッキングを使用してチェックするにはどうすればよいでしょうか? ありがとう。

ユーザーがアプリケーションの使用を開始した時点から、Android アプリケーションの使用状況に関する完全な情報を追跡したい。

ユーザーが行ったすべてのアクティビティと、ユーザーが入力したデータも追跡したいと思います。これらのデータをスクリーンショットなどとしてサーバーに送信したいと考えています。

私の目的は、これらすべてを追跡してサーバーに送信する方法を見つけることです..

Plsはいくつかの実装のアイデアを提案します

前もって感謝します