12

アプリケーションのユーザー別に分類された項目 (下の青いノード) のリストがあります。カテゴリ自体をグループ化して分類することができます。

結果の構造は有向非巡回グラフ (DAG)として表すことができます。項目はグラフのトポロジの下部にあるシンクであり、上部のカテゴリはソースです。一部のカテゴリは適切に定義されている可能性がありますが、多くはユーザー定義であり、非常に厄介な場合があることに注意してください。

例：

サンプルデータ
(出典: theuprightape.net )

その構造で、次の操作を実行したいと思います。

  • 特定のノードの下にあるすべてのアイテム (シンク) を見つける (ヨーロッパのすべてのアイテム)
  • n 個のノードのセット (example.com から SMTP 経由で送信されたすべてのアイテム) のすべてを通過するすべてのパス (存在する場合) を検索します。
  • 一連のノードのすべての下にあるすべてのノードを見つけます (交差: 茶色い食べ物)

1 つ目は非常に簡単に見えます。ノードから開始し、考えられるすべてのパスをたどって最下部にアイテムを集めます。しかし、より速いアプローチはありますか？すでに通過したノードを覚えておくと、おそらく不要な繰り返しを避けるのに役立ちますが、さらに最適化はありますか?

2つ目はどうすればいいですか？最初のステップは、セット内の各ノードの高さを決定し、開始するノードを決定してから、セットの残りを含むその下のすべてのパスを見つけることです。しかし、これは最善の (または良い) アプローチですか?

ウィキペディアにリストされているグラフ トラバーサル アルゴリズムはすべて、特定のノードを見つけること、または 2 つのノード間の最短または最も効果的なルートを見つけることに関係しているようです。どちらも私が望んでいるものではないと思いますか、それともこれが私の問題にどのように適用されるかわかりませんでしたか? 他にどこを読むべきですか？

4

2 に答える 2

2

グラフが非循環的であるという事実にもかかわらず、引用した操作は、制御フロー グラフ分析の同様の側面を思い出させます。優性に基づいた、適用可能なアルゴリズムの豊富なセットがあります。たとえば、あなたの 3 番目の操作は、コンピューティングの最前線を思い出させます。「入り口」と「出口」ノードを一時的に導入すると、アルゴリズムが直接機能すると思います。入口ノードは「与えられたノードのセット」を接続し、出口ノードはシンクを接続します。

Robert Tarjan の基本アルゴリズムも参照してください。

于 2008-11-26T20:54:26.260 に答える
2

3つの質問すべてに対して本質的に同じ操作であるように私には思えます。「ノード Y の下のすべての X を検索します。ここで、X は Z 型です」と常に尋ねています。必要なのは、「ノードの下のすべてのノードを見つける」ための一般的なメカニズムだけであり (Q3 を解決)、「nodetype=sink」の結果をフィルタリングできます (Q1 を解決)。Q2 では、開始点 (ノード セット) と終了点 (開始点の下の任意のシンク) があるため、ソリューション セットは指定された開始ノードからシンクまでのすべてのパスです。したがって、基本的に持っているのはツリーであり、基本的なツリートラバーサルアルゴリズムを使用することをお勧めします。

于 2008-12-02T18:29:59.000 に答える