- ベストアンサー
数値を複数の群に分ける最適な組み合わせを求める方法
- 数値を複数の群に分ける方法について説明します。与えられた数値列で隣り合う数値しか同じ群に含めることはできず、各群の合計値が最も均等になる組み合わせを求めることが目標です。
- 例えば、数値列{5,2,7,12,6,15,4}を3つの群に分ける場合、{5,2,7},{12},{6,15,4}という組み合わせが最も均等です。
- 実際の問題では、組み合わせの数が増えると計算時間に影響するため、全ての組み合わせを試さずに最適な組み合わせを求める方法を提示してください。
- みんなの回答 （92）
- 専門家の回答
質問者が選んだベストアンサー
>回答No.23 amanojaku1 「2018/06/15 03:48:47」の時点で修正しました。 それ以前にコピーしている場合は注意して下さい。 数値を複数の群に分ける最適な組み合わせを求める方法 http://ashtarte.pa.land.to/utf8/smt.cgi?r+sara/&bid+000000DC&tsn+000000DC&bts+2018/06/15%2002%3A04%3A46&
その他の回答 (91)
- amanojaku1
- ベストアンサー率54% (265/488)
>ついでにgmq要素の値を算出 ついでにgmp要素の値を算出
- amanojaku1
- ベストアンサー率54% (265/488)
>回答No.29 amanojaku1 >JavaScriptを実行してデバッグ表示からgmq要素の値の変化を見た方がイメージしやすいです >回答No.30 amanojaku1 分かりやすそうな部分を説明します。 JavaScriptのプログラムと合わせて お読み下さい。 gmq要素の表示は左側が最下位の桁、右側が最上位の桁です。 5, | 2,7,12,6, | 15, | 4, >gmq=1,4,1,1 gmt=5,27,15,4 gmmin=4; gmmax=27; gmmdif=23; gtmin=6; gtmax=19; gtmdif=13; まずパターンの生成処理に入る前のgmqは上記の「1,4,1,1」になってます。 下記のkが加算されるgmqの桁を示しています。 ざっくりとしたアルゴリズムは kの初期値は「0」 kが示す「gmqの桁」(gmq[k])に1を加算 下位の桁は1クリア gmqの最上位の桁(gmq[gp-1])の値を算出 ついでにgmq要素の値を算出 gmqの最上位の桁(gmq[gp-1])の値を算出、ゼロならループする(その場合kは加算(k++)される) k=0; gmq[k]=2; ←「k=0」なので「gmq[0]++」で「gmq[0]=2」 >gmq=2,4,1,0 ←gmqの最上位の桁(gmq[gp-1])の値がゼロならループする(その場合kは加算(k++)される) k=1; gmq[k]=5; ←「k=1」なので「gmq[1]++」で「gmq[1]=5」、下位の桁は1クリア >gmq=1,5,1,0 ←gmqの最上位の桁(gmq[gp-1])の値がゼロならループする(その場合kは加算(k++)される) k=2; gmq[k]=2; ←「k=2」なので「gmq[2]++」で「gmq[1]=1」、下位の桁は1クリア >gmq=1,1,2,3 ←gmqの最上位の桁(gmq[gp-1])の値がゼロではないのでループからbreak
お礼
目から鱗です。何とも美しいアルゴリズムですね。 最上位桁に最大値を入れておくというのがポイントですね。これがforループの最後の周回で０になった時点で下位桁の繰り上がりが全て終了し、パターンの網羅が完了すると。 自分なら最上位桁のさらに上に計算用の桁を追加してしまいそうですが、最上位桁は全体から残りを引けば自動的に計算出来ますね。 単純に要素数(N)を５、群の数(GC)を３にして並べてみると理解出来ました。４以上だと組み合わせも増えてきて頭の中では難しいですね。 1,1,5 <=初期状態 1,1,3 <=１番目のパターン 2,1,2 3,1,1 4,1,0 <=繰り上がり 1,2,2 2,2,1 3,2,0 <=繰り上がり 1,3,1 2,3,0 <=繰り上がり 1,4,0 <=繰り上がり（終了） いつも見る２進数とビットの並びが逆なのでちょっと混乱してしまいましたが、分かればどうと言うことはないですね。実際は２進数ではなく(N-(GC-1))進数ですか。
- amanojaku1
- ベストアンサー率54% (265/488)
>実際にgmq要素の値を表示するように変更してもいいですし <head> <meta http-equiv="Content-Type" content="text/html; charset=Shift-JIS"> <!-- charset=Shift-JIS、UTF-8 --> <TITLE>test</TITLE> </head> <body> <script type="text/javascript"> <!-- gpa = [5,2,7,12,6,15,4]; gp = 4; gmq = Array(gp).fill(1); gmp = Array(gp).fill(0); gmmin = -1; gmmax = -1; gmmdif = -1; gtmin = -1; gtmax = -1; gtmdif = -1; gppc = 0; // gtmp, gtmq, gppc while(0<gmq[gp-1]){ gppc++; // gmq[2] = gpa.length-(gmq[0]+gmq[1]); gmq[gp-1] = gpa.length p = 0; for(let i = 0; i<(gmq.length-1); i++){ gmq[gp-1] -= gmq[i]; p += gmq[i]; gmp[i+1] = p; } gmt = Array(gp).fill(0); gmc = 0; pc = 1; for(let i = 0; i<gpa.length; i++){ if(pc<gmp.length){ if(gmp[pc]==i){ pc++; document.write(' | '); gmc++; } } gmt[gmc] = gmt[gmc]+gpa[i]; document.write(gpa[i]+','); } document.write('<br>'); document.write('>gmq='+gmq+'<br>'); document.write('gmt='+gmt+'<br>'); gmm = gmt.slice().sort((a, b) => a-b); gmmin = gmm[0]; gmmax = gmm[gmm.length-1]; gmmdif = gmmax-gmmin; document.write( 'gmmin='+gmmin+'; '+ 'gmmax='+gmmax+'; '+ 'gmmdif='+gmmdif+'; '+ '<br>'); if((gtmdif<0)||(gtmdif>gmmdif)){ gtmdif = gmmdif; gtmin = gmmin; gtmax = gmmax; gtmq = gmq.slice(); gtmp = gmp.slice(); } document.write( 'gtmin='+gtmin+'; '+ 'gtmax='+gtmax+'; '+ 'gtmdif='+gtmdif+'; '+ '<br>'); document.write('<br>'); for(let k = 0; k<(gmq.length-1); k++){ gmq[k]++; for(let i = 0; i<k; i++){ gmq[i] = 1; } gmq[gp-1] = gpa.length document.write( 'k='+k+'; '+ 'gmq[k]='+gmq[k]+'; '+ '<br>'); p = 0; for(let i = 0; i<(gmq.length-1); i++){ gmq[gp-1] -= gmq[i]; p += gmq[i]; gmp[i+1] = p; } document.write('>gmq='+gmq+'<br>'); if(0<gmq[gp-1]){ break; } } document.write('<br>'); } document.write('<br>'); document.write("<< Answer >>"+'<br>'); gppc document.write('PatternCounter='+gppc+'<br>'); gmp = gtmp; gmt = Array(gp).fill(0); gmc = 0; for(let i = 0; i<gpa.length; i++){ for(let j = 1; j<gmp.length; j++){ if(gmp[j]==i){ document.write(' | '); gmc++; } } gmt[gmc] = gmt[gmc]+gpa[i]; document.write(gpa[i]+','); } document.write('<br>'); document.write('gmt='+gmt+'<br>'); document.write( 'gtmin='+gtmin+'; '+ 'gtmax='+gtmax+'; '+ 'gtmdif='+gtmdif+'; '+ '<br>'); // --> </script> </body> </html>
- amanojaku1
- ベストアンサー率54% (265/488)
訂正です。 >// 「gtmdif、gtmin、gtmax、gtmq、gtmp」の保存 // 「gtmdif、gtmin、gtmax、gtmq、gtmp」への保存 >何となく分かってきました パターンの生成は何となくで充分です。 それよりJavaScriptを実行してデバッグ表示からgmq要素の値の変化を見た方がイメージしやすいです(実際にgmq要素の値を表示するように変更してもいいですし)。 // gmq：gpaを分割する際の配列要素数(配列) // 例えば{5},{2,7},{12,6,15,4}の場合、gmqは{1},{2},{4}
- amanojaku1
- ベストアンサー率54% (265/488)
>２進数の数学的特徴 どんなn進数でも良いですが、例は3進数です。 3桁の2進数なら「000、001、010、011、100、101、110、111」となります。
- amanojaku1
- ベストアンサー率54% (265/488)
>回答No.25 amanojaku1 >>分かりやすい説明のためです、どんなn進数でも良いです >この場合のアルゴリズムは「n進数」と言う固定的なモノではなく、「可変進数」みたいな感じです。 パターンの詳細はJavaScriptを実行してデバッグ表示を参照して下さい。
- amanojaku1
- ベストアンサー率54% (265/488)
>回答No.23 amanojaku1 >分かりやすい説明のためです、どんなn進数でも良いです この場合のアルゴリズムは「n進数」と言う固定的なモノではなく、「可変進数」みたいな感じです。
- amanojaku1
- ベストアンサー率54% (265/488)
>回答No.23 amanojaku1 >// 例えば3桁の3進数の全てのパターンを生成すると考えて下さい >// 「000、001、002、010、011、012、020、021、022、100、…、222」となります。 >// 基本は1づつ加算していて、桁の繰り上がり時に下位の桁が全てクリアされます。 >// 「222」に1が加算されるとオバーフローとなってパターンの生成は完了します。 >// このアイデアを応用しています(そのまま使っている訳ではありません) >// gmqを対象にパターンを生成しています、gmqの場合 桁の繰り上がり時に下位の桁はゼロ・クリアでは無く「1クリア」であると言う事に注意して下さい。 {5,2,7,12,6,15,4}で群の数を３にすると まず、gmq[0]は1づつ加算されます {5/2/7,12,6,15,4} {5,2/7/12,6,15,4} {5,2,7/12/6,15,4} {5,2,7,12/6/15,4} {5,2,7,12,6/15/4} ここで桁が上がります {5/2,7/12,6,15,4} gmq[1]へ桁が繰り上がりgmq[1]が2、gmq[0]が「1クリア」されます。 パターンの詳細はJavaScriptを実行してデバッグ表示を参照して下さい。
- amanojaku1
- ベストアンサー率54% (265/488)
>C++に移植したところ、性能はかなり改善しました。実用的には十分です。 >ところで、提示頂いたプログラムですが、簡単なコメントを入れて頂くことは出来ますでしょうか？各変数の意味、ブロック単位の処理内容、while文を抜ける条件などが書いてあれば処理の流れを理解出来ると思います。 こちらでは文字数制限で投稿できないので下記に投稿しました。 数値を複数の群に分ける最適な組み合わせを求める方法 http://ashtarte.pa.land.to/utf8/smt.cgi?r+sara/&bid+000000DC&tsn+000000DC&bts+2018/06/15%2002%3A04%3A46&
お礼
C++で書き直したコードを載せます。行数の関係上、デバッグ出力部は省略しています。C++11な環境でしかビルド出来ないかも知れません。 このコードで私の環境では2000万パターンを超えても５秒程度で結果が出ました。 全パターンを網羅せずに済む方法を考えてみましたがやはり難しいですね。gtmdif=0となれば以降の探索を打ち切るようにしましたが、このようなケースは稀でしょう。 この書き方だと、１番目のパターンのみfor文で生成しないため、少々特殊になってしまいます。まあ大した問題でもないですが。 コメントやデバッグ出力を除くと、アルゴリズムの肝であるwhile文は実質70行程度になりました。一見複雑と思える問題が、僅か数10行程度のシンプルなプログラムで記述出来ることに今更ながら感動しています。 数学力というよりは、問題の本質を見極めて、既知のアルゴリズムに当てはまるよう単純化する能力が必要ですね。 #include <algorithm> #include <vector> #include <iostream> using namespace std; typedef long long LLONG; // n! LLONG factorial(const LLONG n) { _ASSERT(n >= 0); if (n == 0) return 1LL; LLONG tmp = n; for (LLONG i = 1; i < n - 1; ++i) tmp *= (n - i); return tmp; } void CalcOptimalGrouping(const vector<int> gpa, const int gp) { const size_t gpa_size = gpa.size(); if (gpa_size == 0 || gp >(int)gpa_size) { printf("Invalid input."); return; } vector<int> gmq(gp, 1); const size_t gmq_size = gmq.size(); vector<int> gmp(gp, 0); const size_t gmp_size = gmp.size(); vector<int> gmt(gp); const size_t gmt_size = gmt.size(); vector<int> gtmp; int gmmin = -1; int gmmax = -1; int gmmdif = -1; int gtmin = -1; int gtmax = -1; int gtmdif = -1; LLONG gppc = 0; // gtmp, gtmq, gppc while (0 < gmq[gp - 1]) { gppc++; int p = 0; for (size_t i = 0; i < (gmq_size - 1); i++) { gmq[gp - 1] -= gmq[i]; p += gmq[i]; gmp[i + 1] = p; } fill(gmt.begin(), gmt.end(), 0); int gmc = 0; size_t pc = 1; bool filter = false; for (size_t i = 0; i < gpa_size; i++) { filter = false; if ((pc < gmp_size) && (gmp[pc] == i)) { pc++; printf(" | "); gmc++; filter = true; } gmt[gmc] += gpa[i]; if (filter || i == 0) printf("%d", gpa[i]); else printf(",%d", gpa[i]); } vector<int> gmm = gmt; sort(gmm.begin(), gmm.end()); gmmin = gmm[0]; gmmax = gmm[gmm.size() - 1]; gmmdif = gmmax - gmmin; if ((gtmdif < 0) || (gtmdif > gmmdif)) { gtmdif = gmmdif; gtmin = gmmin; gtmax = gmmax; gtmp = gmp; } if (gtmdif == 0) break; for (size_t k = 0; k < (gmq_size - 1); k++) { gmq[k]++; for (size_t i = 0; i < k; i++) { gmq[i] = 1; } gmq[gp - 1] = gpa_size; int p = 0; for (size_t i = 0; i < (gmq_size - 1); i++) { gmq[gp - 1] -= gmq[i]; p += gmq[i]; gmp[i + 1] = p; } if (0 < gmq[gp - 1]) { break; } } printf("\n"); } // 全パターン網羅出来ているかチェック（(要素数-1)から(グループ数-1)を選択する場合の数に等しい） const LLONG gppc_calc = factorial(gpa_size - 1) / ((factorial(gp - 1) * factorial((gpa_size - 1) - (gp - 1)))); // nCr = n! / (r! * (n-r)!) _ASSERT(gppc_calc == gppc); /********************* <<Answer>> *********************/ } int main() { gpa = {5,2,7,12,6,15,4}; int gp = 3; CalcOptimalGrouping(gpa, gp); }
- amanojaku1
- ベストアンサー率54% (265/488)
どうでしょうか？、JavaScriptをCに変換できたでしょうか？
お礼
C++に移植したところ、性能はかなり改善しました。実用的には十分です。 ところで、提示頂いたプログラムですが、簡単なコメントを入れて頂くことは出来ますでしょうか？各変数の意味、ブロック単位の処理内容、while文を抜ける条件などが書いてあれば処理の流れを理解出来ると思います。
お礼
コメント追加して頂きありがとうございます。今頑張って理解しているところですが、何となく分かってきました。 それにしても２進数の数学的特徴をうまくこの問題に当てはめるという発想が凄いですね。問題の本質は順列のパターンを網羅することですが、私は再帰を使うイメージしかなかったです。