問題タブ [backtracking]

これが私が書いたコードです。

少し説明。私はチェスのボードを表すために int [8][8] を使用しており、最初はボードのすべての正方形に数字 -1 を入れています。

ナイトが移動すると、カウンター (int カウンター) で訪問するマスをマークし、そこから (そしてナイトが実行できるすべての正当な動きに対して) パスを見つけるために再帰呼び出しを行います (目標は、各マスを 1 回だけ訪問することです)。 ）。

カウンターが 64 に達すると、関数bool knighttour(square start,int &counter,int cb[][8]) は true を返す必要があり、メイン プログラムは [8][8] チェス盤にマークされているように「騎士のツアー」を表示する必要があります。

私が提供した上記のコードは無限ループで実行されると思います。3分間走らせました。

バックトラッキングを使用して、可変長の一致を可能にする長い文字列内のすべての部分文字列を検索したいと思います。つまり、指定された最大数の不一致、挿入、および削除を許可する一致です。有用な例を見つけることができませんでした。私が見つけた最も近いものは、こちらの論文ですが、それは非常に複雑です。誰？

乾杯、

マーティン

検討：

次のいずれかの位置にある場合、アルファベットはタイル内の別のアルファベットに隣接してi_indexいます。j_indexi_indexj_index

ここで、すべて*はに隣接する場所を示しますx。

タスクは、タイル内の特定の文字列を見つけることです。条件は、指定された文字列のすべての文字が隣接している必要があり、指定された文字列を構成するためにタイル内の1つの文字を複数回使用することはできないということです。

私は単純なバックトラックソリューションを考え出しました。そのソリューションはかなり高速ですが、最悪の場合の時間は本当に悪いです。

例：タイルの4x4がすべての's、つまり16 a 'で満たされ、検索する文字列がaaaaaaaaaaaaaaaab、つまり15a 'sと1つのbであるとします。1つは、タイルに表示されない文字を含む文字列を削除することです。しかし、それでも最悪のケースは、タイルにababababababababがあり、検索する文字列がabababababababbbbであると言うことで表示される可能性があります。

私の試みは次のようなものです：

https://ideone.com/alUPf：

印刷するもの：

この関数spは作業を行い、バックトラッキングを実行します。

もっと良い方法はありますか？または、最悪の場合の時間を短縮することは可能ですか？

n-Queen問題のすべての可能な解決策に対してアルゴリズムを実装すると、多くのブランチで同じ解決策に到達することがわかりました。n-Queens問題に対するすべてのユニークなソリューションを生成する良い方法はありますか？異なるブランチ（保存と比較を除く）によって生成された重複ソリューションを回避するにはどうすればよいですか？

これが私が最初の解決策として試したことです： http ：//www.ideone.com/hDpr3

コード：

考えられるすべてのソリューションを生成するために、同じコードnqdfs_all ()関数を使用しましたが、コントロールを親に返さず、代わりに列挙とチェックを続けました。この関数を呼び出すと、さまざまなブランチが到達した重複した結果が表示されます。

私は現在、再帰的なバックトラックの美しいトピックを研究しています。迷路から最短経路を見つける、またはn-queens問題など、古典的な例をすでに試しました。しかし、私が今取り組んでいる問題は本当に私を混乱させます：実際、私は単純なジグソーパズルを解くのは簡単な練習かもしれないと思いました：私はn = a * bのサイズで正確にそれだけのボードを持っています（ n）ピース。
結局、私はすべてのピースを特定の順序でボードに配置し、特定の制限（隣人とのマッチングなど）に従うようにしたいのです。かなり簡単だと思い、次のアルゴリズムを思いつきました。

基本的に、このアルゴリズムは本来の機能を果たしますが、残念ながら、「小さい」ボードサイズ（n <100）でのみ機能します。10 x 10の正方形と100個のようなボードがある場合、関数は検索して検索し、ヒープスペースが不足しているためにJVMがクラッシュするまで終了しません。eclipseのメモリサイズ制限を1.2gまで設定してみたところ、機能が長くなりましたが、それでも十分ではありませんでした。

