プログラム・プロムナード：円周上の点による最大面積多角形

全文

(1)[email protected]. 今回の問題は，2000 年 11 月につくばで開催されたアジア地区予選の問題 G, Telescope である．. また，2 点 i, j が与えられた時に，円の中心とそれらの点から構成される二等辺三角形の面積を求める. 半径 1 の円周上に n 個の点が与えられる．そのうちの m 個を選んで作られる多角形（m 角形）のうちの. 関数 double area(int i, int j). 最大面積を求めるのが問題である．n, m はあらかじ. も定義してあるとする．この面積の求め方は親切に. め与えられ，さらに各点の位置は 0 p 1 なる実数. も問題文中に示されており，. 値として与えられる（1 は一周，すなわち 360 度を表す）．問題の規模は 3 m n 40 となっている． -1 に問題の解答例を示す.. sin((p[j]-p[i])*2*PI)/2. である（標準ライブラリ関数 sin の引数の単位はラジアンである）．. 最も単純に考えると，n 個の点から m 個を取り出す組合せをすべて生成し，その面積を求めて最大値をとればよい．しかしそのような組合せは n C m . この準備があると，3 点 i, j, k（反時計回り順）で囲まれる三角形の面積は area(i,j)+area(j,k)+area(k,i). n!(m!(nm)!)であり，これはつまり n の指数オーダ. として求めることができる．ここで注意しなければ. の時間を要することになる．実際，この問題の規模. ならないのは，この三角形が円の中心を含まない場. では 40C20 1.4 . 合である．そのときには上式の 3 項のうちいずれか. 1011. だから現在の計算機でそのま. ま計算するのは時間的に少し苦しいことになる（問題. 1 つが負になるが，その正当性は. の規模さえ十分小さければ，こういった力任せの方. かである．ところで，問題文中に示された面積の求. 法も悪くはない）．. め方では，2 点のなす角が 180 度未満の場合のみを紹. -2 を見れば明ら. このような指数オーダの時間を要する組合せ問題の計算量をいかに減らすか，が今回のテーマである. P1 P2. 実際の問題では，入力データの形式が決まっており，それに合うようにプログラムすることも重要な課題である．しかし，本稿では本質的部分に集中で. P0 P3. きるように，入力データはすでに変数に格納されているとする．. P4 -1 n5, m3 のときの解の例を示す．黒丸は採用した点，白丸は採用しなかった点を表す．. 664. 43. 6. 2002. 6. −1−.

(2) j. O. j (a) i. O. j i. (b). k. i O (c). k -2. k. ijk. 求める多角形 ijk の面積(a)は，Oij, Ojk, Oki の面積の和となるが，Ojk の面積(c)は j, k のなす角が 180 度以上あるため負となり，符号なしで考えると OijOki の面積(b)から(c)を引いたものが(a)となる．. 介してあるだけで，このように 180 度を越える場合には面積が負になることがあることには触れていない．このことはのちのち重要な意味を持ってくるのだが．作成目標である最大面積を求める関数は double calc(void). とすることにしよう. なお，本稿では「n 番目」とある場合，先頭を 0 番目と数えることとする．また，以下のプログラムでは，最大値，最小値，絶対値を求める MAX, MIN, ABS なるマクロを使っているがこれらはしかるべく定義されているものとする．. 1. &. 関数 place(mi,ni)は，mi 番目の採用点として ni 以降を候補とした時の最大面積を返す関数である．. まず，最も単純にすべての組合せを生成しては面積計算を行うプログラムを示す．. 内部では，点 ni を見送るか採用するかで 2 通りの再帰呼出に分岐し，そのうちの大きい方を返すことにしている．各点の採用状況は大域配列 nodes[]に記録していき，再帰末端の面積計算で利用する．このプログラムは明らかに指数オーダを必要としている．. 2 前章のプログラムは大域配列を使用しており引数だけでは値が定まらず，このままでは改良が難しい．そのため，指数オーダには違いがないのだが別の書き方のプログラムを導入する． mi 番目の採用点 ni までの採用状況が定まっていてその次の採用点を選ぶ状況を考える．あと (mmi1) 個の採用点を選べばよい．次の採用点 nj. IPSJ Magazine Vol.43 No.6 June 2002. −2−. 665.

