組み合わせ爆発の凄さ
私（自分）の好きなプログラミング言語で理解してもらおうと言語別の索引をつけてみました。私はプログラムを自分で書き換えて試さないと理論を理解できない傾向にあります。いろいろ書き換えてみようと思っています。たぶんpython。
『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！
『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！
同じところを 2度通らない経路の数を数えるアルゴリズムについて 川原 純 湊 真一 JETRO 湊離散構造処理系プロジェクト/北海道大学 情報科学研究科
「フカシギの数え方」― 組合せ爆発に立ち向かう 最先端アルゴリズム技術 湊 真一 北海道大学 / JST ERATO
フカシギおねえさん問題の高速計算アルゴリズム 岩下 洋哲 JST ERATO 湊離散構造処理系プロジェクト 2013/7/26
メディアラボ第11期展示「フカシギの数え方」展示解説
「フカシギの数え方」 同じところを2度通らない道順の数
メディアラボ第11期展示「フカシギの数え方」インタビュー
日本科学未来館第11期メディアラボ展示「フカシギの数え方」
フロンティア法:BDD/ZDDを用いた 高速なグラフ列挙索引化アルゴリズム
湊 真一 北海道大学 情報科学研究科 / JST ERATO 2012年8月9日
同じ所を２度通らない道順の数
おねぇさぁぁぁぁぁん！ 日本科学未来館のアニメに狂気が宿っていると話題に
おねえさんのコンピュータを作ってみた
vim
Vimおねえさんといっしょ！みんなで数えてみよう！: pla.log
perl
「フカシギの数え方」をPerlで解く
VB(Visual Basic)
僕も組み合わせ爆発の凄さをみんなに伝えたくなりました^0^！
PHP
『フカシギの数え方』 おねえさんといっしょ！ PHPで数えてみよう！
java
2012-10-19 おねえさんを組み合わせ爆発から救う：完結編おねえさんは星になった
python
ZDDを自作して数え上げお姉さんを救ってみた
C++ + python
おねえさんのコンピュータを作ってみた
2012年9月15日土曜日「フカシギの数え方」の問題を解いてみた
Graphillion
Graphillion: 数え上げおねえさんを救え / Don't count naively
「フカシギの数え方」から広がる世界 ~離散構造処理の現在と今後の展望~
湊 真一 北海道大学 大学院 情報科学研究科 教授
オープンハウス2013：基調講演「フカシギの数え方― 組合せ爆発に立ち向かう最先端アルゴリズム技術」湊真一
サイエンティスト・トーク「フカシギの不思議」
参考資料(reference)
graphillionを使ってみた
dockerで
docker run -v /tmp/work:/tmp/work -it kaizenjapan/zdd /bin/bash
/tmp/workはdockerを起動する前に存在するフォルダ。:/tmp/workは、docker上にできるが、docker終了後はdocker hubに登録してもdocker上には残らないので、docker hubに登録する場合は、必要なデータは/home/pythonのような入れ物を作って保存しておくと良い。
ソフトが導入済みの状態。プログラムは/home/pythonに入れてある。
プログラムは下記のようにprintを加えて出力するように。
# https://qiita.com/cabernet_rock/items/50f955afc16287244154
# https://qiita.com/kaizen_nagoya/items/f309b0c2bb015bbc71c3
# https://qiita.com/kaizen_nagoya/items/3a8d89f095489b6e1f56
# https://qiita.com/kaizen_nagoya/items/819f10124ec453b7ef27
# 必要なモジュールのインポート
from graphillion import GraphSet
import graphillion.tutorial as tl
import time # 計算時間を調べる。
# グリッドのサイズを指定
universe = tl.grid(2, 2)
GraphSet.set_universe(universe)
tl.draw(universe)
start = 1 # スタート位置
goal = 9 # ゴールの位置
paths = GraphSet.paths(start, goal)
print (len(paths))
#
key = 4 # 1箇所目
treasure = 2 # 2箇所目
paths_to_key = GraphSet.paths(start, key).excluding(treasure)
treasure_paths = paths.including(paths_to_key).including(treasure)
print (len(treasure_paths))
#
universe = tl.grid(8, 8) # 9×9のグリッド
GraphSet.set_universe(universe)
start = 1
goal = 81
s = time.time() # 計算開始時刻
paths = GraphSet.paths(start, goal)
print (time.time() - s )# 計算時間
print (len(paths))
実行結果は
# python3 gra.py
12
2
0.25122714042663574
3266598486981642
9を12にしたらKilledで終わらなかった。10,11でもkilled.メモリを使い果たしているかも。
主記憶16GBだがdockerに割り当てが少ないかも。
dockerに12GBに割り当てて10で実行したら、１２時間たつがまだkilledにはなっていない。
docker 作成と登録
なお、上記docker hubへ登録したものは次のように作成した。
$ docker run -v /tmp/work:/tmp/work -it ubuntu /bin/bash
起動したら
# apt update;apt -y upgrade
# apt install -y python3 python3-pip vim wget curl sudo apt-utils
# pip3 insatll networks matplotlib graphillion
apt installでvim以降は個人的に利用するために入れたもの。
docker hub への登録は
$ docker commit 04b268b5a441 kaizenjapan/zdd
$ docker push kaizenjapan/zdd
04b268b5a441 の値は、docker psでもわかるが、コマンドプロンプトにも値が出てる。
関連資料(related document)
今日のpython error:ModuleNotFoundError: No module named
https://qiita.com/kaizen_nagoya/items/3a8d89f095489b6e1f56
今日のpython error: invalid keyword argument for this function
https://qiita.com/kaizen_nagoya/items/819f10124ec453b7ef27
後書き(post script)
この資料は、Knuthの著作に出てくる問題で、湊 真一 が考案したZDD方式をKnuthの著作の新版でも取り上げている題材です。
Knuthの名著"The Art of Computer Programming"(Vol.4, Fascicle 1, 2009年)において, 湊が考案したデータ構造「ZDD」 が項目として詳しく掲載された（日本人初）
日本のプログラマが、この題材をよりよくプログラミングすることにより、技術の伝搬速度を高めようとするための試みです。
ありとあらゆる言語で記述してみて、分かりやすく、応用しやすい記述を模索します。
文書履歴(document history)
ver. 0.01 初稿 20200121 午前
ver. 0.02 プログラム追記 20200121 昼
ver. 0.03 docker登録 20200121 午後
ver. 0.04 Knuth追記 20200122 午前
ver. 0.05 The Art of Computer Programming 表紙追記 20200122午後
ver. 0.06 ありがとう追記 20230505
最後までおよみいただきありがとうございました。
いいね 💚、フォローをお願いします。
Thank you very much for reading to the last sentence.
Please press the like icon 💚 and follow me for your happy life.
