ファンリピート社のブログFR note

ChatGPTは組み合わせ最適化問題が解けるのか

ChatGPTは組み合わせ最適化問題が解けるのか

こんにちは。日常の様々な場面で「CharGPT」のワードを聞く機会が増えてきました。

一見万能そうに思えるChatGPTですが、不得意なこともあると想像できます。今回はChatGPTに少し複雑な文章題を出題し答えを導けるのか検証したいと思います。

目次

\ ホワイトペーパー /
ローコード・ノーコード開発が理解できる資料集

【下記の4点の資料が無料でダウンロードできます】

  • 基礎知識の解説
  • 開発事例集
  • おすすめノーコードツール13選
  • ローコード・ノーコード開発会社比較

ChatGPTとは

あわせて読みたい

ChatGPTとは、名前の通りチャットを通して入力されるユーザの質問に対してAIが文章による回答を生成するサービスのことです。「GPT」という言語モデルがベースになっています。インターネット上で無料で利用ができ、日本語にも対応するほか、pythonやC言語などのコードを回答として表示することもできます。

組み合わせ最適化問題とは

今回は、CharGPTに組み合わせ最適化問題を出題してみようと思うのですが、その前に組み合わせ最適化問題について説明したいと思います。

株式会社 NTTデータ数理システム

引用

“組み合わせ最適化ソリューション(強化学習AI×シミュレーション)|株式会社NTTデータ数理システム.” NTTデータ数理システム, https://www.msi.co.jp/solution/s4/ReinforcementLearning.html. Accessed 8 August 2023.

組み合わせ最適化とは、膨大な数の組み合わせから、条件を満たす組み合わせや、最も良い組み合わせを探索することです。

応用例としては、効率の良い配送ルートの策定、シフトスケジュールや生産計画などのスケジューリングなどがあります。

組み合わせ最適化ソリューション(強化学習AI×シミュレーション)|株式会社NTTデータ数理システム.” NTTデータ数理システム, https://www.msi.co.jp/solution/s4/ReinforcementLearning.html. Accessed 8 August 2023.

シフトスケジュールで考えると、同じシフトに入れる人数が決まっていたり、業務効率にそれぞれ得手不得手がある人でシフトを組むとき、雇用側に不利益が生じないような効率のよいシフトの組み方を考えるのが組み合わせ最適化問題に当たります。

看護師など夜勤がある場合は、連続して夜勤にならないようにしたり、どの仕事場でも相性の悪い人同士は同じシフトに入れないよう設定しなければなりませんね。こういった少しの条件が入るだけで効率の良い組み合わせを考えるのがぐっと難しくなります。

今回は、考えてもすぐ分からないような組み合わせ最適化の問題をChatGPTに聞くことで解決するのを目標にしたいと思います。

出題する組み合わせ最適化問題

簡単そうに見えて複雑な以下の組み合わせ最適化問題を考えてみました。

田中さんと山田さんの二人で3丁の包丁を使って野菜を切る場合の時間効率について考える。

ジャガイモ30個、人参10本、玉ねぎ25個を全て切りたい。

ただし、同時に使える包丁はそれぞれ1丁ずつ。野菜を1個切り終えるまで他の野菜は切ってはいけない。

A, B, Cの包丁の性能は以下の通り

Aの包丁ではジャガイモ1個に1分、ニンジン1本に2分、玉ねぎ1個に1.5分かかる。

Bの包丁ではジャガイモ1個1.5分、ニンジン1本2分、玉ねぎ1個に1分かかる。

Cの包丁ではジャガイモ1個1.75分、ニンジン1本1.5分、玉ねぎ1個に1分かかる。

田中さんと山田さんにはそれぞれ得意な包丁と苦手な包丁がある。

田中さんは、上記のBとCの包丁を規格通り使い、Aの包丁を1.5倍効率よく使える。

山田さんは、上記のBとAの包丁を規格通り使い、Cの包丁を0.75倍効率悪く使う。

全ての野菜をより早く切り終えるにはどうすればよいか。

ChatGPTにアクセス

あわせて読みたい

こちらにアクセスすると次のような画面が表示されます。

ChatGPTにアクセス
図1.ChatGPTにアクセス

既にアカウントを作っている場合はLog inを選択し、ログインします。新規アカウントを作成する場合はSign upより新規登録ページに移動します。

図2. 新規登録

アカウントはメールアドレスだけでなく、Googleアカウント、Microsoftアカウント、Appleのアカウントでも作成できるので好きな方法で登録しましょう。

サインアップが終わると名前と生年月日を入力するページに切り替わるので入力しておきます。電話番号認証や非ロボット認証もあるので正確に回答します。

