第7章最小の高さの木を組み立てる（やさしい版) — 関数プログラミングによるアルゴリズム設計の真珠

整数のリストが与えられたとき、その整数を葉のラベルにしてできるだけ「浅い（高さの低い）」木を組み立てたい、というのがこの章の問題です。木は次のように定義します。

data Tree = Leaf Int | Fork Tree Tree

Dart sealed class Tree { const Tree(); } class Leaf extends Tree { final int x; const Leaf(this.x); } class Fork extends Tree { final Tree u, v; const Fork(this.u, this.v); }

木のフリンジ（fringe）とは、葉のラベルを左から右へ並べたリストのことです。たとえば入力リストが [3, 1, 4, 1, 5] なら、フリンジがこのリストになる木を、なるべく浅く作りたい、ということです。

この章のテーマもっと一般に、「木のリスト（それぞれ高さつき）」を、順序を保ったままひとつの最小高さの木にまとめる問題を、線形時間 O(n) で解くアルゴリズムを導きます。ポイントは foldrn（空でないリスト用の畳み込み）と融合則で指数時間の素朴解を効率化し、最後に貪欲な挿入操作にたどり着くことです。

はじめに

すでに知られている2つの方法

入力が整数リストで、そのすべてを葉に持つ最小高さの木を作る方法は、昔から2つ知られています。どちらも線形時間で動きます。

この2つは違う形の木を作りますが、どちらも高さは最小になります。

ここで扱う一般化

ボトムアップの発想を一歩進めると、次のような問題になります。

一般化した問題 木のリスト（それぞれ高さつき）が与えられたとき、それらを順序を保ってひとつの木にまとめ、しかも高さを最小にする——これを線形時間でできるか？

入力が「葉だけのリスト」の特殊ケースなら、これは前の問題に戻ります。しかし、木の高さがバラバラで一般の場合、線形時間で解ける「明らかな理由」はありません。本章では、まさにそれができることを導きます。

最初の一歩

問題を「高さのリスト」として言い直す

木のリストのかわりに、その高さの列 xs = [x₁, x₂, …, x_n]（自然数の列）が与えられたと思っても、問題は同じです。求めたいのは、フリンジが xs になる木のうち cost（コスト）を最小化するもの。cost は次で定めます。

cost (Leaf x) = x cost (Fork u v) = 1 + (cost u max cost v)

Dart // 葉の高さを 0 ではなく葉の値 x とみなす特殊な「コスト」。 int cost(Tree t) => switch (t) { Leaf(:final x) => x, Fork(:final u, :final v) => 1 + (cost(u) > cost(v) ? cost(u) : cost(v)), };

これは通常の高さ（height）とほぼ同じ定義ですが、葉 Leaf x の「高さ」を 0 ではなく x とする点だけが違います。もとの木の高さを引きずるためにこう定義するわけです。

解きたいこと求める関数はこう書けます。

mincostTree = minBy cost · trees

ここで trees は「与えられたフリンジを持つあらゆる木」を返し、minBy cost はその中から最小コストの木を1つ選ぶ関数です。

trees の帰納的な定義

trees はトップダウンでもボトムアップでも書けますが、ここでは帰納的（要素を1つずつ足していく）な書き方を採ります。

trees :: [Int] → [Tree] trees [x] = [Leaf x] trees (x:xs) = concatMap (prefixes x) (trees xs)

Dart // フリンジ xs を持つすべての木を列挙する。 List<Tree> trees(List<int> xs) { if (xs.length == 1) return [Leaf(xs[0])]; final x = xs.first; final rest = trees(xs.sublist(1)); return [for (final t in rest) ...prefixes(x, t)]; }

concatMap f は concat · map f の略です。prefixes x t は「木 t の中に x を最左の葉として入れるすべての入れ方」のリストを返します。

prefixes :: Int → Tree → [Tree] prefixes x t@(Leaf y) = [Fork (Leaf x) t] prefixes x t@(Fork u v) = [Fork (Leaf x) t] ++ [Fork u′ v | u′ ← prefixes x u]

Dart // x を最左の葉として入れるすべての入れ方。 List<Tree> prefixes(int x, Tree t) => switch (t) { Leaf() => [Fork(Leaf(x), t)], Fork(:final u, :final v) => [ Fork(Leaf(x), t), for (final uPrime in prefixes(x, u)) Fork(uPrime, v), ], };

空リストは扱わないので foldrn を導入

minBy cost は空集合に対しては定義できないので、入力を空でないリストに限定したい。ところが Haskell 標準の foldr は空も許してしまうし、foldr1 は少し不便です。そこで空でないリスト用の畳み込み foldrn を導入します。

foldrn :: (a → b → b) → (a → b) → [a] → b foldrn f g [x] = g x foldrn f g (x:xs) = f x (foldrn f g xs)

