農地の生産効率を最大にする～組み合わせ最適化問題に挑戦

2023.09.29X5:プログラミングコンテスト

第10回プログラミングコンテスト

　アスプローバ社主催の第10回プログラミングコンテストが、2023年9月に行われました。今回の問題は、定められた面積の農地を効率的に用いて、多くの作物を収穫するプログラムを作ることです。参加者には約１週間の期間が与えられました。そして9月22日、東京・五反田のアスプローバ本社で、表彰式と懇親会が開かれ、賞金が贈呈されました。席上、上位入賞者が解法を説明し、盛んな質疑応答がありました。800人を超える参加者から回答が寄せられました。これまでのプロコン史上最多だったといいます。

　田中智宏社長は開会のあいさつで、こう話しました。「私たちの会社は、工場の生産計画を最適にするプログラムを作っており、日々、工場から寄せられる問題を解いています。それはコンテストより難しいかもしれません。できればみなさんのように、この分野を得意とする人に仲間に加わってもらい、一緒に挑戦したいと思っています」

　さて今回の問題では、農地が正方形の区画に区分されていて、区画と区画の一部は水路になっています。この土地を使って各種の作物を栽培します。作物を植えたり収穫したりするときは、農機を使います。農機は栽培されていない区画だけを通って移動します。目標は、なるべく多くの区画を有効に利用できるような計画を立てることです。得点は、各種作物の栽培期間の累計を、面積と期間の積で割ったものとします。

　アスプローバ社の本業である工場の生産計画にあてはめると、作業場所を確保し、効率的な生産をする方法の探索につながります。一種の「詰め込み問題」と考えることもできます。

　出題者であるアスプローバのエンジニア、小島健介さんは「組み合わせ最適化の問題を解くのにはさまざまな方法がありますが、今回は『焼きなまし法』では解けないだろうという問題を作りました。ただコンテストの途中で、予想よりも高い得点が出ていたので、何か想定よりも良い解法がありそうだと思っていました。それがどんな方法かは分かっていませんでしたが、コンテスト終了後に焼きなまし法が使えることが分かりました」と話します。出題者も驚く高得点で、参加者のレベルの高さが示されました。

　焼きなまし法とは、解を繰り返し求め直して、よりよいものを見つけていく方法です。たださまざまな条件を満たさないと、うまくいきません。上位入賞者は、解法を次の通り説明してくれました。

3位　saharan(サハラ)さん

　当初は「ゴミ」のような結果しか出ませんでした。問題を解く過程で、２つの重要な気づきがありました。１つは、植え付けの開始時期をばらばらにしていたのを、一斉にしてみたことです。これによって、焼きなましを適用できる状態にすることができました。もう１つは、通路を含めて焼きなましをするということに気付いたことです。そのうえで、利用率の低いところを改善したり、高速化の方法を探ったりして、何とか3位に入ることができました。楽しくできたと思います。

2位　hogloid(ホグロイド)さん

　初めは貪欲法で着手し、とりあえずの解を求めました。通路を作っていく際、（グラフ理論で言う）次数が多い方を優先し、さらに曲がったところが少ないものを選んでいきます。次数の多さは、多くの区画に隣接しているということになります。曲がりが多いと遠回りになって通路が増えるので、よくないのです。5日目くらいから、その初期解を焼きなましによって改善していきました。いつどこで収穫するかを反復改善していきます。私はヒューリスティックコンテスト（正解・不正解だけでなく、解の良さでスコアが変わるタイプのコンテスト）にはあまり参加したことがなく、今回はいい勉強になりました。

　優勝したsugim48（スギム）さんは、体調不良でご欠席でした。

　アスプローバ社では、今後もプログラミングコンテストを通じて、優れたプログラミング技能者を発掘、顕彰し、プログラミング技法の進歩に貢献したいと考えています。

（了）