CharGPTのチャット開始画面
図3.利用開始

無事にログインが完了するとこちらの画面が出てくるので、下部の「Send a message」から「こんにちは」と送ってみます。個人情報のためアイコンを隠しています。

CharGPTのこんにちはに対する回答
図4.回答

GPT-3.5とGPT-4の違い

ログインしてみると先ほどの図のように画面上に「Default(GPT-3.5)」と出ていることが確認できます。これは言語モデルのバージョンを表しています。ChatGPTは利用料を払うことでGPT-4が利用できることになっています。

4が最新のバージョンとなっており、3.5よりも多くの機能を持っています。例えば、3.5では画像を送信したり画像を生成したりが出来ませんが4ではユーザが画像を送信して説明したり、GPTが送られてきた画像にテキストで説明ができるようになりました。また、3.5よりも高い精度で回答が可能で、公式の発表ではアメリカの司法試験の成績が3.5が下位10%程度の成績だったものが4では上位10%程度の成績が取得できたことも明らかになっています。参考(https://cdn.openai.com/papers/gpt-4.pdf

まずは、無料版のGPT-3.5に聞いてみましょう。

早速質問してみる(GPT-3.5)

先ほど考えた組み合わせ最適化問題をそのままコピーして送信してみます。

以下のような回答が得られました。

組み合わせ最適化問題に対する回答①
図5.回答①
組み合わせ最適化問題に対する回答②
図6.回答②

回答を確認

上から順番に確認してみます。

田中さんと山田さんが包丁を効率的に使って野菜を切るためには、それぞれの得意な包丁と苦手な包丁を適切に活用する必要があります。以下の手順で効率的に作業を進めることができます。

その通りですね。

田中さんの作業分担: 田中さんはBの包丁とCの包丁を規格通り使い、Aの包丁を1.5倍効率よく使えるので、ジャガイモと玉ねぎの切り分けにAの包丁を使用します。

  • ジャガイモの切り分け:Aの包丁で切る。
  • 人参の切り分け:Bの包丁で切る。
  • 玉ねぎの切り分け:Aの包丁で切る。

Aの包丁が一番得意なのがジャガイモで田中さんはAの包丁を使うと効率が1.5倍なので、田中さんがジャガイモを切った方が良いですね。田中さんは、ずっとAを使った方が早く切れそうに感じます。

山田さんの作業分担: 山田さんはBの包丁とAの包丁を規格通り使い、Cの包丁を0.75倍効率悪く使うので、人参と玉ねぎの切り分けにCの包丁を使用します。

  • ジャガイモの切り分け:Bの包丁で切る。
  • 人参の切り分け:Cの包丁で切る。
  • 玉ねぎの切り分け:Cの包丁で切る。

山田さんはCの包丁の効率が悪いので使わない方が良さそうに感じてしまいます。

これにより、田中さんと山田さんが同時に作業を進めることができます。次に、各野菜ごとの切り分けにかかる時間を計算し、最短時間で全ての野菜を切り終えることができる組み合わせを求めます。

同時に別の野菜を切ることが時間短縮の鍵であることは明らかです。

各野菜の切り分けにかかる時間の計算: 

ジャガイモ:田中さん(A) → 30個 × 1分 = 30分、

      山田さん(B) → 30個 × 1.5分 = 45分 

人参:田中さん(B) → 10本 × 2分 = 20分、

   山田さん(C) → 10本 × 1.5分 = 15分 

玉ねぎ:田中さん(A) → 25個 × 1.5分 = 37.5分、

    山田さん(C) → 25個 × 1分 = 25分

田中さんと山田さんの作業組み合わせ: 田中さんと山田さんは、ジャガイモと玉ねぎの切り分けを同時に行うことで、時間を節約できます。人参の切り分けは別々に行います。

種類ごとの野菜を切り分けるのに必要な時間を計算しているようです。しかし、効率の良し悪しの部分を無視して計算してしまっています。また、野菜は途中で切り替えても良いので各種1個当たりにかかる時間を計算した方が分かりやすい気がします。

最短時間で野菜を切り終える組み合わせ:

  • ジャガイモと玉ねぎの切り分け:田中さん(A) + 山田さん(C) → 45分
  • 人参の切り分け:田中さん(B) + 山田さん(C) → 20分

合計時間:45分 (ジャガイモと玉ねぎ) + 20分 (人参) = 65分

こちらの計算の内訳が分からないので確かめられません。田中さんと山田さんは同時に切る作業ができるのでジャガイモと玉ねぎの切り分けに45分もかからないように感じます。

したがって、田中さんと山田さんが最短時間で全ての野菜を切り終えるには、合計で65分かかります。

とてもそれらしい回答を出してはくれましたが、計算や考え方に誤りが生じています。

段階ごとに解いてもらう

段階を踏んで解いてもらうことにします。まず、野菜1個あたりにかかる時間を担当する人と包丁の組合せごとに出してもらいましょう。

以下の文章を送信してみました。

「一旦、田中さんと山田さんがABCの包丁で野菜1個を切り終えるのにかかる時間を計算してください。」

回答は以下の通りです。

それぞれの包丁で野菜1個を切り終えるのにかかる時間を計算します。

田中さんの包丁使用時間:

– Aの包丁:ジャガイモ 1個に 1分

– Bの包丁:人参 1本に 2分

– Cの包丁:玉ねぎ 1個に 1.5分

山田さんの包丁使用時間:

– Aの包丁:ジャガイモ 1個に 1.5分

– Bの包丁:人参 1本に 2分

– Cの包丁:玉ねぎ 1個に 1分

田中さんの得意な包丁(Aの包丁)を1.5倍効率よく使えるため、時間を1.5で割って計算します。山田さんの苦手な包丁(Cの包丁)を0.75倍効率悪く使うため、時間を1.25倍して計算します。

それぞれの包丁で野菜1個を切り終えるのにかかる時間は以下の通りです:

田中さん:

– Aの包丁:1分 ÷ 1.5 = 0.67分 (約0.67分)

– Bの包丁:2分

– Cの包丁:1.5分

山田さん:

– Aの包丁:1.5分

– Bの包丁:2分

– Cの包丁:1分 × 1.25 = 1.25分 (約1.25分)

これは合っています。

これを元にして、もう少しかみ砕いて問題文を説明します。

以下の文を送ってみました。

「この情報を元に田中さんと山田さんがABCの包丁を使い、ジャガイモ30個、人参10本、玉ねぎ25個を二人で切り終えるのに必要な最短時間を求めて下さい。二人でこれらの野菜を切れば良いことに注意してください。」

回答は以下の通りです。

田中さんと山田さんがABCの包丁を使って、ジャガイモ30個、人参10本、玉ねぎ25個を最短時間で切り終えるための計算を行います。

田中さんの各包丁での切り分け時間:

– Aの包丁:0.67分/個

– Bの包丁:2分/個

– Cの包丁:1.5分/個

山田さんの各包丁での切り分け時間:

– Aの包丁:1.5分/個

– Bの包丁:2分/個

– Cの包丁:1.25分/個

最短時間で切り終えるために、田中さんと山田さんが同時に作業を進めることを考えます。野菜ごとにどちらの人がどの包丁を使うかを選択し、最小の時間を計算します。

各野菜の切り分けにかかる時間の計算:

ジャガイモ:

– 田中さん:30個 × 0.67分/個 = 20.1分

– 山田さん:30個 × 1.5分/個 = 45分

人参:

– 田中さん:10本 × 2分/個 = 20分

– 山田さん:10本 × 2分/個 = 20分

玉ねぎ:

– 田中さん:25個 × 1.5分/個 = 37.5分

– 山田さん:25個 × 1.25分/個 = 31.25分

最短時間を求めるため、田中さんと山田さんが同時に作業する場合、各野菜の切り分けにかかる時間を合計します:

合計時間 = ジャガイモの時間 + 人参の時間 + 玉ねぎの時間

合計時間 = 20.1分 + 20分 + 31.25分

合計時間 ≈ 71.35分

したがって、田中さんと山田さんがABCの包丁を使ってジャガイモ30個、人参10本、玉ねぎ25個を最短時間で切り終えるためには、約71.35分かかります。

どうしても、二人でこの数の野菜を切ればよいということが理解できていないようです。

「田中さんと山田さんのジャガイモを切る数は足したら30、ニンジンを切る数は足したら10本、二人で玉ねぎを切る数は足したら25個です」

この文章を送ってみましたが、やはりうまく理解できないようでした。

了解しました。申し訳ありませんが、前回の回答での誤りを修正して計算を行います。

田中さんと山田さんがジャガイモ、人参、玉ねぎを切る数がそれぞれ足し合わせて合計個数と一致する場合、最適な作業分担を見つけることができます。

各包丁ごとの切り分け時間を再度計算します:

田中さん:

– Aの包丁:ジャガイモ 1個に 1分 ÷ 1.5 = 0.67分

– Bの包丁:人参 1本に 2分

– Cの包丁:玉ねぎ 1個に 1.5分

山田さん:

– Aの包丁:ジャガイモ 1個に 1.5分

– Bの包丁:人参 1本に 2分

– Cの包丁:玉ねぎ 1個に 1分 × 1.25 = 1.25分

各野菜の切り分けにかかる時間を計算します:

ジャガイモ:

– 田中さん:30個 × 0.67分/個 = 20.1分

– 山田さん:(30 – 20)個 × 1.5分/個 = 15分

人参:

– 田中さん:(10 – 0)本 × 2分/本 = 20分

– 山田さん:10本 × 2分/本 = 20分

玉ねぎ:

– 田中さん:(25 – 0)個 × 1.5分/個 = 37.5分

– 山田さん:25個 × 1.25分/個 = 31.25分

最短時間を求めるため、田中さんと山田さんが同時に作業する場合、各野菜の切り分けにかかる時間を合計します:

合計時間 = ジャガイモの時間 + 人参の時間 + 玉ねぎの時間

合計時間 = 20.1分 + 20分 + 31.25分

合計時間 ≈ 71.35分

したがって、田中さんと山田さんがABCの包丁を使ってジャガイモ30個、人参10本、玉ねぎ25個を最短時間で切り終えるためには、約71.35分かかります。

二人で同時に野菜を切ればよいという計算ができないようです。

その後も、何回か文言を変えて説明しましたが誤った回答が送られてしまいました。これが理解できないとこの問題を解くのは難しいと思います。また、前の回答ではきちんと算出できていた、包丁と人ごとの切るのにかかる時間も出せていません。このような複雑な問題を解くのには向いていなさそうです。

GPT-4に送ってみる

試しに精度が高いGPT-4で全く同じ文章で聞いてみることにします。

GPT-4の回答①
図7.GPT-4の回答①
GPT-4の回答②
図8.GPT-4の回答②
GPT-4の回答③
図9.GPT-4の回答③
GPT-4の回答③
図10.GPT-4の回答④
GPT-4の回答⑤
図11.GPT-4の回答⑤
GPT-4の回答⑥
図12.GPT-4の回答⑥

すると、初めから田中さんと山田さんの包丁の得意不得意を考慮し野菜1個当たりの時間効率を求めてくれました。回答に誤りが生じていてもこちらで簡単に説明して訂正すれば対応し、より正確な回答を導いてくれています。結果的にGPT-3よりも短い時間を求められ、GPT-4の精度の良さが体感できました。

しかし、野菜は1個切り終えたら種類を変えても良いので、田中さんが最後のニンジンを切っている間に最後に生じる山田さんが何もしない時間を無くす必要があります。GPT-4は助言をすることで、ある程度回答に近づけますが、このように訂正しつつ人間とGPTの共同作業で回答を導く方法が一番妥当だと考えられます。

この組み合わせ最適化問題では、「何もしない時間が無いようにする」「効率の良い包丁と悪い包丁の使用割合を上手く調整する」「同時に作業する」といった効率面で重視すべき事柄が多いのも解くのが難しい原因だと考えられます。この3点に注意しながら、自分とGPTで協力して答えを考えてみるのも良いかもしれません。

結論

GPT-3.5の場合、組み合わせ最適化問題を解くには向いていないが、簡単な計算なら文章の入力だけでもできる。

回答を得るのに必要な文章を分かりやすく書く必要があるが、段階を踏んで求めていくと途中で前に得た回答を誤ったまま使用することがある。

GPT-4では、人間が少し助言をすることで精度の良い回答が得られる。

最後に

ChatGPTは便利なツールですが、このような複雑な文章問題を解くのは難しく、問題を送る側で工夫しChatGPTに分かりやすい文章を送る必要があるようです。しかし、ChatGPTは言語やプログラミングなどある程度定まっているルールによく適応することが分かっているため、英語学習や新たなプログラミング言語の習得に利用してみるのがおすすめです。

メンバーを募集中!

当社ではお客様に向き合い、お客様の事業成功にコミットをできる仲間を募集しています。

正社員、インターンから副業まで、幅広く採用活動を進めております。プロジェクトマネージャーやシステムエンジニアとして当社のシステム開発業務に携わってみませんか?

当社と共に、業界トップを目指して挑戦したい方は未経験者から経験者まで広く募集しているので、ぜひエントリーをお待ちしています。

\ ホワイトペーパー /
ローコード・ノーコード開発が理解できる資料集

【下記の4点の資料が無料でダウンロードできます】

  • 基礎知識の解説
  • 開発事例集
  • おすすめノーコードツール13選
  • ローコード・ノーコード開発会社比較
  • URLをコピーしました!

この記事を書いた人

株式会社ファンリピートのアバター

株式会社ファンリピート

FRnoteは株式会社ファンリピートのメンバーによって運営されている社内ブログです。ノーコード・ローコードの技術ブログを始めとして、最新のIT技術、業務で役立つノウハウなど様々なトピックをまとめています。


目次
閉じる