10/13 の問題、アルゴリズム発見しました。"Algorithms for the Shortest and Closest Lattice Vector Problems" (pdf) の 22 ページ "The Enum Algorithm"。題意が少し違っていて、「a, b, c を一次独立な空間ベクトル、d を任意の空間ベクトル、r を正の実数とするとき、| na + mb + kc - d | が r 未満になる整数値 n, m, k を列挙せよ。」となっている。実は欲しいのはこの問題の解だったので、ちょうどよかった。Molby 内蔵の Ruby インタプリタで実装してみました (enum_close_vectors.rb)。一応動いているみたい。
タグ：ソフトウェア
