IoT, AI,機械学習 トピックス

何をパックすればよいか?

投稿日:

ナップザック問題」という言葉を聞いたことがありますか? ナップザックの容量が決まっていて、できるだけ多くの重量を入れたいとか、優先度の高いものをできるだけパックしたい場合の解法です。 データサイエンスの「動的計画法」と呼ばれる解析手法の一つです。

資料をご覧ください → ナップザック問題

p.1 「ナップザックの容量は10Lです。できるだけ多くの物品をザックに詰め込むには、どの用品の組み合わせにすればよいか?」という問題です。容量10Lという制約条件があります。A~Eの物品の容量と重量を表にしてあります。下表は横軸重量縦軸は空→A→・・・→Eのように一つ一つ物品を入れていきます。セル内の上段の数字は容量下段はザックに入れた物品のアルファベットを示しています。 (0、空)のセル内は0、物品Aをザックに入れた場合が、赤矢印の先にある赤枠のセルになります。(1、A)のセルで3Aと書いてあります。重量1kg、容量3LのAが入っていると言う意味です。このセルより右のセルは全て同じ3Aです。物品Aしか入っていないからです。 次は、ここに物品Bを入れますので、赤矢印の先の赤枠(4,B)になります。AとB合わせて重量4kg、容量5Lなので、5ABと書かれています。このセルの左側は上の行からコピーし、右側は全て5ABです。 物品Cを入れる場合は、少し複雑になります。 空のザックに物品Cだけを入れると2kgになり4Cとなります。この右隣りは、物品Aを入れて7ACが続き、(6,C)のセルでは、物品Bを入れて)9ABCとなります。赤枠以外の赤線の先は、組み合わせが変わったセルです。 この操作を続けていくと、物品の合計容量が10Lになるのは、重量7kg、容量10Lの物品ACEが入る場合と、重量9kg、容量10Lの物品CDの2通りです。解答は3品種が入る黄色のセル10ACEとなります。

p.2 問題を少し変えて「ナップザックの重量は9kgまで。できるだけ多くの物品をザックに詰め込むには、どの用品の組み合わせにすればよいか?」としました。容量の代わりに、物品の価値を点数化しました。入れる価値が高いほど点数を高くしておきます。今回は、重量が制約条件になっています。 p.1と同様の解答になります。

いかがでしたか? 我々が頭で考えるとやや面倒臭いですが、このアルゴリズムAIに入れて計算させれば、あっという間に回答を出してくれると思います。 これからは、データサイエンスの時代です。プログラミングまで知らなくとも、アルゴリズムの種類ぐらいは覚えていきましょう。

 

-IoT, AI,機械学習, トピックス

Copyright© 進化するガラクタ , 2021 All Rights Reserved Powered by STINGER.