3

次のような表現でいっぱいのテキストコンテンツがあります。

a = 1
d = b + c 
b = a * c
c = 2 - a
...

この式はランダムな順序で記述できます。これらの式をそれぞれ抽出して評価することはできますが、次のような循環評価を避けるために最適なアルゴリズムを見つける必要があります。

a = 1
d = ? (skip)
b = ? (skip)
c = 2 - a = 1
...
d = ? (skip)
b = a * c = 1
...
d = b + c = 2
...

余分な計算パスを避けるために、関係する引数で方程式を「順序付け」する方法はありますか?

a = 1
c = 2 - a = 1
b = a * c = 1
d = b + c = 2
...

?

4

1 に答える 1

2

式ごとに、グラフにノードを作成します。ここで、着信エッジは依存する他の式です。次に、トポロジカル ソートを使用して評価順序を決定します。

例：

表現:

a = 1
d = b + c 
b = a * c
c = 2 - a

グラフ ノード:

a()
d(b,c)
b(a,c)
c(a)

トポロジカル ソート:

begin
    process a
        process a's dependencies (none)
        output a
        mark a as done
    process d
        process d's dependencies
            process b
                process b's dependencies
                    process a (already done)
                    process c
                        process c's dependencies
                            process a (already done)
                        output c
                        mark c as done
                output b
                mark b as done
            process c (already done)
        output d
        mark d as done
    process b (already done)
    process c (already done)
end

結果：

a c b d
于 2012-09-23T04:25:57.303 に答える