MS Access Tips/Sample and VBA and Blog customize etc...

VBAで組み合わせ合計探索

「数値のリストがあり、そのすべての組み合わせの中から、指定した合計の組み合わせを求めなさい。」

定期的に掲示板で出てくる問題です。(1年に一度ぐらいかな)

今回もMougのExcel掲示板で出てきました。

その合計の元になる数字を取り出す

これの回答用にサンプルを作成したので紹介します。

VBAで組み合わせ合計探索タイトル

難易度:

解を求める困難性

かつて、AccessClub掲示板でも同様の質問があり、私がスレを立てて議論したことがあります。

合計探索問題、みなさんの頭脳に挑戦!!^^;

そうそうたるメンバーが、創意工夫したコードを投稿しているので、非常に興味深く、また、参考になる内容だと思います。

この問題を解く前に下記に点について理解しておく必要があります。

n件のデータの組み合わせ数は 2のn乗になり、件数が増えると急激に増加します。

n2のn乗
101,024
201,048,576
301,073,741,824
401,099,511,627,776
501,125,899,906,842,620

50件だと兆の上の京という単位になります。ここまで来るとスパーコンピューターでも現実的な時間で解くのは困難です。

現在のPCで解く場合、実用的なのなのは30件ぐらいまでと考えたほうがいいでしょう。

掲示板で出てくる質問はこの辺が理解できてなくて、データ数が60件だの100件だのという不可能案件が多いです。

また、30件ぐらいで実用的な時間で求められたとしても、大量の解が出たら、その中からどれが正解か選択するのが困難ということもでてきます。

このような案件は間違っても気軽に受けないで、よくよくデータを分析して、不可能ならきっぱりと断りましょう。

問題仕様

シートのA列に数値、B列に名称のデータがあります。

このデータから、B例の同じ名称内でA列の数値のすべての組み合わせの合計から、
C2セルに入力した合計値に等しいものを取得して、その組み合わせをD列以降に"○"を付けて表示します。

合致する組み合わせが100件を超えたときはその時点で探索を中止します。

エクセルブック

うう 20件
ええ 17件
おお 13件
計 50件

標準モジュール

実行結果

DoSearch プロシージャを実行してください。
全50件、一社当たり最大20件の上記のサンプルデータで、私の環境で 0.05秒程度で結果が出ました。

エクセルブック合計探索実行後

一社当たり最大30件に増やして試してみましたが、1秒以内で終了しました。 ただ、結果件数が75件になりましたので、ここから目的のものを探すのが難しいですね。

コードの高速化の解説

高速化するために下記のロジックを使用しています。

基本的にはすべての組み合わせを配列を使用して木構造で総当たりする。

枝の途中で先に解がないと判断出来たら、枝の分岐に戻る(枝刈り)。

データ配列は枝刈りを効率的にするために数値で昇順にソートしておく。
ソートは高速なクイックソートのアルゴリズムを利用。

木構造と枝刈りロジックのモデル図
リンク無し画像

合計値は配列に格納して分岐に戻るときはそれを利用するようにして再計算を省略。

探索合計値が小さいほど枝刈りが有効に働くので小さいときは高速だか、大きくなるにしたがって遅くなる。
そこで、探索合計値が総合計値の半分を超えたときは、総合計値 - 探索合計 を検索して、結果の逆を出すようにする。

プログラミングの専門教育を体系的に受けたことがなく、行き当たりばったりでここまできましたので、用語等は怪しいです
(間違いがあれば指摘してください。)
アルゴリズムとしては、オーソドックスなものだと思います。

達人の方で、もっと高速に処理できるというスペシャルなアルゴリズムやロジックがありましたら、ぜひご教示ください。

サンプルファイルが下記からダウンロードできます。

VBASearchSum.xlsm (Excel マクロ有効ブック - 29kb)
VBASearchSum.xls (Excel 97-2003 ブック - 75kb)


拍手する

2 Comments

30246kiku says..."お暇な時にでも"

お世話になっております。

検索合計値を 140000 で実行すると、
N列から変なものが表示されますが、何が起こっているのでしょうか?

2014.09.29 20:20 | URL | #1a/xiM.Q [edit]
hatena says..."re:お暇な時にでも"

> 検索合計値を 140000 で実行すると、
> N列から変なものが表示されますが、何が起こっているのでしょうか?

確かに、おかしな結果になりますね。
ちょっとコードを見直してみます。

2014.09.29 20:36 | URL | #5uE6dEgY [edit]

Leave a reply






Trackbacks

trackback URL
http://hatenachips.blog34.fc2.com/tb.php/430-8634473c
Excel VBA をやってみた その11
副題:hatena さんに挑戦・・・っていうか、もう一度やってみた・・・ 「Excel VBA をやってみた その3(合計値検索)」とか 「再帰処理にはまる(その4 乾杯!!)」のリベンジ(?)になるか・・・返り討ちの雰囲気ですが・・・ hatena さんの記事「VBAで組み合わせ合計探索」を、自分なりにやってみたものになります。 詳細の仕様/サンプルファイルの入手は hat...
該当の記事は見つかりませんでした。