C++プログラム：二分木における最大独立集合（LIS）のサイズを求める方法

この記事では、与えられた二分木（バイナリツリー）における最大独立集合（LIS：Largest Independent Set）のサイズを求めるC++プログラムを紹介します。

独立集合とは、木の中で互いに隣接していない（親子関係にない）ノードだけで構成される集合のことです。つまり、「選んだノード同士が直接つながっていない」という条件のもとで、できるだけ多くのノードを選ぶ問題を解きます。

アルゴリズム

この問題は、動的計画法（メモ化再帰）を用いることで効率的に解けます。各ノードについて「そのノードを含まない場合」と「そのノードを含む場合」の2通りのサイズを計算し、大きい方を採用します。

開始。
　　構造体nを作成し、データd、左の子ポインタl、右の子ポインタrを宣言する。
　　2つの整数のうち大きい方を返す関数max()を定義する。
　　与えられた二分木における最大独立集合のサイズを返す関数LIS()を作成する。
　　現在のノードを含まない場合のサイズを計算する
　　int size_excl = LIS(root->l) + LIS(root->r)
　　現在のノードを含む場合のサイズを計算する
　　int size_incl = 1;
　　if (root->l)
　　　　size_incl += LIS(root->l->l) + LIS(root->l->r)
　　if (root->r)
　　　　size_incl += LIS(root->r->l) + LIS(root->r->r)
　　2つのサイズのうち大きい方を返す
　　新しいノードを生成する関数newnode()を作成する。
終了。

最適化のポイント

各ノードには計算済みのLIS値を格納するフィールドを持たせています。一度計算した結果はキャッシュとして再利用されるため、同じ部分木を繰り返し計算する無駄がなくなり、計算量が大幅に削減されます。

サンプルコード

#include <iostream>
using namespace std;
struct n {
    int d;
    int lis;
    struct n *l, *r;
};
int max(int x, int y) {
    return (x > y) ? x : y;
}
int LIS(struct n *root) {
    if (root == NULL)
        return 0;
    if (root->lis)
        return root->lis;
    if (root->l == NULL && root->r == NULL)
        return (root->lis = 1);
        int lis_excl = LIS(root->l) + LIS(root->r);
        int lis_incl = 1;
    if (root->l)
        lis_incl += LIS(root->l->l) + LIS(root->l->r);
    if (root->r)
        lis_incl += LIS(root->r->l) + LIS(root->r->r);
        root->lis = max(lis_incl, lis_excl);
        return root->lis;
}
struct n* newnode(int d) {
    struct n* t = (struct n *) malloc(sizeof(struct n));
    t->d = d;
    t->l = t->r = NULL;
    t->lis = 0;
    return t;
}
int main() {
    struct n *root = newnode(30);
    root->l= newnode(20);
    root->l->l = newnode(10);
    root->l->r = newnode(7);
    root->l->r->l = newnode(9);
    root->l->r->r = newnode(6);
    root->r = newnode(50);
    root->r->r = newnode(26);
    cout<<"Size of the Largest Independent Set is "<< LIS(root);
    return 0;
}

実行結果

Size of the Largest Independent Set is 5

この例の二分木では、値が30・10・9・6・26である5つのノードを選ぶことで、互いに隣接しない最大の独立集合が得られます。