Dart // 空でないリスト用の右畳み込み。末尾要素だけ g、それ以外は f で畳む。 B foldrn<A, B>(B Function(A, B) f, B Function(A) g, List<A> xs) { if (xs.length == 1) return g(xs[0]); return f(xs.first, foldrn(f, g, xs.sublist(1))); }

trees = foldrn (concatMap · prefixes) (wrap · Leaf) wrap x = [x]

Dart List<T> wrap<T>(T x) => [x]; // trees を foldrn で書き直す。concatMap は展開して flatten するだけ。 List<Tree> treesFold(List<int> xs) => foldrn<int, List<Tree>>( (x, ts) => [for (final t in ts) ...prefixes(x, t)], (x) => wrap(Leaf(x)), xs, );

木のかわりに「森」を経由する定義

木の話は森（森 = 木のリスト）の言葉で書き直したほうがきれいになる、ということがよくあります。trees もそうで、「森のリスト」を作って各森を巻き上げて木にする、という定義がすっきりします。

trees = map rollup · forests forests :: [Int] → [Forest] forests = foldrn (concatMap · prefixes) (wrap · wrap · Leaf) prefixes :: Int → Forest → [Forest] prefixes x ts = [Leaf x : rollup (take k ts) : drop k ts | k ← [1 .. length ts]] rollup :: Forest → Tree rollup = foldl1 Fork

Dart // 森 = 木のリスト。左脊柱を表す。 typedef Forest = List<Tree>; // 森を左から Fork で畳んで木に戻す。 Tree rollup(Forest ts) => ts.skip(1).fold(ts.first, (a, b) => Fork(a, b)); // x を最左の葉として入れる森版。k で分ける位置を変えて全通り。 List<Forest> prefixesF(int x, Forest ts) => [ for (var k = 1; k <= ts.length; k++) [Leaf(x), rollup(ts.sublist(0, k)), ...ts.sublist(k)], ]; List<Forest> forests(List<int> xs) => foldrn<int, List<Forest>>( (x, fs) => [for (final ts in fs) ...prefixesF(x, ts)], (x) => wrap(wrap<Tree>(Leaf(x))), xs, ); List<Tree> treesViaForests(List<int> xs) => [for (final ts in forests(xs)) rollup(ts)];

キーワード：左脊柱（left spine）この定義では、各森は木の左脊柱を表します。左脊柱とは、最左の葉から根に向かって伸びる経路に沿った右部分木の列のこと。列の先頭は最左の葉そのものです。列を rollup（左から Fork で畳む）すると、もとの木が復元できます。

minBy cost は「非決定的関数」でよい

minBy cost :: [Tree] → Tree に望むのは、「最小コストの木をひとつ返す」ことだけです。

この仕様では出力が1つに定まらないので、minBy cost は非決定的な関数と見ます。実装例は次のとおり。

minBy f = foldl1 (cmp f) cmp f u v = if f u ≤ f v then u else v

Dart // f を評価した値が小さい方を選び続ける（Comparable な値を返す想定）。 T minBy<T, K extends Comparable<Object>>(K Function(T) f, List<T> xs) => xs.skip(1).fold(xs.first, (u, v) => f(u).compareTo(f(v)) <= 0 ? u : v);

しかしこれだと「最小コストで最初に現れた木」を選ぶことになり、入力の順序に依存します。順序に依存しない全順序 ≼ を作って選ぶ手もありますが、それも過度に特殊なので、この章ではminBy cost を非決定的関数のまま扱う方針を採ります。

融合

指数時間を効率化するには

minBy cost · trees をそのまま実行すると、あらゆる木を作ってから最小を選ぶことになり、指数時間かかります。これを速くする定石は、foldrn の融合則を使うことです。

もっとも単純な融合則は、次の等式が成り立つときに使えます。

ただし条件は h (g x) = g′ x と h (f x y) = f′ x (h y) がすべての x, y について成り立つこと。

非決定的関数のための「弱い融合則」

ところが h が非決定的だと、両辺の等号を要求するのはきつすぎます。そこで精緻化（refinement）という関係を使います。

記号 ⇝ の意味 f x ⇝ g x は、f x の可能な出力の集合が、g x の可能な出力の集合を含むこと。特に g が普通の関数なら、「g x は f x の候補のひとつ」という意味になります。

これが成り立つのは、h (g x) ⇝ g′ x（すべての x）で、かつ h y ⇝ y′ ならば h (f x y) ⇝ f′ x y′（すべての x, y, y′）が成り立つときです。

insert を新しい関数として登場させる

minBy cost (foldrn (concatMap · prefixes) (wrap · Leaf) xs) ⇝ foldrn insert Leaf xs

条件は、以下の融合条件をみたす insert が作れることです。

