組合せ爆発単語

クミアワセバクハツ
  • 6
  • 0pt
掲示板へ

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

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

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

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

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

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

サ、次ハ、11×11ネ

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

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

この問題は2014年現在、26×26までの経路の数が判明している。
最新の情報は数列データベース該当記事海外サイトへexit)などでも確認できる。

格子の大きさ 経路の数(通り)
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

関連商品

関連コミュニティ

私は皆に「組み合わせ爆発のすごさの関連コミュニティ」を教えたいけど見つからないの!か教えて!

関連リンク

関連項目

【スポンサーリンク】

  • 6
  • 0pt
スマホ版URL:
https://dic.nicovideo.jp/t/a/%E7%B5%84%E5%90%88%E3%81%9B%E7%88%86%E7%99%BA

この記事の掲示板に最近描かれたお絵カキコ

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

組合せ爆発

47 nの3乗
2016/09/17(土) 21:04:24 ID: D7vsc7Bxcy
アルゴリズム化できるものは関数化できるからプログラミングだけど、
ビジービーバー関数や、クサイ関数は計算すら出来ないらしい
48 ななしのよっしん
2016/11/06(日) 21:01:29 ID: JIRZVyaylE
1×1×1×1だと
267×4!で6408かな

267も数え上げるの大変だった・・・
49 48
2016/11/07(月) 00:00:26 ID: JIRZVyaylE
プログラム組んでみたら6432パターンになった・・・あれ?
50 連投スマソ
2016/11/07(月) 07:25:57 ID: JIRZVyaylE
またさらに1次元増やして1×1×1×1×1でやってみた
50パターンえた・・・?
時間かかりすぎて終わらん
もうここらへんでやめておこ
51 ななしのよっしん
2017/02/17(金) 19:10:16 ID: +3JvGNuS7a
(1つ前の結果÷今の結果)÷(1つ前の結果÷2つ前の結果)が
10×10以降どんどん3.043・・・と、どんどん一定値に収束していってるから
なんとなく次の数字の近似値が予測できるよ!桁数くらいは合うんじゃないかな?
52 ななしのよっしん
2017/02/23(木) 09:44:20 ID: MzhZPOSAE/
対数をとった数列の階差数列の階差が一定値に収束するみたい
53 ななしのよっしん
2017/11/20(月) 21:16:10 ID: f7QpjJPree
スパコンで計算していたお姉さん、まさかの量子コンピューターで救われる
54 ななしのよっしん
2017/12/14(木) 23:55:32 ID: SCdliAQJ1I
うわあすごい計算スピード
 もっといっぱい教えられるね!
55 ななしのよっしん
2018/03/25(日) 23:12:27 ID: 2XBCUQmrkd
カーズドン引き
56 ななしのよっしん
2019/04/15(月) 06:22:24 ID: qs5onhpFDU
10×10で25万年かかるなら もし 「ボルツマンの」が現れるまでの時間(10^(10^50)年)だけかけたら いくつ×いくつまで数えられるのだろうか・・・!?

急上昇ワード