グループ分けの問題

質問

ランダムな数字があり(大きさも個数も特に制限無し)、それを次のように
グループ分けします。
・グループ内の数字の合計がある値(これは与えられます)以上であること。
この条件を満たして、グループの数をできるだけ多くしたい。
それを解くようなプログラムはできないでしょうか? プログラムでなくても
必ず最適な解が見つかる指針でも結構です。

宿題とかではありません。

私が手でやる時は、、、例えば、合計を1万とします。
まず、大きな数字から拾っていって、合計1万に近づいたらできるだけ大き
く超えない数を探す。取り敢えず1グループできたら、その繰り返し。

そして最後のグループ。もし、そのグループの不足が他のグループの超過の
合計より大きければそれでお終いですが、超過の合計の方が大きい場合、数
の入れ替えを行いながら微調整をします。例えば、現在合計10100のグループ
の中に300があり、1万に達していないグループに210があったとすると、それ
らを入れ替えれば10100-->10010となり、無駄が減り、残りのグループの合計
を90増やすことができます。このようにして数(orその合計)の近い数(orその
グループ)の組を見つけて入れ替えることにより、調整を行い、不足している
グループが1万を超えるように試行錯誤します。

でも、例えば10100のグループが4つ、残りの合計が9700だった場合、超過の合
計は400ですが、5グループにするのは可能なのか、不可能なのかわかりません。

手でやっていて、それが最適解かどうかわからないので、気持ち悪いです。

よろしくお願い致します。
以上

回答No.4

tgb · ベストアンサー

このような問題は、うまい解法が無く計算時間はデータの規模が大きくなるとやたらと大きくなるＮＰ問題という部類に入るものでしょうか。これ！と言ううまい方法は見つかっていないそうなので諦めるしかなさそうです。つまり、基本的には手順を追って１つ１つ調べ上げるしかないと言うことになりましょうか。
　あまり参考にならないかも知れませんが（また既にご存じかも知れませんが）、次善策として、近似的に解を求める方法が提案されているようです。よく話題にされるものにＡＲ（遺伝的アルゴリズム）というのがあります。本質問の問題の解法としては向いているのではないかと思います。あと、名前を知っているだけなので見当違いになるかも知れませんが、ＳＡ（シミュレーテッド・アニーリング法）と言うのもあるようです。どちらも（ＳＡもそうだったと思います）確率的な方法と言えると思いますが、うまい工夫・アイデアによって目的の解に効率的に近づくようになっているようです。ただ、よりよい解は求めますが最終的に正解（厳密解）に到達するかどうかは保証されないようです。それでも、ANo.#2に紹介されているように合計がピッタリいくつになると言う問題と異なり、良質ではないが最低限の条件を満たす解を求める手順は容易に探すことが可能で後はそれを改良すると言う方法が可能なのでだいぶ気休めにはなるかと思われます。
　このような手法については実際に自分で試したことがない場合は当然相応の勉強が必要ですが、その上で自分の問題をどのように適用させるかの工夫が必要かと思います。そこで、プログラムの作成が面倒くさいと言うなら、現在の手作業をそのままプログラム化するのも手だと思いますがいかがでしょうか？　その際、（数値の合計）／（制限値）が理論上可能なｍａｘのグループ数なのでこれが途中で計算をやめさせる場合の判断材料になると思います。また、話が前後しますが、最適化のアルゴリズムを採用する場合は最適化の条件としては「グループ個数を最大にする」というのは定式化しにくそうですので、厳密には近似の目標になるのかも知れませんが「制限値を超える値の合計を最小にする」で置き換えた方がよい（定式化しやすい）かも知れません。
　この手の問題はデータの規模が重要でそれを抜きにして議論するのは意味がないのではないかと思います。ご質問の説明にある具体例からすると合計値が５万程度で１個のデータが平均２００とすればデータ個数２５０と概算できますが、このオーダーとすると組み合わせとしてはかなり膨大になりそうです。このような場合個々の問題のデータの性質に応じて何らかの工夫を施す必要があると思います（そうしてもだめと言うこともあり得ますが）。その意味でデータの規模、性質などは常に気にしておいた方がよいと思います。
　他に調べてみたい場合は
　　キーワード：ナップサック問題、割り当て問題、ＮＰ問題、
　　　　　　　　組み合わせ最適化、確率的最適化、
　　　　　　　　ＡＲ（遺伝的アルゴリズム）、
　　　　　　　　ＳＡ（シュミレーテッド・アニーリング法）
　　等が参考になると思います。

