問題タブ [backtracking]

プログラムを終了せずに最初の解決策を見つけた後、バックトラッキングアルゴリズムを停止する方法はC / C ++にありますか？

関数がすぐに関数を終了するようにしたいのですが、すべてのレベルの再帰を1つずつ終了してリターンを示すのではありません。

深さ優先検索に関するウィキペディア:

深さ優先検索 (DFS) は、ツリー、ツリー構造、またはグラフをトラバースまたは検索するためのアルゴリズムです。1 つはルート (グラフの場合はルートとしていくつかのノードを選択) から開始し、バックトラックする前に各ブランチに沿って可能な限り探索し ます。

幅優先探索とは

「開始ノードを選択し、すべてのノードのバックトラックをチェックし、最短パスを選択し、隣接ノードのバックトラックを選択し、最短パスを選択し、連続的なバックトラックにより各パスをトラバースするため、最終的に最適なパスを見つけるアルゴリズム。

Regexfindのプルーニング -- バックトラッキング?

バックトラッキングという用語は、そのさまざまな用途のために混乱を招きます。UNIX のfindSO ユーザーの剪定は、バックトラッキングで説明されました。Regex Buddy は、正規表現の範囲を制限しない場合、「壊滅的なバックトラッキング」という用語を使用します。あまりにも広く使われている包括的な用語のようです。そう：

1. グラフ理論で特に「バックトラッキング」をどのように定義しますか?
2. 幅優先検索と深さ優先検索の「バックトラック」とは何ですか?

[追加した]

バックトラックに関する適切な定義と例

1. ブルートフォース法
2. ストールマン (?) が発明した用語「依存性指向のバックトラッキング」
3. バックトラッキングと正規表現の例
4. 深さ優先検索の定義。

SWI-Prologには、常に失敗し、マシンがバックトラックするのを防ぐ組み込みの述語がありますか？プログラムの実行をすぐに停止します（これは何をfail/0しませんか）？カットは使えますが、好きではありません。

そのようなこと!, failをすることは私にとって問題ではありませんが、私が望むことを達成するために、私はより多くの場所でカットを使用する必要があり、これは私が好きではないことです。

だから私は一日中この課題を解決しようとしてきましたが、それを得ることができません.

次の関数は 2 つの文字列を受け入れます。2 番目 (1 番目ではない) には*'s (アスタリスク) が含まれる可能性があります。
An*は文字列 (空、1 文字以上) の置換であり、(s2 でのみ) 1 回、2 回、それ以上、またはまったく出現しない可能性があります。別の*( ab**c) に隣接することはできません。それを確認する必要はありません。

文字列が同じパターンの場合、true を返します。再帰的
で なければならず、ループ、静的およびグローバル変数を使用しないでください。ローカル変数とメソッドのオーバーロードを使用できます。

次のメソッドのみを使用できます: charAt(i)、substring(i)、substring(i, j)、length()。

例:

1: TheExamIsEasy; 2: The*xamIs*y→ 真
1: TheExamIsEasy; 2: Th*mIsEasy*→ 真
1: TheExamIsEasy; 2: *→ 真
1: TheExamIsEasy; 2: TheExamIsEasy→ 真
1: TheExamIsEasy; 2: The*IsHard→ 偽

アスタリスクが検出されるまで、文字を 1 つずつ比較してみました。次に、連続する char ( ) をat positionの文字とcharAt比較して、アスタリスクが空のものかどうかを確認します。のカウンターとして; false の場合 --両方のカウンタとして再帰を続行します。 別のアスタリスクが見つかるか、文字列の終わりまでこれを続けます。i+1s1ii+1s2is1
i+1

わからない、私の脳は物事を見失い、集中できない、何か指針/ヒントはありますか？私は正しい方向にいますか？

また、これを解決するためにバックトラッキング技術が使用されると言われています。

これまでの私のコード（理論的にも仕事をしていません）：

私の問題の抽象化は、デカルト平面にはたくさんの長方形があるということです。これらの長方形は既知の整数サイズを持ち、横座標 (水平座標) が既知で固定されている整数座標を持っている必要があります。縦座標 (垂直座標) のみが異なる場合があります。

問題は、指定されたすべての長方形を含む最小の長方形が最小である縦座標を見つけることです。これは、小さな長方形の横座標が固定されているため、幅が固定されているため、最小の高さを持つ必要があることを意味します。

バックトラッキングを使用する必要があるかどうか、またはより高速な方法があるかどうかはわかりません.50個の長方形では、正しい解を計算するのにかなりの時間がかかり、貪欲なアルゴリズムはうまくいきません。

編集：申し訳ありませんが、私は十分に明確ではなかったことに気づきました。最初にこの質問をしたとき、私はカレンダー アプリケーションを作成していました。マネージャーは、チームのイベントを次のように入力します。