minBy cost ts ⇝ t ⇒ minBy cost (concatMap (prefixes x) ts) ⇝ insert x t (7.1)

つまり insert x t は「prefixes x t の中で最小コストの木を1つ返す」関数です。すると (7.1) は、次の (7.2) が成り立てば導けます。

minBy cost ts ⇝ t ⇒ minBy cost (map (insert x) ts) ⇝ insert x t (7.2)

(7.1) が (7.2) から導ける計算

次の等式（空でないリストからなる空でないリスト上で成り立つ）を使います。

minBy cost (concatMap (prefixes x) ts) = {concatMap を展開} minBy cost (concat (map (prefixes x) ts)) = {上の等式} minBy cost (map (minBy cost · prefixes x) ts) ⇝ {f ⇝ f′ から map f ⇝ map f′ と g · f ⇝ g · f′} minBy cost (map (insert x) ts)

素朴な単調性 (7.3) は成り立たない

cost u ≤ cost v ⇒ cost (insert x u) ≤ cost (insert x v) (7.3)

ただし u, v は同じフリンジを持つ木。ところがこれは成り立ちません。次の反例を見ましょう。

左脊柱にコスト情報が付いていて、どちらの木もコストは 10 で等しい。ここに 8 を挿入すると、

コストが同じ 10 の木でも、挿入後のコストは変わってしまう。よって (7.3) はダメ。

強めた単調性 (7.4) にすればうまくいく

しかし観察してみると、v の左脊柱を下向きに読んだコスト列 [10, 8, 7, 5] は、u の [10, 9, 5] より辞書式順序で小さいことがわかります。そこで比べる量を強めます。

cost′ u ≤ cost′ v ⇒ cost′ (insert x u) ≤ cost′ (insert x v) (7.4)

spine は rollup の逆で spine · rollup = id。cost′ はコスト列を辞書式順序で比べる関数です。xs ≤ ys なら head xs ≤ head ys なので、cost′ を最小化すれば cost も最小化されます。この (7.4) から次が導けます。

これまでの計算をまとめる

脊柱が出てきた以上、脊柱を使った trees の定義に立ち戻ってまとめると次のとおり。

minBy cost · trees ⇝ {精緻化（cost′ にする）} minBy cost′ · trees = {trees を森で書いた定義} minBy cost′ · map rollup · foldrn (concatMap · prefixes) (wrap · wrap · Leaf) = {costs = map cost · reverse と置く} minBy (costs · spine) · map rollup · foldrn (concatMap · prefixes) (wrap · wrap · Leaf) = {下で示す主張} rollup · minBy costs · foldrn (concatMap · prefixes) (wrap · wrap · Leaf) ⇝ {融合則。minBy costs · prefixes x ⇝ insert x} rollup · foldrn insert (wrap · Leaf)

で、spine と rollup が互いに逆であることから直ちに従います。

最適な挿入

挿入前後の脊柱を比べる

図 7.1 の2つの木を比べます。左の木の脊柱は ts = [t₁, …, t_n]。右の木の脊柱は、途中まで rollup してから x を頭にくっつけた形で、Leaf x : rollup (take j ts) : drop j ts になります。それぞれの脊柱にはコスト c_k, c′_k が振られていて、次で定まります。

c₁ は葉 t₁ の値。c′_k も同様の式で j+1 ≤ k ≤ n の範囲で定まります。c′_j > c_j、j+1 ≤ k ≤ n で c′_k ≥ c_k。

どこで切ればよいかの規則

主張最小を実現する j は、1 ≤ j < n の範囲で次を満たす最小の j です。

1 + (x max c_j) < c_j+1 (7.5)

そのような j が存在しないなら j = n を選ぶ。

(7.5) の証明の骨子

(7.5) が成り立てば c′_j = 1 + (x max c_j) < c_j+1。したがって j+1 ≤ k ≤ n で c′_k = c_k となります。もっと小さい i < j でも (7.5) が成り立つとき、列を辞書式で比べると：

[c′_n, c′_n−1, …, c′_i+1, c′_i, x] = {i+1 ≤ k ≤ n で c′_k = c_k かつ i < j} [c_n, c_n−1, …, c_j+1, c_j, … c_i+1, c′_i, x] < {c_j < c′_j} [c_n, c_n−1, …, c_j+1, c′_j, x] = {j+1 ≤ k ≤ n で c′_k = c_k} [c′_n, c′_n−1, …, c′_j+1, c′_j, x]

つまり(7.5) を満たす j は小さいほどよい。反対に j で (7.5) が成り立たないと c′_j+1 > c_j+1 となり、その先も c′_k ≥ c_k となって、コスト列が悪化します。

単調性 (7.4) の証明

木 u, v のコスト cost′ u, cost′ v が等しい場合は、任意の x を入れた後のコストも等しいので明らか。そうでない場合、

