Azure環境上にあるo1-previewを使って、以下のナップサック問題を解かせてみました。
ナップサック問題とは、ナップサックにものを入れるときどれを何個入れればいいかを計算する問題です。数学では数理最適化手法を使う際の例でよく出てきます。
Azure OpenAI Service チャットプレイグラウンドに以下のプロンプトを投入してみました。使用したモデルは o1-preview (version:2024-09-12) です。
プロンプト（整数ナップサック問題）
以下の問題は、Nuorium Optimizer C++SIMPLE例題集V26 の 2.5ナップサック問題 を引用しています。
あなたは優秀な数学者です。次の問題を数理最適化手法を使って解答手順を論理的に説明しながら解答を導出してください。
#問題容量65のナップサックに次の表にある品物を詰め込むことにします．この時，詰め込んだ品物の総価値を最大にするためには何をいくつ詰め込むと良いでしょうか．ただし，同じ品物を何個詰め込んでも良いものとします．
|品物|1個あたりの価値|1個あたりのサイズ||----|--------------:|----------------:|
|缶コーヒー|120|10|
|水入りペットボトル|130|12|
|バナナ|80|7|
|りんご|100|9|
|おにぎり|250|21|
|パン|185|16|
結果
以下、o1-preview の解答です。
私は、ナップサック問題の数理最適化手法を用いて、この問題を解決します。ナップサック問題とは、容量制限のある袋に複数の品物を選んで入れ、その価値の総和を最大化する問題です。この問題では、同じ品物を何個でも選べる「無制限ナップサック問題」として扱います。
>
まず、与えられた品物の価値とサイズを整理します。
>
|品物|1個あたりの価値 (v_i)|1個あたりのサイズ (w_i)|
|----|----------------:|----------------:|
|缶コーヒー|120|10|
|水入りペットボトル|130|12|
|バナナ|80|7|
|りんご|100|9|
|おにぎり|250|21|
|パン|185|16|
>
ナップサックの容量は65です。目的は、総価値を最大化することです。
>
### 手順1: 品物の価値密度を計算する
>
価値密度とは、1単位サイズあたりの価値を表します。これを計算して、効果的な品物の選択に役立てます。
>
\[
\text{価値密度} = \frac{v_i}{w_i}
\]
>
計算結果：
|品物|価値密度 \((\frac{v_i}{w_i})\)|
|----|-------------------------:|
|缶コーヒー|12.0|
|水入りペットボトル|10.83...|
|バナナ|11.42...|
|りんご|11.11...|
|おにぎり|11.90...|
|パン|11.56...|
>
価値密度の高い順に並べると：
>
1. 缶コーヒー (12.0)
2. おにぎり (~11.90)
3. パン (~11.56)
4. バナナ (~11.42)
5. りんご (~11.11)
6. 水入りペットボトル (~10.83)
>
### 手順2: 最適な組み合わせを探索する
>
価値密度の高い品物から順に選び、ナップサックの容量を超えないように組み合わせを試します。
>
**まず、缶コーヒーを可能な限り詰めます。**
>
- 缶コーヒーのサイズは10なので、65 ÷ 10 = 6個まで入れられます。
- 6個の缶コーヒーのサイズ合計は60、価値合計は720です。
- 残り容量は5で、これは他の品物の最小サイズ7より小さいため、他の品物は入れられません。
>
**次に、おにぎりを検討します。**
>
- おにぎりのサイズは21なので、65 ÷ 21 = 3個まで入れられます。
- 3個のおにぎりのサイズ合計は63、価値合計は750です。
- この時点で、価値合計は缶コーヒーのみよりも高くなります。
>
**さらに、組み合わせを試します。**
>
**ケース1:**
- おにぎり2個（サイズ42、価値500）
- 残り容量は23。
- 缶コーヒー2個を追加（サイズ20、価値240）
- 合計サイズ62、残り容量3。
- 価値合計は500 + 240 = 740。
これは、おにぎり3個のみの750よりも低いです。
>
**ケース2:**
- おにぎり2個（サイズ42、価値500）
- パン1個を追加（サイズ16、価値185）
- 合計サイズ58、残り容量7。
- バナナ1個を追加（サイズ7、価値80）
- 合計サイズ65、価値合計は500 + 185 + 80 = 765。
これまでで最高の価値合計です。
**ケース3:**
- おにぎり1個（サイズ21、価値250）
- 缶コーヒー4個を追加（サイズ40、価値480）
- 合計サイズ61、残り容量4。
価値合計は250 + 480 = 730で、ケース2より低いです。
**ケース4:**
- おにぎり1個（サイズ21、価値250）
- 缶コーヒー3個（サイズ30、価値360）
- バナナ2個（サイズ14、価値160）
- 合計サイズ65、価値合計は250 + 360 + 160 = 770。
これは現在の最高値です。
### 手順3: 最適解の決定
以上の試行から、価値合計770が最大であり、その組み合わせは以下の通りです。
- **おにぎり：1個**
- **缶コーヒー：3個**
- **バナナ：2個**
### 手順4: 解答
**答え：**
- おにぎりを1個、缶コーヒーを3個、バナナを2個詰め込むと、総価値770で最大になります。
**詰め込む品物の詳細：**
- おにぎり：サイズ21、価値250
- 缶コーヒー：サイズ10×3＝30、価値120×3＝360
- バナナ：サイズ7×2＝14、価値80×2＝160
**合計：**
- サイズ：21 + 30 + 14 = 65（ナップサックの容量ぴったり）
- 価値：250 + 360 + 160 = 770（最大）
**よって、この組み合わせが最適解となります。**
考察
ナップサック問題は、動的計画法という問題の部分集合に切り出して解いていく方法と、総当たりでもとめる全探索法の２つがあります。
o1-previewは、前者の動的計画法もどき（価値密度の一番高い商品を可能な限り最初に詰めるという部分問題を設定して解いていく）を使って解答をつくっています。
全探索法の場合、整数変数が多くなればなるほどトークンを大量に消費していき、やがてモデルの制約条件を超えてしまう危険性があります。
ただ..この問題の整数変数は商品ごとの数量なので6個と少数です。論理的に解決する場合、総当たりでも探索数はたかが知れているため制約内で済むので、全探索法を採用したとしてもそれはそれで合理的な解き方だといえます。
ちなみに、問題の引用元での解答は、以下の通りo1-previewの解答と異なっています。
詰め込む個数["おにぎり"] = 1
詰め込む個数["りんご"] = 1
詰め込む個数["バナナ"] = 1
詰め込む個数["パン"] = 1
詰め込む個数["缶コーヒー"] = 0
詰め込む個数["水入りペットボトル"] = 1
総価値 = 745
これは、引用元サイトとo1-previewが異なる目的関数（上記では価値関数とよんでいる）の定義がことなっていることも要因のひとつです。
ナップサックにいれる価値を引用元サイトが、各品物について「1個あたりの価値」と「その品物を詰め込んだ個数」の積の最大化を求めているのに対して、o1-previewが価値密度×個数の総和の最大化を求めているためです。
今回のナップサックに固形物をつめる場合は、問題の捉え方からすると前者のほうが正しいですが、回答を見るとo1-previewのほうがより価値合計の高い商品を選択しています。
これまでの数理最適化をコンピュータに解かせる場合、整数変数・目的関数・制約条件を人間側が考えてコンピュータ上のソルバーに解かせる方法が主流でしたが、上記のように整数変数・目的関数・制約条件の設定からコンピュータにまかせる丸投げができるようになります。
ただし、今後は数理最適化問題などを勉強しなくていいか、というとそうではありません。コンピュータの解決方法や回答が正しいのかどうかを判断するのは人間にしかできません。
AIの作ったものは、人間が責任を取るしかない、ということです。