だから私の質問は：ボードサイズn> 100で動作するように上記のアルゴリズムを最適化することは可能ですか？私は何が間違っているのですか？それとも私は完全に間違ったアプローチを取っていますか？

よろしくお願いします。

低レベルのコースで課題として再帰を扱うのは初めてです。私はインターネットを見回しましたが、私が思いついた方法と同様の方法を使用している人を見つけることができないようです (おそらく、これが機能しない理由について何かを示しています)。std::__copy_move...エラーは、c++ STL にあると思われるセグメンテーション違反です。とにかく、私のコードは次のとおりです。

私はしばらくの間、このことに頭を悩ませようとしてきましたが、何が問題なのか理解できないようです. どんな提案でも大歓迎です！:)

都市のペア間の距離を含むテーブルを指定して、2つの都市間の最小距離を計算できるようにする必要があります。2つの都市は直接接続されていない可能性があり、代わりに3番目の都市を介して接続されている可能性があります。

これが私が持っているテーブルです

と

pl/sqlで再帰とバックトラッキングがどのように機能するかわかりません。

再帰を使用せずに文字列のリストから単一の文字にアクセスする方法を理解するのに問題がありますが、代わりにバックトラックします。

たとえば、この文字列のリストがあり、これらの文字列の1つ（'。''o'、'*'）から1文字を返すことができるようにしたいと考えています。私が取り組んでいるプログラムは、それを行と列として扱っています。私のデータベースでは、次のような事実があります。

私は述語を持っています：

行と列の番号（インデックスは1から始まります）を受け取り、その特定の行と列のエントリ（TheEntry）を返します。

述語の頭が正しく構築されていない可能性があると感じていますが、リスト内の各文字列を再帰せずに文字ごとに調べて返す方法に焦点を当てています。

私はプロローグに不慣れで、これに大きな困難を抱えています。

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

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

無向グラフGと各コンポーネントに属する頂点を持つ連結成分の数を決定するためにACM競合の問題を作成しています。すでにDFSアルゴリズムを使用して、無向グラフの連結成分の数を数えていますが（問題の難しい部分）、各成分に属するノードを示したり、ノードの記録を持ったりすることは考えられません。

入力：入力の最初の行は、テストケースの数を示す整数Cになります。各テストケースの最初の行には、2つの整数NとEが含まれています。ここで、Nはグラフ内のノードの数を表し、Eはグラフ内のエッジの数を表します。次に、それぞれ2つの整数IとJを持つE線をたどります。ここで、IとJは、ノードIとノードJの間にエッジが存在することを表します（0≤I、J

出力：各テストケースの最初の行に、次の文字列「ケースG：接続されたPコンポーネント（s）」を表示する必要があります。ここで、Gはテストケースの数（1から開始）を表し、Pは接続されたコンポーネントの数を表します。グラフで。次に、スペースで区切られた連結成分に属するノードを（小さいものから大きいものの順に）含むX行。各テストケースの後に、空白行を印刷する必要があります。出力は「output.out」に書き込む必要があります。

例：

入力：

出力：

これが私のコードです：

接続された各コンポーネントまたは構造に属するノードのメモリをどのように運ぶか、保存に使用する必要があるか、これを行うためにコードをどのように変更する必要があるかについて疑問があります。提案、アイデア、または擬似コードでの実装を聞きたいです。ありがとうございます

以前の投稿で指定した問題に対して、バックトラッキング ベースのソリューションを実装しました: Packing items into Fixed number of bins

(Bin は、vector<int>sum() などの追加メソッドを備えたデータ型の単純なラッパーです)

このアルゴリズムは非常に高速に動作しますが、大規模なデータ セットではスタック オーバーフローが発生する傾向があります。

それを改善するためのアイデアや提案を探しています。

編集：

明示的なスタックを使用して反復アプローチを試みることにしましたが、私のソリューションは期待どおりに機能しません - 時々間違った結果が得られます。

どんな提案でも大歓迎です。