問題タブ [recursive-backtracking]

3桁の数字のすべての順列を再帰的に見つけることに取り組んでいます。

次の順列メソッドを構成するのにうんざりしています。

各ステップの詳細とともに、すべてのケースをカバーしようとしましたが、それでも突然スタックオーバーフロー例外が発生します。

あなたの貢献に感謝します。

このコードは、4 クイーンの問題を解決しようとしています。4 つのクイーンを 4*4 のチェス盤に配置し、それらのいずれも互いにキャプチャすることはできません。

このようなボードがあるとしましょう

x はボックスと '.' を使用します。は無料です。すべての領域を埋めるためにトリオミンを配置する必要があるため、空きセルはありません。トリオミンはL字型で、同じトリオミノには同じ番号をつけています。

したがって、解決策は次のようになります。

考えられるバックトラッキング python アルゴリズムは何ですか?

私は約 5 年間プログラミングをしていますが、動的な迷路を作成するのに何の問題もありませんでした。しかし、再帰的なバックトラッキングになると、どこから始めればよいかまったくわかりません。私は多くのチュートリアル、トピック、およびいくつかのアルゴリズム wiki (ダイクストラのアルゴリズム) を読みましたが、それらは私には意味がありません。

基本的な再帰がどのように機能するかは知っていますが、以前に検索されたパスを保存せずに再帰的なバックトラッキングがどのように可能であるか (私にはそう思われます)、または追跡されているパスが突然 2 つに分割された場合に何が起こるかを理解し始めることはできません。

私のプログラムは次のように動作します: 迷路は 484 のパネル (mazeTiles という名前の Panel[] 配列) から構成されます。22 列あり、各列には 22 枚のパネルが入ります。黒いパネルの背景は壁で、白いパネルは通過可能です。

これは実行時にどのように見えるかです (そして、左上の開始四角形 (赤) から緑四角形への有効なパスがない場合にのみ表示されるエラー メッセージ):

http://postimg.org/image/6c7wgxtz1/

表示されるエラーメッセージは、明らかに解けるのに「迷路が解けません」というもの。このエラー メッセージは、Button2_Click メソッドにあります。

以下は、チュートリアルから取得した (および変更した) コードです。問題はメソッド内にあることは間違いありませんが、これをトラブルシューティングする方法がわかりません。

赤い四角から緑の四角までのすべてのパスまたは最も速いパスを見つけて保存する必要があります (最も速いパスのみをマークします)。緑の四角は静的ですが、赤の四角と迷路全体はランダムに生成されます。

配列と目標 (数値) が与えられた場合、配列から要素を追加することで目標を達成できるかどうかを判断する必要があります。ここに私のコード（JavaScript）といくつかの結果があります：

check(6,[1,3,5]) を呼び出した後に add() のスタックに起こると予想されること

実績：

最初のブランチから離れることはありません。なんで ？ 編集: わかりました、提案に基づいて、引数として配列を渡さない方が良いと思います:

ここではうまく機能します。

括弧の生成
n 対の括弧が与えられた場合、整形式の括弧のすべての組み合わせを生成する関数を作成します。

たとえば、n = 3 の場合、解セットは次のようになります。

"((()))"、"(()())"、"(())()"、"()(())"、"()()()"

---

個人的には、
時間の複雑さ
= O(n! ) (tmpStr をコピーする時間を含まない)、n は入力、
= O(n * n!) (tmpStr をコピーする時間を含む) だと思います。

スペースの複雑さ
= O(n) (スタック スペースの使用量)、
= O(n) (スタック + 再帰スペースの使用量)。

---

コード: Java

単語区切り(動的プログラミングを使用: Top->Down)
文字列 s と単語 dict の辞書が与えられた場合、s にスペースを追加して、各単語が有効な辞書単語である文を作成します。

そのような可能な文をすべて返します。

たとえば、指定された
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

解決策は【「猫と犬」、「猫砂犬」】です。

---

質問：

• 時間の複雑さ ?
• 空間の複雑さ ?

個人的に私は思います、

• 時間計算量 = O(n!)、動的計画法なし、n は与えられた文字列の長さ、
• スペースの複雑さ = O(n)。

困惑：

• 動的計画法で時間計算量を把握できません。
• 上記のスペースの複雑さは正しくないようです。

---

コード[Java]