有向非巡回グラフを順に並べるソートアルゴリズム。
Directed Acyclic Graph で DAG ともいう。
1.A→B 2.A→B ↑ ↓ ↓ ↓ D←C D→C 閉路 閉路じゃない
DAGでは、どのリンクに対しても、流入元ノードが前、流出先ノードが後に来るように1列に並び替えることができる。これをトポロジカルソートという。
「リンクが常に右向きになっている」と言い換えてもよい。
上記2.のトポロジカルソート例 ┌───v A→B D→C └───^ DAGでない1.は、どこかに左向きのリンクができてしまう A→B→C→D ^----------┘
ソート結果は一意に決まるとは限らない。2.の場合、ADBCもソート結果の1つである。
各ノードnにつき、以下の情報を保持する
B E この場合、 ↘ ↗ Aに流入するリンク数はBCDの「3」 C→A→F Aからの流出先ノードは「E,F,G」となる ↗ ↘ D G
また、以下のデータを作成する
以下の擬似コードでソートできる
while Sが空になるまで Sから任意のノードnをpop Lの末尾にnを追加 foreach m in nから流出する先のノードリスト mの流入リンク数を1減らす if mの流入リンク数 == 0 mをSに追加 if Lの長さ == ノード数N Lがソート結果 else グラフはDAGでなく、トポロジカルソート不可能
# ・ノードIDは、0~N-1とする # ・以下のデータは既に作られているとする # inc[n] = nに流入するリンク数(int) # out[n] = nからの流出先のノード集合(list or set) S = {i for i, c in enumerate(inc) if c == 0} L = [] while S: n = S.pop() L.append(n) for m in out[n]: inc[m] -= 1 if inc[m] == 0: S.add(m) # DAGであることは前提として、チェックは省略 print(L)
Sに同時に複数のノードが入っている瞬間があると、pop時にどれが選ばれるかによってソート結果が変わる。
ここで、例えばSに優先度キューを用いるとノードIDが小さい順に取り出され、小さいノードを優先して前に持ってくるよう固定される。
ソート結果の1つを求めるなら上記でよいが、「ソート結果としてあり得る並び方が何通りになるか」という問題は、現実的な時間では解けない。
オーダーは、動的計画法を上手く使うことでO(N * 2^N)となるので、N=20くらいまでなら何とかなる。
全ノードの集合をUとし、その部分集合Sを考える。
$f(S) = Sのみを使ったソート結果の候補数$ とする。f(U)を求めればよい。
この時、以下の関係が成り立つ。
Sの中で、「ソート結果で最も右に置くことができるノード」(Sの中に流出先ノードがない、末端ノード)の集合をTとすると、
$f(S) = \displaystyle \sum_{n \in T} f(S \setminus \{n\})$
となる。$S \setminus \{n\}$は、「Sからnを除いた集合」という意味。
A→B→C→E \ ↗ →Dー→F
このようなグラフの場合、ソート結果は以下の9通りあるが、
最も右に置くことができるのは、EかFである。
つまり、$f(\{ABCDEF\}) = f(\{ABCDE\}) + f(\{ABCDF\})$ ということになる。
Eを除いたABCDFに付いて考えると、最も右に置くことができるのはCかFである。
つまり、$f(\{ABCDF\}) = f(\{ABCD\}) + f(\{ABDF\})$
同様に、$f(\{ABCD\}) = f(\{ABC\}) + f(\{ABD\})$……と求めていき、$f(\phi)=1$で確定する。
集合がキーになる動的計画法で、要素数が高々32個くらいまでなら、集合をbitフラグで管理するとよい。bitDPという。
{ABCDEF} = 0x111111、{A,C,F} = 0x100101 という感じだ。これならメモリも少なく済むし、要素が含まれるかのチェックもbit演算で済むため速い。
わかりやすくするため要素数の多い方から考えていったが、実際には要素数が少ない方から計算していく。
「候補数が確定した集合i」に、「新たに末尾に加えられるノードj」があれば、「iにjを加えた集合」の候補数に集合iの候補数を加算する。
iをforループで小さい方から回していくと、iに到達した時にはiに含まれる全ての要素kについて考慮が済んでおり、候補数が確定していることが保証される。
各ノードnにつき、以下の情報を持っておく。
今回の例では、たとえばDからはE,Fへ流出するので、Dの値は0x110000 となる。
後は下記の擬似コードで求められる。iは候補数確定済みの部分集合、jはiの末尾に付け加えることが可能かチェック中のノードIDである。ノードIDは、0~N-1が振られているとする。
dp = サイズ2^Nの配列 dp[0] = 1 for i in 0~2^N-1 for j in 0~N-1 if 「集合iの中にjはまだ存在しない」 and 「jの流出先ノードにiの要素が含まれない」 dp[iにjを加えた集合] += dp[i] dp[2^N-1]が候補数
# b[n] = ノードnからの流出先ノードの集合のbitフラグ dp = [0] * (1 << N) dp[0] = 1 # ノードIDと対応するビット位置は繰り返し求めるので事前計算しておく jbs = [(j, 1 << j) for j in range(N)] for i in range(1 << N): for j, jb in jbs: if (i & jb) == 0 and (i & b[j]) == 0: dp[i | jb] += dp[i] print(dp[-1])