(3) node0. node0. node0. 0. 0. 0. ni. ni. ni. nj. nj. nj -3. 点 ni から終端点 node0 までの最大面積を求める．ni とその次の採用点 nj の部分（色の濃い三角形）と，nj から先の部分（色の薄い扇形）に分け，後者は再帰呼出によって最大面積を求める．それらのうちで和が最大面積を与える nj を採用する．. を，ni のすぐ次(ni1)から始めて順次あとの点を候補とする. nj から先は再帰的に最大面積が求まるとして，ni と nj の一区間の面積と，再帰的に求まった nj から先の面積の和が ni からの面積となり，これを最大化すればよいことになる（. -3）．. この問題では，最初の採用点から始めて一周する形で計算を進めるので，区間の終端点はすなわち最初の採用点となり，これは計算を通じて固定できる．そこでこれを node0 なる大域変数に保持することにする．関数 place は，mi 番目の採用点として ni を選んだ時の最大面積を返す関数である．最初の採用点 node0 は最も外側のループで制御する．. このプログラムでは，最大面積の初期値として，0 ではなく-PI を与えている．これは求めているのが部分面積であるから前述のとおり負になることがあり得るためで，ここを 0 としてしまうと間違った答になってしまう．. 3 前章のプログラムの実行効率が悪い原因は，同じ関数を何度も評価していることにある．実際，引数である mi, ni はそれぞれ m, n で抑えられるのであるから，異なる呼出は高々 node0 ごとに nm 種類しかない．この関数の値は，引数で完全に決定されるので，関数の呼出結果を表に記憶することを考える． 2 次元配列 double memo[NMAX][NMAX]を用意し, 初期値としては「未計算」を表す特別な値を入れて. 666. 43. 6. 2002. 6. −3−.

(4) おく．計算関数 place が呼ばれると，まず引数をキーとして memo 配列の該当する場所をチェックし，すでにその引数の組について計算済みであればその値を直ちに返す．「未計算」の値が見つかった場合には前項の処理を正直に行って値を計算し，memo 配列に格納する．この方式によれば，place 関数の呼出は引数の組に対して高々 n 回だけになり，全体の計算量は n3m で抑えられることになる（引数の組が nm だけあり， 1 回の呼出によって下請け関数が n 回呼び出される. さらに，初の採用点 node0 の選び方が n 通りある）．こうした手法を. tabulation と呼び，古典. 的な高速化手法の 1 つである．. 4 単純再帰プログラムでは,. （1）のように再帰的な定義を行った．ここで，前項と同様に関数呼出し place(mi, ni)を配列要素 memomini に対応させれば，これは関数呼出の関係ではなく，配列要素間の関係を示す漸化式とみることができる．. このように，再帰的な関数の結果を順序よく表に. memomini の値そのものは前項と同じ値となるが，. 収めていくことによって計算を効率化する手法を. ここではさらにその具体的な計算順序が与えられた. dynamic programming と呼ぶ．. ことになる．漸化式. 動的計画法が適用できる問題の特徴は，与えられた問題を小さいサイズの問題に分解した時に，その（2）. 親問題の解が子問題のいずれかから得られる点である．. にしたがって，mi の最大値 m1 から始めて 0 に向. この問題のような組合せ最適化の問題では，動的. かって計算していけばよい．この場合にも，プログ. 計画法が適用できるかどうかを判断するのが重要で. ラム全体の計算量は. n3m. で済む．. この問題の場合，さらに空間的な計算量を減らすことが可能である．式（2）から，memo の第一の添字. ある．その意味では，プログラム 2 を思いついた段階で動的計画法の要件を満たしているということができる．. に注意すると，1 つ先の行だけを使って計算している. この問題について，動的計画法の適用に失敗する. ことが分かり，ある行の計算が終了すると先の行は. 考え方をあげよう．面積最大 m 角形を作る際に，面. 不要になる．さらに，1 行の中で ni の要素を求める. 積最大 m1 角形を出発点とし，それにいずれか 1 つ. には ni1 から先だけを使っている．以上をまとめる. の新しい頂点を加えることで面積最大 m 角形としよ. と，mi を m1 の行から始めて，行内では ni を最も. うとするのである．この考え方がうまくいかないの. 小さい値から始めていけば，memo 配列は 1 次元で済. は，正方形と正三角形が重なった点が与えられた場. むことになる．. 合，正三角形に新しい 1 点を加えることによっては. 以上を反映させたプログラムを次に示す.. 正方形は作れないことを考えると分かる．親問題の解（正方形）には，子問題の解（正三角形）は含まれ. IPSJ Magazine Vol.43 No.6 June 2002. −4−. 667.