• イベントAは午後2時から。午後4時に終了します。
• イベントBは17時から。午後6時に終了します。
• イベントCは16時から。午後6時に終了します。
• イベントDは午後2時から。午後3時に終了します。
• イベントEは午後3時から。午後5時に終了します。

これらのイベントをタイムラインに表示したいのですが、オーバーラップせずに画面の占有面積をできるだけ小さくしたいと考えています (マネージャーは各イベントをその四角形で表示し、その四角形で説明を表示したいため)。

上記の例の最適な配置は次のとおりです。

A と C は直線上にあり、D、E、B は別の直線上にあります。貪欲なアプローチでは、A と B を同じ行に配置し、C と D を別の行に配置し、E を 3 行目に配置します。

文字列の代わりに私が書いたいくつかのクラスを使用しているため、実際の問題は少し複雑ですが、次のように想像できます。700の3文字の単語のリストがある場合、どのようにしてすべての組み合わせを見つけることができますか？これらの単語の5つを最初と最後の文字でリンクすることで形成できます。つまり、CAT TOW WAR RAD DOGは成功しますが、CAT TOW WARRAGGODも成功します。

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

しかし、これは生産するゴミを追加し続けるだけです。私は再帰的なバックトラックがひどいので、この例を機能させることができれば、最終的にこの概念を理解できると思います。賢い人を助けてください！

この質問の目的のために一般的に作成された例として、私の意図は、ある数aの 、次に同じ数bの 、さらにもう 1 つの に一致させることbです。

このスニペットに示されている 2 つのパターンを調べます (これも ideone.com にあります)。

2 つのパターンの一致には違いがあることに注意してください。r1は、バランシング グループ コンストラクトで貪欲な繰り返しを使用し、3aと 3に一致しますbが、これは意図したとおりではありません。r2しぶしぶ繰り返しを使用する は、2aと 3を与えますがb、これは意図したとおりです。

これを説明できる唯一の方法は、(?<B-A> b)+バックトラックが 1 つ少ない に一致する場合b、スタックからポップしBますが、対応してスタックからポップされたものをプッシュバックしないAということです。したがって、bバックトラッキングにより 1 つ少なく一致したとしても、Aスタックは空のままです。r1これは、どのように一致するかを説明できる唯一の方法ですaaabbb。

reluctant +?inを使用しr2てもこの問題は発生しないことに注意してください。A私の見方では、貪欲な繰り返しとは異なり、消極的な繰り返しは、いわばスタックへの「ダメージを元に戻す」必要がないためです。対照的に、貪欲な繰り返しは可能な限り多くの「ダメージ」を引き起こしますが、バックトラックはAスタックに「物事をそのまま残す」ことに失敗します。

これは何が起こったのかについての正しい分析ですか？もしそうなら、これは仕様によるものですか? 基本的には、貪欲な繰り返しでバランシンググループを後戻りすると不均衡が生じる可能性があるため、これはバグとして分類される可能性があるためです (または、少なくとも文書化されていない驚くべき動作)。

考えられるすべての解決策を列挙し、最良のものを見つけることで解決できるように見える問題があります。そのために、最適なソリューションが見つかった場合にそれを列挙して保存するバックトラッキングアルゴリズムを考案しました。これまでのところ正常に動作します。

さて、このアルゴリズムをCUDAに移植したかったのです。したがって、私はいくつかの明確な基本的なケースを生成するプロシージャを作成しました。これらの基本的なケースは、GPUで並行して処理する必要があります。CUDAスレッドの1つが最適な解決策を見つけた場合、他のすべてのスレッドは、もちろん、作業を停止できます。

そこで、次のようなものが必要でした。最適なソリューションを見つけるスレッドは、プログラムの実行中のすべてのCUDAスレッドを停止し、計算を終了する必要があります。

簡単に検索したところ、スレッドは同じブロック内にある場合にのみ通信できることがわかりました。（したがって、他の人がスレッドをブロックするのを止めることは不可能だと思います。）

私が考えることができる唯一の方法はoptimum_found、すべてのカーネルの先頭でチェックされる専用のフラグを持っていることです。最適なソリューションが見つかった場合、このフラグはに設定される1ため、将来のすべてのスレッドは、それらが機能する必要がないことを認識します。ただし、もちろん、すでに実行されているスレッドは、反復ごとにチェックしない場合、このフラグに気づきません。

それで、残りのすべてのCUDAスレッドを停止する可能性はありますか？

次のコードがあるとします。

今私がするとき

コンソールに印刷されたネイバーのリストを取得できます。しかし、どうすれば結果リストとして取得できますか？何かのようなもの

（上記の部分は、処理方法が原因で実際​​には機能しませんmember。何か提案がありますか？

配列「4,2,7,5,1」を「1,2,4,5,7」にソートするソート方法を構築したい私の現在のコードは

なにが問題ですか