問題タブ [recursion]

複雑なグラフ構造をたどるパスを見つける必要があります。グラフは、次のようなものを使用して作成されます。

これを複雑にしているのは、ノードが以前のノードを参照できることです。例えば、

A -> C -> E -> A

私がする必要があるのは、特定の値を持つノードに到達するまで、ノードを通るパスを表すスタックのリストを取得することです。非常に大きなパスが利用できる可能性があるため、最大のノードを試すことができます。

誰かがこれを構築する方法を持っていますか (または同様のもの)? 私は過去に再帰を行ったことがありますが、何らかの理由でこれについて考えて、完全に脳のおならをしています。私の質問はラムダ式を指定しましたが、ラムダの使用は必ずしも必要ではありません。どんな解決策にも感謝します。

補足:この再帰の質問に対する aku の優れた回答からクラスを取り上げました。以下に示す彼のエレガントなソリューションはツリー構造をトラバースしますが、必要なことを実行するのに十分な柔軟性がないようです (たとえば、循環するパスを却下し、成功したパスを追跡します)。

編集：

以下のコメントと回答からの入力に基づいて、CodeProject で優れたソリューションを見つけました。A* パス検索アルゴリズムを使用します。 ここにリンクがあります。

私はキャリアの中でこの問題に数回遭遇しましたが、解決策に満足したことは一度もありませんでした。ASP.NetMVC、C＃、SQLServer2008で行っているプロジェクトで再び問題が発生しました。

私がPersonタイプ（クラス）を持っていると想像してください。私はさらに、人を拡張するタイプの母と父を持っています。父と母は非常に似ています。どちらも「子供」と呼ばれるプロパティを持っています。これは、Personタイプのコレクションです。「人」は、基本のPersonクラス、Motherクラス、またはFatherクラスのいずれかで表すことができます。この例から、継承（is-a）と関連付け（has-a）の両方の関係が進行していることがわかります。

これらのOOタイプを使用して、SQLServerに家系図を作成して保存したいと思います。人、母、父の3つのテーブルが欲しいと思います。すべてのオブジェクトには、Personのエントリがあり、必要に応じて、MotherまたはFatherにエントリがあります（PersonとのFK関係があります）。さらに、母の記録と子の記録の間の関係を保存するために、父と同じように、いくつかの横断歩道のテーブルが必要になります。

これはストレージの優れた戦略のように聞こえますか？

深くて広い家系図について、これをどのように効率的に照会しますか？

私が悩まされている問題は、ツリー内のノードで返され、与えられたデータの多形性です。これがPersonオブジェクトのツリーである場合は、再帰共通テーブル式を使用します。ただし、任意のノードに対して3つの異なる形状のデータが返される可能性があります。これを、C＃の3つのOOタイプの1つにマップします。明らかにC＃またはストアドプロシージャで再帰を実行できますが、過去のそのようなソリューションのパフォーマンスにはあまり満足していません。さらに、レコードを自然に挿入するにはどうすればよいですか？SQL ServerでのFK関係の強制のため、過去には常に正しい順序（Person、次にFatherまたはMother）で挿入する必要がありました。

このタイプのORMを処理するフレームワークはありますか？

編集：

明確にするために、私が必要とする解決策は、表示するために家系図全体を取得し、家系図にノードを追加および編集できるようにすることです。最善の解決策は、深いツリーの1つのクエリでこれを行うことだと思います。スキーマを設計し、保存し、取得する方法は、私が求めているものですか？

だから私はPythonで簡単な二分木を書いていて、出くわしました[...]

これがEllipsisオブジェクトに関連しているとは思わないが、それ以上に、無限ループと関係があるようだ（Pythonの浅いコピーのため？）。この無限ループの原因と、アクセス時に拡張中に拡張されない理由は、私が完全に失ってしまったものです。

a+bを使用したバージョン

[a、b]を使用したバージョン

では、[...]とは正確には何ですか？

「A Gentle Introduction to Haskell」を読んでいますが、早い段階で次の例を使用しています。これは、GHC では正常に機能し、私の脳では恐ろしく機能します。

そして呼び出しコード：
take 10 reqs

私がそれをどのように見ているかは、 がreqs呼び出されclient、引数 0 とresps. したがって、resps今は呼び出される必要はありません...これは再び呼び出さreqsれますか? それはすべてとても無限に思えます...誰かがそれが実際にどのように機能しているかを詳しく説明できれば、私は最も感謝しています!