　以下は私なりに考えてみた工夫です。（上のＡＲ等とは無関係です）

＃１）データを大きさの順に並べておく
　　組み合わせデータを生成する場合の列挙のしやすさを考えれば当然ですが。

＃２）等級化する
　組み合わせを減らすため、例えば
　　１０５、１０７　----->　１００級
　　１１３、１１６　----->　１１０級
　のようにして１０以下の誤差で同一量のデータと見なすというようなことが考えられます。

＃３）全体を予め分割
　同じく組み合わせを減らすため、初めから例えば、２００個のデータを大きさの順に並べた後、交互に２つに分けて１００個ずつの２つの問題に分けると言うことも考えられます。

＃４）全体の組み合わせを減らすため、まず１グループのみの可能性の組み合わせを考えておき、グループの取り出しはこの組み合わせの中からどの組み合わせを取り出すかで決めます。この際、１つの組み合わせを採用することにより以後取り出し不可能となる組み合わせが計算できるのでそれをリストから除く作業を行います。
例えば１０５と言う数値が２個あり、これを含み、制限条件をみたす組み合わせが３０通りあったとしてもこの組み合わせの中から２つ選択してしまえば残りの組み合わせは使えなくなると言ったことを考慮します。
このように組み合わせ作業を２段階にすれば、全体の組み合わせを減らすと同時に、データ生成、チェック手順については比較的単純な考えやすいアルゴリズムにすることができるのではないかと思います。
※勿論このような小手先の工夫では追いつかないかもということも忘れてはなりませんが．．．

お礼

ご回答ありがとうございました。お返事が遅くなってしまい申し訳ございません。
質問をしておきながら、私自身全く専門家ではないので、ご回答をしっかり理解
してからお返事しようと思いつつ、遅くなってしまいました。

なお、この問題がどこから来ているか、数の大きさと個数の目安、についてはNo2の
補足に書かせて頂きました。もしよろしければ、ご覧になってください。

>このような問題は、うまい解法が無く計算時間はデータの規模が大きくなるとやた
>らと大きくなるＮＰ問題という部類に入るものでしょうか。

まさかとは思いましたが、そうなのですか。
ところで、このような部類に入るか、うまい解法があるかを判定する方法はあるの
でしょうか?
いろいろ挙げていただいた近似的な解法は、すべて存じませんが、勉強すれば役立
ちそうだと思いました。

>「グループ個数を最大にする」というのは定式化しにくそうですので、厳密には近
>似の目標になるのかも知れませんが「制限値を超える値の合計を最小にする」で置
>き換えた方がよい（定式化しやすい）かも知れません。
なるほど、その通りですね。

>この手の問題はデータの規模が重要でそれを抜きにして議論するのは意味がないの
>ではないかと思います。
仰る通りですね。申し訳ありませんでした。

以降の工夫も参考になりました。

質問に書きましたように、手動で解くときに、上手くできる時もあるし、あともう1
グループというところで、行き詰まってしまうこともあります。手動でも(最適解で
ないにしても)見つかる時もあるので、コンピュータでもできるような気がしてしま
います。でも、自分でやっていることでさえ、プログラム化することができません。

質問では
>(大きさも個数も特に制限無し)
と大風呂敷を広げてしまいましたが、(数はやはり大きかったとしても)少なくとも
問題を解く段階では大きさも個数も決まっているわけですから、教えて頂いたいろ
いろな工夫を参考に考えてみたいと思います。

ありがとうございました。
以上

回答No.3

nishi6

先ほどの回答はやはり十分理解していなかったみたいです。修正点を書いてみます。

