3

有向非巡回グラフ (DAG) で定式化できるこの技術的な問題があります。ノードはイベント (タイミングは不明) を表し、有向エッジは関係シップをエンコードします: 「私はあなたより若い/私はあなたの前に起こった」.

Weighted DAG (WDAG) が DAG の距離関数を意味するように、エッジの重み (つまり、「動的な重み」) を推定する必要があります。言い換えると、ノード A と B の間のパスの重みの合計は、すべてのパスで等しくなければなりません。

重みが整数であっても、これは未定の問題です（トポロジカルソートが一意ではないという根本的な理由と同じだと思います）。一般論として、ノード/イベント間の時間間隔を表すエッジの重みは実数です。したがって、ここでは指定されていない、重み付き DAG に事前設定された目的関数 C=J(WDAG) を導入します。

私の質問は次のとおりです。1) 重みが DAG の距離関数を形成し、2) 目的関数のコスト C を最小化するという制約に従って、WDAG に正定値の重みを分散するアルゴリズムはありますか?

これは、従来 WDAG に関連付けられていた最短パスまたは最小スパニング ツリーの問題とは無関係のようです。上記の問題に対する正式な解決策またはヒューリスティックな解決策はありますか?

よろしく、

ステファン

4

1 に答える 1

1

必要なのはトポロジカルソートだけだと思います。

  1. トポロジカル ソートに従ってノードをソートします。
  2. 取得した順序で [0,1] 間隔でそれらを配布します。
  3. [0,1] ライン上のノード ペアの距離は、それらを接続するエッジの重みを示します。

これは考えられる解決策の 1 つです。質問で説明したものよりも重みに制約がある場合、問題はより困難になる可能性があります。

于 2011-07-02T17:05:27.923 に答える