とすると、共通の先頭部分（長さ k）を落として、[c_n−k, …, c₁] と [d_m−k, …, d₁]（ただし c_n−k < d_m−k）が残ります。この部分に x を入れた後のコスト列も、u 側のほうが v 側より（辞書式で）大きくならないので、(7.4) が成り立ちます。

insert の実装

(7.5) は x max c_j < cost t_j+1 と同じなので、insert はこう実装できます。

insert x ts = Leaf x : split x ts split x [u] = [u] split x (u : v : ts) = if x max cost u < cost v then u : v : ts else split x (Fork u v : ts)

Dart // 森 ts に x を挿入する。先頭に Leaf x を置き、脊柱の一部を Fork で畳む。 Forest insertTree(int x, Forest ts) => [Leaf(x), ...splitTree(x, ts)]; // (7.5) を満たす最初の位置まで先頭 2 本を Fork でまとめ続ける。 Forest splitTree(int x, Forest ts) { if (ts.length == 1) return ts; final u = ts[0], v = ts[1]; final maxXU = x > cost(u) ? x : cost(u); if (maxXU < cost(v)) return ts; return splitTree(x, [Fork(u, v), ...ts.sublist(2)]); }

最終形：コストを持ち回す

cost の計算を毎回やり直すのは無駄なので、木 t を (cost t, t) の対で持ち回すデータ精緻化を入れると、最終的なアルゴリズムはこうなります。

mincostTree = foldl1 Fork · map snd · foldrn insert (wrap · leaf) insert x ts = leaf x : split x ts split x [u] = [u] split x (u : v : ts) = if x max fst u < fst v then u : v : ts else split x (fork u v : ts) leaf x = (x, Leaf x) fork (a, u) (b, v) = (1 + a max b, Fork u v)

Dart // (コスト, 木) の対で持ち回す最終形。cost の再計算をなくすデータ精緻化。 typedef CT = (int cost, Tree tree); CT leafCT(int x) => (x, Leaf(x)); CT forkCT(CT a, CT b) => (1 + (a.$1 > b.$1 ? a.$1 : b.$1), Fork(a.$2, b.$2)); List<CT> insertCT(int x, List<CT> ts) => [leafCT(x), ...splitCT(x, ts)]; List<CT> splitCT(int x, List<CT> ts) { if (ts.length == 1) return ts; final u = ts[0], v = ts[1]; final maxXU = x > u.$1 ? x : u.$1; if (maxXU < v.$1) return ts; return splitCT(x, [forkCT(u, v), ...ts.sublist(2)]); } // 森全体を Fork で左畳みして最終的な木にする。 Tree mincostTree(List<int> xs) { final forest = foldrn<int, List<CT>>( (x, ts) => insertCT(x, ts), (x) => wrap(leafCT(x)), xs, ); final trees = forest.map((e) => e.$2).toList(); return trees.skip(1).fold(trees.first, (a, b) => Fork(a, b)); }

leaf と fork は「スマートコンストラクタ」で、コストと木の対を組み立てるだけの補助関数です。

線形時間である理由

時間は split の呼び出し回数で測れます。帰納法で示すのは次の主張です。

したがって、このアルゴリズムは線形時間 O(n) で動きます。

最後に一言

貪欲アルゴリズムの難しさ

最小コスト木の問題は、貪欲（greedy）アルゴリズムを組み立てる練習問題です。貪欲法は完成形が単純に見えても、「本当に最適解が得られる」ことの証明が繊細で難しいのが特徴です。

本章の関係の扱いは「軽いタッチ」にとどめ、Haskell 風の記法で押し通しました。より体系的な扱いは Bird and de Moor (1997) を参照してください。

別解：Hu–Tucker / Garsia–Wachs

別のアプローチ最小コスト木の問題は、Hu–Tucker アルゴリズム（現代版は Garsia–Wachs アルゴリズム）でも解けます。詳しくは Hu (1982) や Knuth (1998) を参照。ただしそちらの最良実装はΘ(n log n)なので、本章の線形時間のアルゴリズムのほうが漸近的には速いです。

Dart // 章の代表アルゴリズム mincostTree の動作確認。 String show(Tree t) => switch (t) { Leaf(:final x) => '$x', Fork(:final u, :final v) => '(${show(u)} ${show(v)})', }; void main() { final xs = [3, 1, 4, 1, 5]; final t = mincostTree(xs); print('cost = ${cost(t)}'); // cost = 7 print(show(t)); // ((3 1) ((4 1) 5)) }

参考文献

Bird, R. S. and de Moor, O. (1997). Algebra of Programming. Hemel Hempstead: Prentice Hall.

Hu, T. C. (1982). Combinatorial Algorithms. Reading, MA: Addison-Wesley.

Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Searching and Sorting, second edition. Reading, MA: Addison-Wesley.

どんな問題？