（６）数値2^nから2^(n+1)-1まで、増分1で次の計算を行う。（計算は同じです）
　　　この時に合計数を越したグループを特定してしまう必要がありました。
（７）次に数値2^(n+1)から2^(n+2)-1について同様の計算をする。
　　　　以降合計値を越す数値になるまで（７）の繰り返しになってしまいました。
　　　　実測してみましたが、私のPCで22個～24個の数値が待てる時間みたいです。（十数分）

計算スピードを上げるには(Excelですが)、小さいほうから10～14個位までの数値の組み合わせの和を事前に作っておき、
この数値の組み合わせについては計算しない方式です。これで22個～24個の時はスピードが上がり、30個くらいまでの数値の計算ができそうです。

やはり、
＞大きさも個数も特に制限無し
が響いてきました。個数の上限くらい決まっていると効率的な方法があるかもしれません。

今回回答も含め、明確な回答になっていません。参考程度にお読みください。失礼しました。

お礼

続きです。まず、No2のお礼で書き忘れた事を書きます。
ご紹介いただいた、別の問題、面白そうですね。こちらも完全理解してからと
思っていましたが、まだまだです。

さて、
>（６）数値2^nから2^(n+1)-1まで、増分1で次の計算を行う。（計算は同じです）
>この時に合計数を越したグループを特定してしまう必要がありました。
この「特定」とはどういうことでしょうか? 一つ目のグループができたところで、
それを除外して、また、同様の計算をするのだと思いますが、その場合、また、
No2の(1)から行うのかな?と思うのですが。

>やはり、
>＞大きさも個数も特に制限無し
>が響いてきました。個数の上限くらい決まっていると効率的な方法があるかもしれ
>ません。
適当に質問したつもりではありませんが、やはり、専門家の方からすると、全くも
っていい加減な質問ですよね。非常に大きな数も考えなくてはいけなくなりますか
ら。申し訳ありませんでした。

以上

回答No.2

nishi6

＞ランダムな数字があり(大きさも個数も特に制限無し)
この『制限無し』については、
　通常のパソコンで通常扱える数値・・・倍精度程度の桁数の整数値（＞0）
　ランダムな数字の個数は有限個数・・・実際は数十個でしょうか。（何個でもかまいませんが）
としています。

質問の意味を正しく捉えていれば、下記の方法で簡単に個数が求まりますが・・・・

（１）使用する数値の個数をＮ個とします。
（２）この使用する数値を昇順に配列Dt(i)（インデックスiは1から）に格納
（３）インデックス１から配列に格納した数値を加算する
（４）指定する合計を超える最小のインデックスを求める。
（５）このインデックスの－１したものを『n』とする。
　　　　数値全部の組み合わせ、(2^Ｎ-1)個のうち、(2^n-1)個は指定する合計になり得ないのが分かります。
（６）数値2^nから2^(n+1)-1まで、増分1で次の計算を行う（2^n+α=mとします）
　　　　mに対して次の計算を行います。
　　　　mと2^pのAND計算をp=0からp=nまで行って、(m AND 2^p)<>0 ならDt(p+1)を加算します。
　　　　　Total=0
　　　　　FOR j=0 TO n
　　　　　　If (m AND 2^j)<>0 Then
　　　　　　　Total = Total + Dt(j+1)
　　　　　　End If
　　　　　Next

　　　　VB(VBA)風に書いています。
　　　　数値の組み合わせを2進数のビットに任せています。
　　　　計算開始数値が決まっていて、計算を終了する条件は、Total>=指定する合計　になります。
　　　　これを Ans とします。

（７）数値の組み合わせは、増分1で計算し、配列Dt(i)は昇順にしてあるので、最初に見つかった数値の
　　　2進数表現に対応するDt(i)の組み合わせが、指定する合計に等しいか最初に超過する組み合わせの
　　　１つ。
（８）(2^Ｎ-1)個 - Ans + 1 が答えになります。