すべての子孫の葉 (直接または間接) を返すツリー ノードに関数を実装する方法を理解しようとしています。ただし、リーフノードが再帰的に配置されるコンテナーを渡したくありません (ツリーが巨大になる可能性があります)。代わりに、ジェネレーターを使用してツリーを反復処理したいと考えています。いくつかのアプローチを試しましたが、これまでのところどれもうまくいきませんでした。これは、私が考えられる解決策に最も近いものです:

しかし、これも機能していません。私は何を間違っていますか？同じ関数にyieldステートメントがある場合、.EnumerateLeavesを再帰的に呼び出すことはできません。

どんな助けでも大歓迎です。前もって感謝します。

編集:ブランチは葉または枝のいずれかを子として持つことができるため、再帰があることを忘れていました。

Mark Lutzによる「LearningPython」を読んでいて、このコードサンプルに出くわしました。

これは、循環データ構造として識別されました。

だから私は疑問に思っていました、そしてここに私の質問があります：

実際のプログラミングで使用される「循環データ構造」とは何ですか？

少し混乱しているようですが、これは非常に短いコードサンプルに起因すると思います...同じオブジェクトLを使用した行がさらに数行あります

Perl のData::Rmapを使用すると、データ構造のリストに対して BLOCK を再帰的に評価し (ローカルで各要素に $_ を設定)、そのような評価の結果で構成されるリストを返すことができます。$_ を使用して要素を変更できます。

これは、ネストされたハッシュやハッシュの配列の階層などを反復処理する場合に便利です。

再帰的な C++ プログラムでメモリの割り当てと割り当て解除に問題があります。自動メモリ管理ソリューションを使用せずに、誰かが私が経験しているメモリリークを解決するのを手伝ってくれるのではないかと思います.

次のコードは基本的に問題を説明しています (これは不自然な例ですが、間違いや簡略化を修正してください)。

数値の値を保持する数値クラス:

再帰を実行する 2 つの関数:

ご覧のとおり、再帰関数で割り当てられたメモリがリークされていますが、再帰の性質に基づいて、このメモリをどこから解放できるかわかりませんか?

組織内に支店用のテーブルがあるとします。それらのいくつかは「メイン」ブランチであり、その他はメイン ブランチにロールアップされるサテライト オフィスです。システム内のいくつかの事柄にのみ影響するこの違いを除けば、ブランチはすべてピアであり、同じ属性 (アドレスなど) を持っています。これをモデル化する 1 つの方法は、次のような表です。

Where is_satellite_office= 1 このレコードが別のブランチsatellite_to_branch_idのサテライトであり、サテライトであるブランチがある場合はそのブランチを参照します。

これらの 2 つの列が特定のレコードで一致するように、テーブルに制約を設定するのは簡単です。

しかし、私が本当に欲しいのは、この再帰が1レベルの深さだけになることを保証する方法です...つまり、親としてブランチを指す場合、それは親自体を持ってはならず、その値is_satellite_officeは0. 別の言い方をすれば、私は完全に再帰的なツリー構造を望んでいません。単一の親子関係に制限したいだけです。それが私がコードを書く方法であり、完全にがらくたのように実行されないデータベースでそれを強制する方法があれば、私はそうしたいと思います。

何か案は？私は MSSQL 2005 に取り組んでいますが、一般的な (ベンダー固有ではない) ソリューションが優先されます。他に方法がない場合を除き、トリガーを適用する必要はありません。

編集: 明確にするためsatellite_to_branch_idに、同じブランチ テーブル内の別のレコードへの再帰的なポインターです。is_satellite_office BITを削除して、同じ情報を提供することに頼ることができることは知っていIsNull(satellite_to_branch_id)ますが、明示的にする方が少し明確であり、さらに、それは質問の要点ではありません。再帰の深さが 1 を超えるのを防ぐための純粋な SQL 制約の方法を本当に探しています。

つまり、次のようなことができますか

N回以外？言い換えれば、ループを作成するメソッドが呼び出されると、パラメータ N が与えられ、メソッドはネストされたこれらのループを N 個作成しますか?

もちろん、「簡単な」または「通常の」方法で行う必要があるという考えです。私はすでに非常に複雑なもののアイデアを持っています。