1

私は「ノード」のネットワークを持っており、各ノードは「結果」を生成します。各ノードと結果には一意の名前/IDがあります。結果は、各ノードの入力と出力の両方として使用されます。ノードのすべての入力結果が利用可能になったら、それを実行できます。ノードが出力の実行を終了すると、出力結果が利用可能になります。

したがって、たとえば：

input node output
       A    x
x      B    y,z
x,z    C    q

上記のネットワークで。ノードAには入力がなく、最初に実行できます。次に、結果xが使用可能になったときにBを実行できます。AとBの両方が実行されると、AとBの結果に依存するため、Cを実行できます。結果は、この場合のyのように、どのノードへの入力としても使用されない最終結果になることもあります。

ネットワークははるかに複雑になる可能性があります。各ノードは多数の結果を生成でき、多数の入力依存関係を持つことができます。

結果を選択して、「q」と言って、そこに到達するためにどのノードを実行する必要があるかを把握できるようにしたいと思います。ノードのより大きなネットワークで複数の結果を得るためにこれを実行したいと思います。

これは一般的なアルゴリズムだと思いますが、この分野での経験はありません。依存関係によって円が作成される可能性があるため、ツリーのように階層的ではありません。私が読んだことから、それは一種の森のグラフに違いないと思います。

いずれにせよ、それはトラバース可能でなければなりません。最初に実行できるノードは常に少なくとも1つあり、他のすべてのノードは、2つのノードが互いに終了するのを待っているデッドロックを作成せずに、ある順序で追跡できる必要があります。

このネットワーク/そのノードをコードで説明する一般的な方法は何ですか？また、そのようなネットワークの正式な名前は何ですか？

4

2 に答える 2

1

探している名前は「依存関係グラフ」です。

分解に使用されるアルゴリズムは「トポロジカルソート」と呼ばれます（http://en.wikipedia.org/wiki/Topological_sortingを参照） 。

このような依存関係を解決する最も有名なツールの1つは、makeと呼ばれます。

あなたの例に対応するMakefileは次のようになります。

x :
    echo node A

y z : x
    echo node B

q   : x z
    echo node C

ご覧のとおり、構文は例の表で使用されているものとほぼ同じです。唯一の主な違いは、「列」の順序が逆になっていることです。「から...に行くことができます」ではなく、「...に行くには...最初に必要になります...」と言います。

入力make <TARGET>すると、希望する順序でノードが解決されることを簡単に確認できます。ここにいくつかの例があります：

make q
  * node A
  * node B
  * node C

make x
  * node A

make z
  * node A
  * node B

（出力を少しきれいにするために、これは上記の出力に使用されたバージョンです：

x :
    @echo " * node A"

y z : x
    @echo " * node B"

q   : x z
    @echo " * node C"

）。

于 2013-03-25T22:04:21.790 に答える
0

単なるグラフの一種であるだけでなく、必要なセマンティクスは、色付きのトークンを持つペトリネットのようなもののように聞こえます。ペトリネットを介した到達可能性分析は、アルゴリズムが文献に存在する確立された問題です。おそらく、ウィキペディアの記事はあなたに始めるためのいくつかのアイデアを与えるでしょう。

于 2013-03-25T22:06:02.717 に答える