1

信号フローベースの「プログラム」（たとえば、Simulinkに似たもの）のグラフがあると仮定します。つまり、いくつかの開始ノードといくつかの終了ノード、およびその間に多数のノードがある有向グラフがあります（循環関係がないことを願っています）

そのグラフをたどって計算順序を教えてくれる、よく知られているアルゴリズム（おそらくPythonライブラリとしても利用可能）はありますか？

例（方向は示されていません、明白であると仮定してください）：

In1 In2
   \\
    [-] [*]-Out1
   / \ /
In3 [+] ------ Out2
       /
    In4

これにより、指示/順序が表示されます。

1. tmp1：= In1-In3
2. Out2：= tmp1 + In4
3. Out1：= In2 * Out2

ありがとう！

4

1 に答える 1

3

トポロジカルソートのある種のバリエーションを探していますか？

開始ノードがわかっているので、それらからアルゴリズムを開始できます。「操作」ノードに出会ったら、それにつながるノードを使用して計算を作成します。当然、グラフは問題に固有のいくつかの点で一貫している必要があります。

これをPythonで実装するには、優れたグラフライブラリ（NetworkXなど）が必要です。トポロジカルソートは実装が非常に簡単で、多くのグラフライブラリにはすでに実装されたアルゴリズムとして含まれています。たとえば、NetworkXの場合--networkx.algorithms.dag.topological_sort。ただし、前述のように、これはおそらくトポロジカルソートではなく、そのバリエーションです。

于 2011-04-27T08:22:27.880 に答える