組合せ爆発単語

11件

クミアワセバクハツ

3.7千文字の記事

掲示板へ

記事編集

組合せ爆発とは、皆に教えたいすごい神秘である。

私は皆に「組合せ爆発のすごさの概要」を教えたいの！止めないで！

ある問題について、場合の数を組み合わせ的に数え上げることができるが、問題を大きくすると答えが爆発的に大きくなる現象を組合せ爆発という。
組合せ爆発の発生する問題のひとつで、自己回避歩行（Self-Avoiding Walk: 外部リンク）と呼ばれているものが、2012年に日本科学未来館の展示「フカシギの数え方」として取り上げられ、動画がYouTubeにも投稿された。

組み合わせの数え方は、碁盤目状に線が引かれた面積n×n(n²)の正方形の、一番左上の点Sから一番右下の点Gまで行くのに何通りあるか？を
「遠回りしてもいいが、同じ点を通ってはいけない」
という条件で調べるもので、1×1（1²）のときは2通り、2×2（2²）のとき12通り、3×3（3²）のとき184通りと一気に複雑化する傾向がある。

ひょんなことから始まった「組み合わせの数え方」を教えるお姉さんが、10×10の組み合わせは？という疑問に答えようとした時に発したセリフで、それはスーパーコンピューターを利用して25万年もの年月を費すこととなった。

私は皆に「組合せ爆発のすごさの関連動画」を教えたいの！止めないで！

サ、次ハ、11×11ネ

ゆっくりによる16×16までの読みあげ(まさかの公式続編)

そしておねえさんは星になった・・・

この問題は2014年現在、26×26までの経路の数が判明している。最新の情報はオンライン整数列大辞典の「A007764」でも確認できる。

この値の算出には宇宙の年齢を超える年月が必要となる……わけではなく、「ZDD」と呼ばれる最適化アルゴリズムなどが用いられている（※簡単に求める公式は存在しない）。

なお、25×25および26×26の計算には「一般市民プログラマー」が貢献している。21×21の数え上げに成功後もアルゴリズム開発を続けていた科学技術振興機構の研究チームのもとに、ある日「高速な解き方を思いついたので見てもらえませんか？」というメールが届き、やり取りを重ねたところ「プロも驚くアイデア」を提案したという。この人物は「アマチュアプログラマー」の肩書きで論文の共著者にも名を連ねている。

格子の大きさ	経路の数（通り）
1×1	2
2×2	12
3×3	184
4×4	8,512
5×5	1,262,816
6×6	575,780,564
7×7	789,360,053,252
8×8	3,266,598,486,981,642
9×9	41,044,208,702,632,496,804
10×10	1,568,758,030,464,750,013,214,100
11×11	182,413,291,514,248,049,241,470,885,236
12×12	64,528, 039,343,270,018,963,357,185,158,482,118
13×13	69,450,664,761, 521,361,664,274,701,548,907,358,996,488
14×14	227,449,714,676,812,739, 631,826,459,327,989,863,387,613,323,440
15×15	2,266,745,568,862,672,746,374,567, 396,713,098,934,866,324,885,408,319,028
16×16	68, 745,445,609,149,931,587,631,563,132,489, 232,824,587,945,968,099,457,285,419,306
17×17	6,344,814,611, 237,963,971,310,297,540,795,524,400,449, 443,986,866,480,693,646,369,387,855,336
18×18	1,782,112,840,842,065,129, 893,384,946,652,325,275,167,838,065,704, 767,655,931,452,474,605,826,692,782,532
19×19	1,523,344,971,704,879,993,080,742,810, 319,229,690,899,454,255,323,294,555,776, 029,866,737,355,060,592,877,569,255,844
20×20	3,962,892, 199,823,037,560,207,299,517,133,362,502, 106,339,705,739,463,771,515,237,113,377, 010,682,364,035,706,704,472,064,940,398
21×21	31,374,751,050,137,102, 720,420,538,137,382,214,513,103,312,193, 698,723,653,061,351,991,346,433,379,389, 385,793,965,576,992,246,021,316,463,868
22×22	755,970,286,667,345,339,661,519,123, 315,222,619,353,103,732,072,409,481,167, 391,410,479,517,925,792,743,631,234,987, 038,883,317,634,987,271,171,404,439,792
23×23	55,435,429, 355,237,477,009,914,318,489,061,437,930, 690,379,970,964,331,332,556,958,646,484, 008,407,334,885,544,566,386,924,020,875, 711,242,060,085,408,513,482,933,945,720
24×24	12,371,712,231,207,064,758, 338,744,862,673,570,832,373,041,989,012, 943,539,678,727,080,484,951,695,515,930, 485,641,394,550,792,153,037,191,858,028, 212,512,280,926,600,304,581,386,791,094
25×25	8, 402,974,857,881,133,471,007,083,745,436, 809,127,296,054,293,775,383,549,824,742, 623,937,028,497,898,215,256,929,178,577, 083,970,960,121,625,602,506,027,316,549, 718,402,106,494,049,978,375,604,247,408
26×26	17,369,931,586,279, 272,931,175,440,421,236,498,900,372,229, 588,288,140,604,663,703,720,910,342,413, 276,134,762,789,218,193,498,006,107,082, 296,223,143,380,491,348,290,026,721,931, 129,627,708,738,890,853,908,108,906,396

数え上げおねえさん問題以外の組合せ爆発の例

「フカシギの数え方」があまりに有名になってしまったため「組合せ爆発＝おねえさん問題」という認識で語られがちだが、自己回避歩行の問題はあくまで一例にすぎない。

組合せ最適化の有名問題には「巡回セールスマン問題」や「ナップサック問題」などが存在するほか、囲碁やオセロの完全解析も盤面が大きくなるごとに計算量が爆増する。身近な例だとカーナビや乗換案内などの経路検索や、自動改札機における運賃計算などでも組合せ爆発が発生している。

Wikipediaの「組合せ爆発」の記事には、関連項目として「欧州連合の言語」へのリンクが貼られている。欧州連合（EU）では加盟各国の言語をEUの公用語としており、法令や公文書を全24言語で作成している。翻訳パターン数の算出は ₂₄P₂ = 552 通りと簡単に求められるものの、翻訳作業には年間で11億ユーロものコストがかかっており、実務上の問題となっている。

ニコニ広告で宣伝された記事

ニコニ広告 (単) 記事と一緒に動画もおすすめ！

提供：シバ

224848300pt

2*2*2と3*3*3の図

この記事の掲示板に最近投稿されたピコカキコ

【おねえさんといっ...