トップ 差分 一覧 ソース 検索 ヘルプ PDF RSS ログイン

NHC秋学校 Integer Programming の講義の復習3

次元を固定した整数計画法の多項式時間アルゴリズム

整数計画法とアルゴリズム的数論

いきなり話が脇道にそれる。脇道にそれたことに気づかないと、「なんで突然 gcd の話が出てくるんだ?」ということを思ってしまう。

この節の結論から先に話すと、

整数計画法はアルゴリズム的数論とは切っても切れない仲である。

ということを言いたいだけである(と思う)。

さて、2数の最大公約数を求めるアルゴリズムはご存知だろう。人類史上、最も古いアルゴリズムであるユークリッド互除法である。これとは別の方法で最大公約数を求めてみよう。

数論のよく知られている結果で、

(*) 整数 a, b の最大公約数は、z = ax + by, z >= 1 の最小値と等しい。ただし、x, y は整数である。

というものがある。これを使うと、

整数計画法

minimize  ax + by
subject to ax + by >= 1, x, y は整数

を解けば、それが a, b の最大公約数となる。

このように、整数計画法を使えば、数論のさまざまな結果を計算したり、証明したりできる。

おまけ (*) の証明(のスケッチ)

8 と 12 の最大公約数を考えよう。z = 8x + 12y はどうがんばっても z = 1, 2, 3 にはならないのはすぐにわかる。z = 4、すなわち 8x + 12y = 4 を満たす x, y が存在することをいう。式を 4 で割ると、2x + 3y = 1 となり、整数論で有名な定理

ax + by = 1 で、a, b が互いに素なら、この式を満たす整数 x, y は存在する。

が使える。したがって、8 と 12 の最大公約数は 4 である。手計算で確かめてみると、8 = 2 * 4、12 = 3 * 4 なので、確かに正しい。

では、この定理はどう証明したらよいかというと、拡張ユークリッドアルゴリズムを使えばよい(省略)。

Lenstra のアルゴリズム

話を元に戻そう。ある多面体が与えられたとき、多面体の中に整数点が存在するかどうか判定する問題を考えよう。これは、整数計画法の制約条件が多面体になっているとき、その整数計画法が解を持つかを調べる問題に相当する。解を持つことを英語で feasible であるという。

この問題に対して Lenstra のアルゴリズムという有効なアルゴリズムがある。概要を説明しよう。多面体がどの方向にもある程度以上太ければ、必ず整数点を含みそうである。例えば、3次元で1辺が10の立方体が必ず整数点を含むのはすぐにわかる。問題になるのは、細い板のように、ある方向の長さが小さい場合である。例として、3次元で、x_3 の範囲が 0〜3 に納まっている多面体 P を考える(任意の x ∈ P について、0 <= x_3 <= 3 が成り立つ)。アイデアは、P を x_3 方向に垂直な(x_1 x_2 平面に平行な)平面でスライスすることである。具体的には x_3 = 0、x_3 = 1、x_3 = 2、x_3 = 3 の4つの平面で P を切る。当たり前であるが、P の整数点は(含むとすれば)すべて 4 つのスライスした平面のいずれかに必ず含まれる。したがって、この平面について、整数点を含むかどうか調べればよい。一般の次元で話をすると、n 次元空間をいくつかの「平面」(n-1 次元空間)にスライスし、いずれかの平面が整数点を含むかどうか調べればよい(これは再帰的に行える)。

解決の必要な問題点が2つある。1つは、多面体がどの方向にもある程度以上太ければ、必ず整数点を含むことを保証しなければならない。これは Flatness 定理を用いる。もう1つは、多面体が「斜め」に置かれている場合を考える必要がある。例えば、細い棒が斜め(x_1 軸と45度の角度)に置かれているなら、x_1、x_2 の両方とも長く見える(a <= x_1 <= b の [a, b] 間が長い)が、棒と垂直な方向から見ると短い(ので整数点を含まない可能性がある)。この場合、x_1 (x_2)軸に平行な方向にスライスすると効率が悪いので、斜め(棒と平行な方向)にスライスするのが良い。

ここまでの背景がわかっていれば、以降、多少複雑な式が出てきてもなんとか追っていけるだろう。

以下、工事中

NHC秋学校2007サポートページトップに戻る