c# - プロジェクトの総コストを合計するための再帰ツリー アルゴリズム

Question

この問題を解決するアイデアはありますが、一般的なツリーのみを使用していますか?

すべてのノードを合計する必要がありますが、エッジ値を尊重します。

2 つのノード間のエッジ > 1 の場合、サブツリーのコストは、サブツリー全体で最も乗算されます。

ソリューションはツリー アルゴリズムを使用する必要があります

ありがとう

http://oi39.tinypic.com/24buik7.jpg

Answer 1

Nodeobject があり、それ自体costと一連の出力を含み、それぞれに重みがあると仮定するとedges、次のことができます。（投稿した写真には木が表示されていないため、pkacprzakが述べたように、DAGがあると思います）

class Edge
{
    public int Weight { get; set; }
    public Node Start { get; set; }
    public Node End { get set; }
}

class Node
{
    private int cost;
    private IEnumerable<Edge> edges;

    // ...

    public int Cost()
    {
        int totalCost = cost;

        foreach (var edge in edges)
        {
            totalCost += edge.Weight * edge.End.Cost();
        }

        return totalCost;
    }
}

CostDAG のソース (つまり、着信エッジのないノード) を呼び出す必要があります。複数の情報源がある場合、何を達成したいかはあなた次第です。