問題タブ [backtracking]

List トランスフォーマーをどのように使用すればよいか、私にはよくわかりませんListT。たとえば、この単純なタスクをどのように実行する必要がありますか:

そして、関数の型は何であるべきですか?

ListTこれは私が達成しようとしているタスクではありません (他の多くの方法を使用してこの問題を解決する方法を知っています) 。そのようなタスクを達成するために使用する方法を知りたいだけです。

数独バックトラッキングソルバーを書いていますが、行き詰まっていて、理由がわかりません。私の再帰呼び出しは大丈夫だと思います。私が欠けているものは何ですか？

入力は、1行のグリッド初期レイアウトでinput.txtファイルから読み取られます。

input.txt：

編集：グリッドの解決を完了していないとして「スタック」を意味します

これはサンプル出力です：

プログラム：

バックトラッキングを使用してナイツ ツアーの問題を解決するアルゴリズムを JavaScript で記述しようとしていますが、うまくいきません。基本的に、この関数は、各移動の場所を含むVisitedという配列を出力することになっています。ただし、配列には位置が追加されず、[[0,0]] のままです。これが私のコードです。どんな手掛かり？

ありがとうございました。

スタック (プッシュとポップを使用) のおかげで、ツリーでバックトラッキング アルゴリズムを使用しています。動作しますが、問題があります。スタックによって指定されたパスは「間違っています」。

たとえば、次のようなツリーがあります。

たとえば、C のパスが必要な場合、この関数は RAB を返します (B ではなく R と A でOK)。

この関数によるものなのか、push() 関数によるものなのかはわかりません。関数にエラーが表示されない場合は、push() を貼り付けますが、かなり長いです。

編集：私は今、よりよく理解しています。関数に追加しました：
ノードがリーフの場合、pop（）。F を検索すると、RB F ではなく RABF が返されます。A をスタックに保持しないようにする方法がわかりません。

edit2 :

コードは次のとおりです: (RBF の代わりに RABF を返します)

if (Prefix(root->left, tas, search)) にelseを追加して、トラバースする子ノードをポップして良い結果を得る方法がわかりません。誰にもアイデアがありますか？

ありがとう ！

この再帰的なバックトラッキングの問題に問題があります。

「整数のリストをパラメーターとして受け取り、再帰的なバックトラッキングを使用して、リストを等しい合計の2つのサブリストに分割できるかどうかを検出するパーティション化可能なメソッドを記述します。指定されたリストを均等に分割できる場合、メソッドはtrueを返す必要があります。そうでない場合はfalse。」

たとえば、リスト[1、2、3]をサブリスト[1、2]、および[3]に分割できるため、「true」の結果が生成されます。

私の解決策は正しいようですが、何があってもfalseを返します。理由がわかりません。

編集：list1から要素を2回削除する問題を修正しました。

ヒットとトライアルの方法で変更し、評価し、要件を満たしていない場合は値を再割り当てする必要があるマトリックスがあります。私はこれを連鎖仮定の再帰関数で行っています。これは、複数のコピーを作成せずに実行できますか？

バックトラック中にマトリックスを復元できますか？

この質問はインタビューで尋ねられ、再帰/バックトラックを扱っています。ブール値の2つの配列があるとします：bool* sourceそしてbool* target、それぞれが同じ長さですn（source / target / nは引数として与えられます）。質問の目的は、操作スイッチを使用するように変換sourceすることです。target

• 複数のトランスフォーンがある場合：それらのいずれかを提示します
• 解決策がない場合：解決策がないことを主張する

定義：操作switch(int i, bool* arr)は、arr[i]とarr[i-1]およびarr[i + 1]の値を反転します（これらのインデックスが0 ... n-1の範囲にある場合）。

言い換えると、操作は通常3ビット（ iswitchとその隣接ビット）を反転しますが、最後は2ビットだけです。

例えば：

• switch（0、arr）は、arr[0]とarr[1]の値のみを切り替えます
• switch（n-1、arr）は、arr[n-1]とarr[n-2]の値のみを切り替えます

アルゴリズムについての提案を事前に感謝します。

私は現在バックトラッキングを学んでいて、8 クイーンの問題に行き詰まりました。私は 8x8 マトリックスを使用していますが、関数に渡すマトリックスに関していくつかの問題があると思います。誰でもコードに最適化をもたらすでしょう、ありがとう。

これが私のコードです。

Java の正規表現エンジンがこの正規表現で壊滅的なバックトラッキング モードになる理由を誰か説明できますか? 私が知る限り、すべての交替は他のすべての交替と相互に排他的です。

文章：'pão de açúcar itaucard mastercard platinum SUSTENTABILIDADE])

一部の代替に所有格一致を追加すると問題が解決しますが、その理由はわかりません.Javaの正規表現ライブラリは、相互に排他的なブランチでバックトラックするには非常にバグが多いに違いありません。