(5) (a). (b). (c). -4 ni も含めた残りの点の総数 nni は 3，採用すべき点の数 mmi は 2 の場合．. ていないのである．. て大きい（甘い）上界であって，採用する必要はない．（2），（3）はデータによってどちらがより小さい（き. 5. びしい）かが決まるので，両方を計算してその小さい方を採用するのが妥当だろう．. この問題については，前章の動的計画法が最適な. 探索の順序が重要になる．結果の良い枝を先に探索. 思う．. しておくと，早期によい暫定解を手に入れることが. しかし，ここではさらに別の手法によって，動的. できるので，それ以降の枝を有効に刈りとることが. 計画法を用いずに単純再帰を高速化することを考え. 可能になる．プログラム 2 では，次の採用点 nj を現. よう．こうした探索の高速化は，状態空間（関数に与. 在点 ni の次から順に探索していたが，これを「より. えられる引数の組）が大きすぎて索表や動的計画法が. 見込みのある」ものを先にするように並べ替えるので. 適用できない場合などに使われる．. ある．この問題では，正多角扇形が面積最大である. branch-and-bound method を適. 用する．これは状態空間を全探索する場合に，「明らかに見込みのない枝」を探索候補から除外していくことで探索の高速化をはかるものである．枝を刈ることによって，その先に展開される膨大な（意味のない）計算を省けるので，状況によってはきわめて有効な方法である．「明らかに見込みがない枝」とは，その枝の先でいかに良い結果が出たとしてもそれまでの最高記録（暫定解）を更新し得ないということで，ある種の上界を計算することになる．また，この判断は十分高速に（すなわち，探索によることなく）行う必要がある．この上界をどう（きびしく）定めるかがポイントで，この問題の場合，mi 番目の採用点を ni とした時の，その先の最大面積の上界として，たとえば（1）ni から終点までの円弧による扇形（. -4（a））. （2）ni から終点までのすべての点から作られる (nni)角扇形（. -4（b））. （3）ni から終点までの正(mmi)角扇形（. -4（c））. などが考えられる．明らかに（1）は（2），（3）に比べ. 43. pruning を導入すると，今度は. 解であり，出題者もおそらくそれを想定していると. まず，. 668. このような. 6. 2002. 6. −5−. ことに着目して，残り角度の平均値に近い nj から探索するのがよいだろう．.

(6) これらの手法の効果を，コンテストの問題に付加されているサンプルデータについて計測してみる． n30, m15 の問題に対して，単純再帰のプログラムにおける place の呼出回数は 614429671 であったが，枝刈りを導入することで 60916 に激減し，さらに探索順序の変更によって 15119 にまで減少している．しかし残念ながら，この上界では n40 というコンテストの最大サイズでは計算が終了せず，より精密な上界の評価が必要である．. 動的計画法を頂点とする，組合せ的な探索問題の最適解を求めるためのアプローチを紹介してきた．これとは別に，最適性を犠牲にしても短時間でそれなりの解を求めるアルゴリズムが各種存在する．状態空間が巨大すぎる場合や，解の最適性にそれほどの意味がない場合などにはそうした方法が適用可能である．プログラミングコンテストの観点から見れば，問題のサイズによってどのようなアプローチをとるべきかがほぼ決まってくるので，そこを見抜くのが 1 つの鍵となるであろう（現実の問題ではかならずしもそれほど単純ではあり得ないが...）．（平成 14 年 5 月 10 日受付）. IPSJ Magazine Vol.43 No.6 June 2002. −6−. 669.

(7)