正方形への円の詰込み問題の発見的解法

正方形への円の詰込み問題の発見的解法
南山大学数理情報学部数理科学科
鈴木敦夫
概要
n 個の等しい半径の円を単位正方形内に詰め込むことができる
ときに，その半径の最大値を求める問題を考える。本論文ではこの
問題を最適化問題として定式化し，非線形計画法の反復解法を用い
て解を求める。そのとき，反復解法の初期値として，ある規則で作
成したボロノイ図の母点を採用する。これによって，ごく少ない手
間で品質の良い解を求めることができることを数値例により示す。
1 はじめに
n 個の等しい大きさの円を単位正方形内に詰め込むことができるとき
に，その半径の最大値を求める問題は，幾何学上の未解決問題として，長
い間，数学者の研究対象となってきた。[1]D1 では n が 27 までのその時
点での最良の値が与えられている。その後，[5] では，n が 20 までの最適
値（厳密な意味での）が証明とともに与えられた。[5] の算法，および証
明では，計算機を用いて組合せ的な方法を用いるので, 計算時間の制約か
ら n が 20 までしか解は求められていない。[3] ではこの問題を，エネル
ギー関数を最小にする問題に定式化し，非線形計画法の手法を用いて解
いている。この方法で近似解を n が 20 から 50 まで求めている。
本研究では，問題を [3] より単純な非線形計画法に定式化し，MATLAB
の最適化ツールを用いて解く。その際，反復の初期値として，ある規則
で求めたボロノイ図の母点を用いる。この規則とは，[2] で地理的最適化
問題の解として紹介されたものである。これは，単位正方形内に n 個の
単位正方形内に利用者が一様に分布し，その利用
施設を配置するとき, 者が最も近い施設を利用するという仮定の元で，利用者の平均移動距離
を最小にする施設の配置をあらわしている。ボロノイ図の紹介，この地
本研究の一部は科学研究費（基盤研究（ C ）(2)，11680458 ）の援助を受けた。
1
図
1:
地理的最適化問題で得られたボロノイ図の一例，n = 15
理的最適化問題の紹介は [4] 第 2 章，第 3 章にある。図１にこの規則で得
られたボロノイ図の一例を示す。図中の白丸がボロノイ図の母点，即ち,
我々の算法の初期点である。また，実線はボロノイ図と単位正方形，破
線はボロノイ図の双対図形であるドローネ三角網をあらわす。我々の方
法によると，ごく簡単に品質の良い解が得られる。例えば，n が 15 の時
には，[1] にあげられているものより良い解が得られた。
本論文では，第 2 節で問題の定式化と解法を，第 3 節で得られた解に
ついて述べる。第 4 節ではまとめと今後の展望について述べる。
2
問題の定式化と解法
問題の定式化にあたっては以下の記号を用いる。
S : 単位正方形
SB : S の境界
n : 単位正方形内に詰め込む円の個数
xi : i 番目の円の中心
Dn : xi (i = 1; :::; n) を母点とするドローネ三角網
(
(
):
):
と xj のユークリッド距離
d xi ; SB
xi と S の境界とのユークリッド距離
円の詰込み問題は，２円の中心間の距離，円と単位正方形の境界との
距離の最小値を最大にする問題として定式化される。即ち，
d xi ; xj
xi
max min[ min
(
2
(i;j )
st
: :
n
D
xi
) min (
d xi ; xj ;
2
S;
i
i=1;:::;n
=1
d xi ; SB
)]
; :::; n
ただし，(i; j ) は xi と xj を端点とする枝をあらわしている。このような
ミニマクス問題の解法は MATLAB の最適化ツールの組込関数 fminimax
として与えられており，これを使うことによって解を手軽に求めること
ができる。もちろん解の品質は，問題の特質を生かした解法を独自に考
案するほうが良いものが期待できるが , それには時間と手間がかかる。そ
れと比較して MATLAB を用いると，数十行のプログラムでかなりの品
質の解が得られる。またそれにかかる時間もおそらく数十分の一であろ
う。本論文では，ミニマクス問題の解法は MATLAB を用い，初期解，計
算の手間を減らす工夫をボロノイ図もしくはその双対図形であるドロー
ネ三角網を用いて行なう。
まず，初期解であるが，この目的関数は凸関数ではないので , 得られる
解は局所最適解である。このような場合，初期解の選び方によって，得
られる解の品質が変わる。また初期解によって，解法にかかる時間も大
きく変わる場合が多い。ここでは，初期解として，[2] で提案された地理
的最適化問題の解を採用する。これは，ボロノイ図の母点を，そのボロ
ノイ領域の重心に移動することを繰り返して得られた母点の位置である。
図 1 がその一例であるが，これを見ると，母点が正方形内に均一に配置さ
れている。また，各ボロノイ領域の内接円を作り，そのうちの半径最小
のものをとると，これは，円の詰め込み問題の近似解になっている。こ
の母点を初期値として用いることで，良い品質の解が短時間で求められ
ることが期待できる。
次に目的関数の第 1 項について考える。この項では，隣接する点間の
距離の最小値を求めているが，ドローネ三角網を用いなければ，すべて
の 2 点の組合せについて，その距離を求めなければならない。即ち n2 の
手間がかかる。ここでは，ある点に最も近い点は，ボロノイ領域で隣り
合う点の中にあるという性質 [4] を用い，この手間を点の数に比例する手
間に減らしている。
表
3
1: 計算結果：得られた解と厳密解 [5] との比較
n 近似解厳密解 [5] 比 (%)
10 0.2879 0.2964 97.12
11 0.2847 0.2847 99.96
12 0.2708 0.2799 96.74
13 0.2629 0.2679 98.10
14 0.2558 0.2586 98.89
15 0.2530 0.2543 99.47
16 0.2500 0.2500 100.0
17 0.2326 0.2343 99.23
18 0.2238 0.2310 96.86
19 0.2232 0.2245 99.40
20 0.2162 0.2227 97.05
平均
98.44
計算結果
1
2
表１，表２に計算結果を示す。表中第列は円の個数 n を，第列は
我々の計算で得られた詰め込まれた円の最大直径（近似解）を，第列
は表では n が
までので示された厳密解を，表２では，n がか
までの
で示された最良解（これは必ずしも厳密解ではない）を
ら
示している。第列は我々の近似解と厳密解，最良解の比を表している。
のときの解（白丸）と，それらを母点とするボロノ
図には，n
イ図を示す。この解は図１を初期解として求めたものである。
1
25
[3]
2
表
20
[5]
4
= 15
2: 計算結果：得られた解と最良解 [3] との比較
n 近似解最良解 [3] 比 (%)
21 0.2137 0.2137 100.0
22 0.2071 0.2113 97.99
23 0.2052 0.2056 99.80
24 0.2019 0.2027 99.57
25
0.2
0.2 100.0
平均
99.47
3
21
図
2:
得られた解（白丸）とそれらを母点としたボロノイ図，n = 15
初期解の計算は，Sun SPARCStation 上の FORTRAN77 でプログラム
し，計算時間は n = 25 の場合で数秒であった。ミニマクス問題を解くの
には，Toshiba Dynabook SS 3410（ Intel 社製モバイル Celeron プロセッ
サ，クロック 400MHz ）上の MATLAB Version 6, Release 12 でプログラ
ムし，計算時間は n = 25 の場合で約 1 分であった。
我々の方法によると，非常に品質の良い近似解が短時間で求められる
ことがわかる。
4
まとめ
円の詰め込み問題は，円の個数が大きいときには未解決の問題である。
近似解法が [3] で提案されているが , 我々の解法は解の品質でそれに迫り,
計算時間では [3] では明示されていないものの，[3] よりもかなり短いもの
と思われる。
今後の課題としては，現在は初期値を 1 通りだけ決めているが，いく
つかの初期値を採用して解を求め，その中で最良のものを解とする，い
わゆるマルチスタートによって，より良い品質の解が求められる可能性
を検証することがあげられる。
参考文献
[1] H. T. Croft, K. J. Falconer and R. K. Guy, Unsolved Problems in
Geometry, Springer-Verlag, New York, 1991. (日本語訳：秋山仁
訳，幾何学における未解決問題，シュプリンガー・フェアラーク東京，
1996 ）.
[2] M. Iri, K. Murota and T. Ohya, A Fast Voronoi Diagram Algorithm with applications to Geographical Optimization Problems, in
P. Thoft-Christensen (ed.), System Modelling and Optimization (Proc.
11th IFIP Conf. on System Modelling and Optimization, 1983, Copenhagen), Lecture Notes in Control and Information Sciences, Vol. 59,
1984, Springer-Verlag, Berlin, pp.273-288
[3] K. J. Nurmela and P. R. J. O stergard, Packing up to 50 Equal Circles
in a Square, Discrete and Computational Geometry, Vol.18, pp. 111120, 1997.
[4]
岡部篤行，鈴木敦夫，最適配置の数理，朝倉書店，1992．
[5] R. Peikert, D. Wurtz M. Monagan and C. de Groot, Packing Circles
in a Square: A Review and New Results, in P. Kall(ed.), System Modelling and Optimization (Proc. 15th IFIP Conf. on System Modelling
and Optimization, 1991, Zurich), Lecture Notes in Control and Information Sciences, Vol. 180, 1992, Springer-Verlag, Berlin, pp. 45-54.
連絡先：南山大学数理情報学部数理科学科 [email protected]

Download Report