1

ノードのサブセットで動作する標準のトポロジカルソートアルゴリズムのバリエーションを探しています。

「依存」、「前」、「後」の 3 種類の有向辺を持つラベル付きノードのグラフを考えてみましょう。

私が望む関数は、ノードのサブセットを受け入れ、線形順序を返します。線形順序付けは、「前」および「後」の制約に従い、「依存先」を「前」の制約として扱います。線形順序付けのノードは、依存関係が含まれるように、入力ノードのスーパーセットである必要があります。

グラフの例:

A depends on B
B depends on C
D before C
E after C

X after Yは自明にY before Xに書き換えることができます

テストケース:

f({A})     -> [C B A]
f({A D})   -> [D C B A]
f({B D E}) -> [D C B E] or [D C E B]

ボーナス ポイント:順序付けの最初と最後のノードを強制するようにアルゴリズムを構成することもできます。

4

1 に答える 1

2

対象のノードの和集合とそれらの依存関係と交差するグラフ全体のトポロジカルソートを取ります。擬似コードの場合：

λ N = A ∩ (N ∪ D)

ここで、 Aはトポロジカルソートされたグラフの順序集合であり、 Nは関心のあるノードのサブセットであり、DはNの依存関係です。交差演算子はAの順序を尊重する必要があることに注意してください。

またはHaskellで（あなたの例のように、文字の代わりにノードに数字を使用します）：

import Data.List (intersect, union)
import Data.Graph (buildG, reachable, topSort)

graph = buildG (0, 4) [(3,2), (2,4), (2,1), (1,0)]

dependencies = buildG (0, 4) [(0, 1), (1, 2)]

ordering = topSort graph

f nodes = ordering `intersect` (nodes `union` deps)
  where deps = concatMap (reachable dependencies) nodes

これは、グラフのすべてのエッジを指定できることを前提としています。合計順序を計算する必要があるのは1回だけなので、後続の呼び出しに対してパフォーマンスが高い必要があることに注意してください。

上記のコードは次のように出力します。

> f [0]
[2,1,0]

> f [0, 3]
[3,2,1,0]

> f [1, 3, 4]
[3,2,4,1]

上記のテストケースと一致します。

何らかの理由でグラフのすべてのエッジを指定できず、相対的な制約だけを指定できる場合は、上記のように（N∪D）を計算し、制約の満足度を適用します。これを行うための素朴な方法は、すべての制約を満たすノードが見つかるまで、これらのノードのすべての順列を試すことです。明らかに、単純な深さ優先探索とバックトラッキングのアプローチでさえ、それよりもはるかに効率的にそれを行うことができます。

編集：深さ優先コード

ものすごく単純。関心のあるノードのすべての順列のツリーを作成し、すべての制約を満たす順列が見つかるまでそのツリーをウォーク/プルーニングします（依存関係も制約であるため、依存関係を制約に追加することに注意してください）。すべての制約は（A、B）の形式で指定されます。これは、「AはBの後に来る必要がある」という意味です。

順列をリストではなくツリーとして生成するため、特定のパスプレフィックスが制約に違反するとすぐに、検索スペースの大きなチャンクを簡単に取り除くことができます。

import Data.Maybe (fromMaybe, isJust)
import Data.List (union, nub, elemIndex, find)
import Data.Tree (unfoldTree, Tree (Node))
import Control.Applicative (liftA2)

dependencies = [(0, 1), (1, 2)]

constraints = [(2, 3), (4, 2)] ++ dependencies

f nodes = search $ permutationsTree $ (deps `union` nodes)
  where deps = nub $ concatMap dependenciesOf nodes

search (Node path children)
  | satisfies && null children = Just path
  | satisfies = fromMaybe Nothing $ find isJust $ map search children
  | otherwise = Nothing
  where satisfies   = all (isSatisfied path) constraints
        constraints = constraintsFor path

constraintsFor xs = filter isApplicable constraints
  where isApplicable (a, b) = (a `elem` xs) && (b `elem` xs)

isSatisfied path (a, b) = fromMaybe False $ liftA2 (>) i1 i2
  where i1 = a `elemIndex` path
        i2 = b `elemIndex` path 

permutationsTree xs = unfoldTree next ([], xs)
  where next (path, xs)      = (path, map (appendTo path) (select xs))
        appendTo path (a, b) = (path ++ [a], b)

select [] = []
select (x:xs) = (x, xs) : map (fmap (x:)) (select xs)

dependenciesOf x = nub $ x : concatMap dependenciesOf deps
  where deps = map snd $ filter (\(a, b) -> a == x) dependencies

ほとんどのコードはかなり単純ですが、ここに私の頭のてっぺんからいくつかのメモがあります。

  • 計算上、これは以前に投稿されたアルゴリズムよりもはるかに高価です。より洗練された制約ソルバーを使用しても、うまくいく可能性はほとんどありません（このような制約で実行できる事前計算は実際にはないため、少なくとも私にはすぐにわかるものはありません）。

  • 指定されたすべての制約を満たすパスがない可能性があるため、「f」関数は多分を返します。

  • 制約Forは、合計計算時間の約43％を占めます。それはかなり素朴です。それをスピードアップするためにいくつかのことができます：

    1）パスが制約を満たしたら、それにノードを追加してもその制約に違反することはできませんが、この事実を利用しません。代わりに、制約が以前に合格したことがわかっている場合でも、特定のパスに関連するすべての制約を再テストし続けます。

    2）制約を線形探索して、適用可能な制約を見つけます。代わりに、それらを適用するノードにインデックスを付けると、これを高速化できます。

    3）テストする制約の数を減らすと、計算時間の約25％を占めるisSatisfied呼び出しも明らかに減ります。

  • 厳密に実行される環境でこのようなコードを実装する場合は、コード構造を少し変更する必要があります。このように、このコードは順列ツリーが怠惰であることに大きく依存しています。これにより、検索コードは不適切と見なされたパスをたどらないため、検索コードをツリー生成コードと絡み合わせる必要がなくなります。

最後に、最初のソリューションだけでなく、すべてのソリューションを検索する場合は、検索本文を次のように変更します。

| satisfies && null children = [path]
| satisfies = concatMap search children
| otherwise = []

完全なグラフを指定できると仮定すると、元のアルゴリズムが明らかに優れているという理由だけで、このコードなどの最適化に時間を費やすことはありませんでした（これは可能だと思います）。

于 2012-12-29T12:18:05.723 に答える