飲料工場が舞台、最適化の手順競う~プログラミングコンテスト飲料工場が舞台、最適化の手順競う~プログラミングコンテスト2024.10.21X5:プログラミングコンテスト第11回プログラミングコンテストアスプローバ社主催の第11回プログラミングコンテストが、2024年9月に行われました。今回の問題は、炭酸飲料の工場が舞台です。甘さと炭酸の強さが異なった飲み物を、効率よく作る手順を見つけることです。4時間の制限時間の中で得点を競いました。解法を説明し、盛んな質疑応答がありました。田中智宏社長は開会のあいさつで、「私たちの会社は、ウインドウズ95の時代から工場の生産スケジューラを作っており、国内だけでなく、海外でも1500本を売り上げました。メイド・イン・ジャパンのソフトウェアは珍しい存在です。今、次世代のスケジューラを開発しており、それはヒューリスティック(人間の思考過程に近い発見的手法)を中軸にしていて、海外でも注目されています。興味があったら仲間に加わってください」と話しました。貪欲法でやってみると...さて今回の問題では、ある飲料工場で、シロップと炭酸水を混ぜ合わせることで炭酸飲料を作ります。それぞれの炭酸飲料は、甘さと炭酸の強さで表現されます。初めは甘さも炭酸も「0」の炭酸飲料だけを持っていますが、操作を行うことで他の炭酸飲料を作成することができます。指定された「甘さ」と「炭酸の強さ」を持つ炭酸飲料を作るには、すでに作った飲料にシロップや炭酸水を追加します。加えた分の甘さや炭酸の強さによってコストがかかります。甘さ2、炭酸5の飲料を作るには、甘さ0、炭酸0の炭酸飲料に甘さを2足して、炭酸を5加えます。コストは「足した分の甘さ+炭酸の量」。この場合は「2+5=7」です。N種類の炭酸飲料を作るために、5N回以内の操作を行うことができます。指定された炭酸飲料を作るための操作列の中で、コストの総和が最も小さいものを見つけることが目標です。問題の狙いを一言で示すと、「まとめてできる処理をまとめてやる」ということになります。工場の生産計画ではよくみられる方法です。参加者は「組み合わせ最適化」のさまざまな手法を駆使して、問題に挑みました。多くの参加者が採用したのは「貪欲法」(どんよくほう)でした。後先のことを考えず、その場その場での最善の選択を繰り返していく手法です。4位に入賞したspawn(スポーン)さんは、こう説明しています。クエリ逆順でマージする方針です。x+y(甘味+炭酸)の大きい方からマンハッタン距離(この場合はコスト)で一番近いものとマージするのを繰り返して解を構成します。これだけだと自明なロスがあったので、今度は順向きに見ていって他の辺の利用を探索します」「クエリ逆順マージの方針に気づいたのと、スコア計算から、できるだけ近い2点をマージするとお得と気づいたのがよかったですね」。spawnさんはITスタートアップのデータサイエンティストで、プログラミングコンテストでの賞金獲得は初めてだそうです。スコアの95%は貪欲法で達成し、残りの5%は山登り法でコスト削減を試みました。最初に良い方針が出たので、それを軸に最後まで進めました。運が良かったと思います」とコメントしました。uwiさんは7歳からプログラミングを始めた実力者で、これまでに多くのプログラミングコンテストに参加してきましたが、現在は子育て中のため「夜のプロコンは厳しい」と語っていました。出題者であるアスプローバのエンジニア、小島健介さんは「今回の問題はシンプルですが、意外に難しいものです。4時間という制限時間もあるので、貪欲法で着手したくなります。実は、焼きなまし法を採用するとうまく行きます」と述べました。焼きなまし法とは、解を繰り返し求め直して、よりよいものを見つけていく方法で、ヒューリスティックと共通した考え方です。アスプローバ社では、今後もプログラミングコンテストを通じて、優れたプログラミング技能者を発掘、顕彰し、プログラミング技法の進歩に貢献したいと考えています。(了)技術革新や予測不能な外的要因に迅速に対応できるよう製造業務においては、より一層生産プロセス全体の改善と生産効率向上が求められています。データやデジタル技術を活用し、生産リードタイム短縮や在庫・コスト削減などを実現する製造現場におけるDX推進の一つとして、生産スケジューラの導入がカギとなります。次のページでは、生産スケジューラ導入によって具体的にどのような業務改善が実現したのか導入企業の事例もご紹介しています。ご参考にしてください。Corporation.アスプローバ。