プログラム的には、
　全部の数値を加算しても指定する合計にならない場合は計算しない。
　2^p計算の有効数値を考慮する必要がある。（49個までなら不要？）
　2^p計算がオーバーフローしないよう計算桁数を分割する必要がある。（32個までなら不要？）
　2^pと2^(p+1)の間を調べる時、pが大きくなると網羅するには時間ががかるので、
　ある数値以上は2分割法で行う。
などの考慮が必要でしょう。

2進数（0、1）が数値の使用、不使用を表し、これに使う数値（重み）を掛けて加算するわけです。2進数が昇順で、重みが昇順なら、2進数を進めて行けば組み合わせが網羅でき、最初に指定合計と等しいか超過したら、それ以降は全て等しいか超過するグループになるわけです。2^Ｎと2^(N+1)間はＮが大きいと計算に時間がかかるため2分割法を使用して、計算区間を100程度に縮小してしまいます。

Excel-VBAで32個の数値を使い計算を行いましたが、2分割法を使用して、計算所要時間は1秒未満です。
数百個の数値を使用しても、2^Ｎ計算を30桁程度で分割して、数回～数十回組み合わせ計算を行うだけなので数秒で計算が終わると予測できます。

最近回答しました下記URLの、前半の処理に近いですね。
http://www.okweb.ne.jp/kotaeru.php3?q=257719

ご参考に。（当方、windows98、500MHzのpc、Excel2000で確認しました。）

お礼

ご回答ありがとうございました。お返事が遅くなってしまい申し訳ございません。
質問をしておきながら、私自身全く専門家ではないので、ご回答をしっかり理解
してからお返事しようと思いつつ、遅くなってしまいました。すみません。まだ、
完全には理解していません。

この問題がどこから来ているか、数の大きさと個数の目安、については補足に
書かせて頂きます。

>2進数（0、1）が数値の使用、不使用を表し、これに使う数値（重み）を掛けて加
>算するわけです。2進数が昇順で、重みが昇順なら、2進数を進めて行けば組み合わ
>せが網羅でき、最初に指定合計と等しいか超過したら、それ以降は全て等しいか超
>過するグループになるわけです。
なるほどと思いました。これで、(2^n-1)個の場合の計算をしなくて済む訳ですね。

>（８）(2^Ｎ-1)個 - Ans + 1 が答えになります。
Ansは指定合計を超えた時のTotalですか? これと(2^Ｎ-1)個を足すところが分かり
ませんでした。

その他、計算時間を減らす工夫、なるほどと思いました。

続けて、No.2のお礼に続きます。

補足

この質問がどこから来ているかをご説明します。

(どうしようもない動機ですみません。でも、数学的に考えたかったのは純粋な
動機です。)
デパート等で、「○月○日から×月×日までのレシートの合計1万円を一口として
何口でも応募できる」というプレゼントがありますよね。
・1万円以上のレシートは一枚で一口なので除外。
・例えば、合計5万円程度。枚数は例えば、30枚とか、そんな感じです。

逆に、こんな問題もあります。好きな音楽だけを集めて、テープを作るとします。
20曲あって、時間の合計は100分。これを60分テープ2本に入れたい。片面30分だから
4面で120分。順番はどうでも良いので、なんとか収めたい。

大小関係が逆になりますが、似たような問題ではないでしょうか?

以上
お時間がありましたら、お願い致します。

回答No.1

noname#5179

もしもとんでもなく長い時間がかかってもいいのなら、すべての組み合わせを計算するのがもっとも楽ですね。

効率を完全に無視して、しらみつぶしの方法の一例をあげます。

例として100個の数が合って、数の合計が50100で、ひとつのグループの最低合計数10000の時に、5つのグループが本当にできるのかどうかという場合には、

グループ1から５をまず仮定します。
そして100個の数をそれぞれどのグループに属するかの組み合わせをすべて作ってみて、すべてのグループの合計が10000を超える例があるかどうかを調べます。

それぞれの数につき5つのグループのどれに属するかを選べるので、
５の100乗というとんでもない組み合わせの例を試す必要がありますが確実です。

補足

ご回答ありがとうございます。

そうなんです。全部調べようとすると膨大な時間がかかります。試算したわけでは
ありませんが、コンピュータで行わせたとしても膨大な時間になりそうですよね。