【アルゴリズムチーム】寿司問題を最適化！？自分だけの🍣最強の寿司デッキ🍣を作ろう！
はじめまして！アルゴリズムエンジニアの松尾です。
「アルゴリズムエンジニアって何をしているの？」という方もいらっしゃると思うので簡単に説明すると、弊社では膨大な選択肢の中からできるだけ良い選択肢を選び出す最適化問題というものを取り扱っていまして、その最適化問題をコンピュータで解く方法をプログラミングするというお仕事をしています。
さて、私はお寿司が好きなんですが、どのネタも美味しそうで毎回どれを選ぶか迷ってしまいます。そこで毎回時間を浪費してしまうんですが、よく考えるとこれも「膨大な選択肢の中から良い選択肢を選び出す最適化問題」なんですよね。
最適化問題に携わる者として、こんな面白そうな問題を放っておくわけにはいきません。しかもこれを解くことで自分だけの🍣最強の寿司デッキ🍣（好きなお寿司をひとまとめにしたセットだと思ってください）を編み出すことができ、お寿司屋さんに行った時の満足度を最大化することができます！どうせ行くなら好きなものをいっぱい食べて大満足したいですからね。
それではやっていきましょう！
準備
まずはコンピュータを使って最強の寿司デッキを作るための準備をしていきましょう。寿司デッキを最適化する前に、コンピュータくんに前提を教えてあげないといけません。今回は以下のように問題を整理してみました。
寿司ネタの一覧が分かっている
各寿司ネタは、「名前」「満足度」「価格」を持っている
満足度の合計値が最大になるように寿司を注文する
コンピュータくんはどのお寿司がどのくらい美味しいのか分からないので、データを作って教えてあげることにしましょう。こんな感じかな……？
例えば、
はまち1皿 + たこ1皿 + 炙り〆鯖1皿 : 110 + 120 + 120 = 350
鯛1皿 + のどぐろ1皿 + つぶ貝1皿 : 130 + 100 + 110 = 340
なので、前者の方が良い寿司デッキということになります。こんな感じで、満足度の合計値が最大になるような組合せをコンピュータで求めていきます。
ちなみに寿司ネタの一覧は社員から募集しました。しゃこって初めて聞いたんですが、江戸前寿司の定番ネタなんですね。なるほど……。
そして満足度は私の独断で決めちゃいました。あくまで今回作りたいのは自分用の最強寿司デッキですからね。ここの評価基準は人によって変わってきそうです。
最強の寿司デッキを求める
コンピュータくんが問題を理解したようなので、早速解かせてみましょう。えいっ！
……
中トロ : 2147483647皿
はまち : 2147483647皿
ぶり : 2147483647皿
鯛 : 2147483647皿
サーモン : 2147483647皿
炙りサーモンチーズ : 2147483647皿
のどぐろ : 2147483647皿
たこ : 2147483647皿
えび : 2147483647皿
しゃこ : 2147483647皿
つぶ貝 : 2147483647皿
炙り〆鯖 : 2147483647皿
鉄火巻 : 2147483647皿
いくら : 2147483647皿
うに : 2147483647皿
山盛りフライドポテト : 2147483647皿
----------------------------------
満足度 : 4949949806335
お会計 : 5433133626910円
お会計5兆4331億円になります。
なんか凄いことになっちゃいましたね……。ちょっとお財布に持ち合わせがなくて困りました。何万年皿洗いをすればよろしいでしょうか……。
予算を決めてあげる
そういえば予算を決めていませんでした。予算を決めずに「満足度ができるだけ大きくなるようにして！」と言ったもんだから、コンピュータくんはそれに従ってできるだけ満足度が高い注文の仕方を求めてくれたようです。確かに満足度も5兆近くありますもんね。コンピュータくんは正しいです。
人間の常識などコンピュータくんは知らないので、教えてあげることにしましょう。条件を一つ追加してみました。
寿司ネタの一覧が分かっている
各寿司ネタは、「名前」「満足度」「価格」を持っている
満足度の合計値が最大になるように寿司を注文する
予算は1500円とし、お会計が予算を超えないようにする
これできっと予算内で最強の寿司デッキをコンピュータくんが求めてくれるでしょう。楽しみですね。えいっ！
……
山盛りフライドポテト: 7皿
-----------------------
満足度 : 2100
お会計 : 1470円
悪ノリした学生かな？
いや確かにフライドポテトは美味しいですよ？美味しいんですけど、こっちにも年齢ってものがありましてね、さすがにそんなたくさん油っこいものばっかり食べられないんですよ。たぶん2皿くらいで限界が来ると思うんです。
それに最強の寿司デッキを作るはずが芋しかないんですけど。ハンバーガーチェーン店に行った方が良いのでは？
満腹度を考慮に入れる
よく考えると、自分の胃袋の大きさをコンピュータくんに伝えていませんでした。それだったら確かに安くて満足度が高いものを大量に食べれば良いってなりますよね。うんうん。
ということで、胃袋の容量をオーバーしないように条件を追加してあげなければいけません。今回は寿司ネタごとに「満腹度」という指標を追加して、満腹度が100を超えないように選んでもらうようにしました。ここまでの条件を整理するとこんな感じですね。
寿司ネタの一覧が分かっている
各寿司ネタは、「名前」「満足度」「価格」「満腹度」を持っている
満足度の合計値が最大になるように寿司を注文する
予算は1500円とし、お会計が予算を超えないようにする
満腹度の合計値が100を超えないようにする
各寿司ネタの満腹度も決めてあげましょう。だいたいこんな感じかな……？
これで私の胃袋が破裂することもないでしょう。それでは計算を実行してみます。えいっ！
……
うに : 4皿
いくら : 2皿
----------------
満足度 : 1060
満腹度 : 100
お会計 : 1500円
どんぶりにしたい感じの組合せが出てきました。
まあ、さっきよりはだいぶ良くなりました。満腹度と予算を上限いっぱいまで使って、なおかつできるだけ満足度を高くしようとしてくれています。でもさすがに4皿も同じものを食べたら飽きそうですね……。こういうストレートな組合せは北海道旅行の時のために取っておきたいです。
1ネタ1皿までにする
フライドポテトのときにも薄々感じてはいたんですが、同じものばっかり食べるとそりゃ飽きます。ですので、同じネタは1皿までという制限をかけてあげましょう。
寿司ネタの一覧が分かっている
各寿司ネタは、「名前」「満足度」「価格」「満腹度」を持っている
満足度の合計値が最大になるように寿司を注文する
予算は1500円とし、お会計が予算を超えないようにする
満腹度の合計値が100を超えないようにする
各寿司ネタはそれぞれ1皿までしか注文できない
もうだいぶおなかが空いてきました。そろそろ良い感じのものをお願いします……えいっ！
中トロ : 1皿
サーモン : 1皿
炙りサーモンチーズ : 1皿
鉄火巻 : 1皿
うに : 1皿
いくら : 1皿
--------------------------------
満足度 : 935
満腹度 : 98
お会計 : 1140円
おおおおお！！！
個人的に大満足な寿司デッキが出来上がりました！予算内で、食べ過ぎにならず、各ネタ1皿ずつになっています！サーモンとマグロが多めですが、個人的に好きなのでOKです。
ついに最強の寿司デッキ完成です！
というわけで
………
……
…
いただきます！
まとめ
今回試した最適化のやり方をまとめるとこんな感じです。
（内部的には「動的計画法」という最適化手法を使っています。）
前提: 各寿司ネタの「名前」「満足度」「価格」「満腹度」が分かっている
条件1: 満足度の合計値が最大になるように寿司を注文する
条件2: 合計金額が予算を超えないようにする
条件3: 満腹度の合計値が100を超えないようにする
条件4: 各寿司ネタはそれぞれ1皿までしか注文できない
皆さんも自分だけの🍣最強の寿司デッキ🍣を作りましょう！
以上、「寿司問題を最適化してみた」でした。
記事が面白かったなと思ったら「スキ」して頂けると嬉しいです。
SNSやHPもチェックしてみてください。最新情報をお送りしています。
ALGO ARTISについて：https://www.algo-artis.com/
最適化ソリューション『Optium』：https://www.algo-artis.com/service
化学業界DXソリューション『Planium』：https://planium.jp/
X：https://twitter.com/algo_artis