[ツリー表示へ] [ワード検索] [Home]
タイトル ： Re^13: 組み合わせ合計検索 つづき 投稿日 ： 2023/08/31(Thu) 16:45 投稿者 ： 魔界の仮面弁士
| > 詳細値：を 多くした場合 198個 えっ。本当にそれだけのものが必要なのですか? そもそも何のために、今回の『組合せ最適化問題』を解こうとしているのでしょうか。 「XY 問題」に陥ることを防ぐためにも、まずは目的を示していただけますか。 > OutOfMemoryException はハンドルされませんでした。 > 種類 'System.OutOfMemoryExceptin' の例外がスローされました。 > 件数が悪さしているのでしょうか？ 高校1年で習う 数学A の組み合わせ計算を思い出してみてください。 要素の数を N とした場合、重複を許さない組み合わせ総数は「((2 の N 乗) - 1) 通り」です。 累乗計算なので、要素数の増加に付けて、組み合わせ数が加速度的に巨大数化していきます。 1 要素の場合、組み合わせ総数は 1 です。 2 要素の場合、組み合わせ総数は 3 です。 3 要素の場合、組み合わせ総数は 7 です。 4 要素の場合、組み合わせ総数は 15 です。 5 要素の場合、組み合わせ総数は 31 です。 10 要素の場合、組み合わせ総数は 1,023 です。 20 要素の場合、組み合わせ総数は 1,048,575 (104万) です。 30 要素の場合、組み合わせ総数は 1,073,741,823 (10億)です。 100 要素の場合、組み合わせ総数は 1,267,650,600,228,229,401,496,703,205,375 (126穣) です。 198 要素の場合、組み合わせ総数は 0.4那由他(4017阿僧祇)です。 ※正確には 401,734,511,064,747,568,885,490,523,085,290,650,630,550,748,445,698,208,825,343 通り。 今のロジック(枝切りとか、初回検出で打ち切り)だけでは、 メモリー的にも時間的にも無理がありそうですよね。 No12137 でやろうとしていたように、組み合わせる個数に制限を設けて、 1 個以上 10 個以下 の範囲での調査に制限したとしても、 20 要素では 184,756 (18万) 通り 30 要素では 30,045,015 (3004万) 通り 40 要素では 1,221,246,131 (12億) 通り 50 要素では 13,432,735,555 (134億) 通り 100 要素では 19,415,908,147,835 (19兆)通り 150 要素では 1,258,067,642,133,715 (125兆)通り 198 要素では 21,381,429,129,671,215 (2京)通り 200 要素では 23,683,917,463,480,695 (2京)通り という、ものすごい量の組み合わせを調査せねばなりません。 ※なお、異なる n 個のものの中から異なる r 個を取り出す場合の組み合わせ数は nCr = n! / ( r! * (n - r)! ) で求められます。10 個以下の組み合わせなら nC1 + nC2 + nC3 + … + nC10 なΣ演算。 仮に、一つのノードが 16 バイトを消費していたと仮定すると、 単純計算で、4GB のメモリー消費で保持できる組み合わせは 2.6 億通りしかありません。 さすがに現状の処理では追い付かないので、要件の見直しが必要になりそうですね。 ※実際には総当たりでは無く、枝切りロジックを仕込んだり、合致する組み合わせを 一つ見つけた時点でそこで調査が打ち切るようにはなっていますが、処理時には 上記以外のメモリー消費も必要であるため、限界性能は単純には算出できません。 |
をクリックするとツリー全体を一括表示します） - 組み合わせ合計検索 つづき - たけし 23/08/11-06:34No.12125