Help us understand the problem. What is going on with this article?

『フカシギの数え方』 おねえさんといっしょ:組み合わせ爆発の凄さ: docker(111)

組み合わせ爆発の凄さ

自分の好きなプログラミング言語で理解してもらおうと言語別の索引をつけてみました。私はプログラムを自分で書き換えて試さないと理論を理解できない傾向にあります。いろいろ書き換えてみようと思っています。たぶんpython。

『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!

『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!
https://www.youtube.com/watch?v=Q4gTV4r0zRs
『フカシギの数え方』 おねえさんといっしょ! みんなで数えてみよう!

同じところを 􏰀 􏰁􏰂􏰃 􏰄􏰅2度通らない経路の数を数えるアルゴリズムについて 川原 純 湊 真一 JETRO 湊離散構造処理系プロジェクト/北海道大学 情報科学研究科
http://www-erato.ist.hokudai.ac.jp/docs/img/main3.pdf

「フカシギの数え方」― 組合せ爆発に立ち向かう 最先端アルゴリズム技術 湊 真一 北海道大学 / JST ERATO
https://www.nii.ac.jp/userimg/openhouse/2013/lec_minato.pdf

フカシギおねえさん問題の高速計算アルゴリズム 岩下 洋哲 JST ERATO 湊離散構造処理系プロジェクト 2013/7/26
http://www.edu.kobe-u.ac.jp/istc-tamlab/cspsat/pdf-open/cspsat2_mtg203_iwashita.pdf

メディアラボ第11期展示「フカシギの数え方」展示解説
https://www.youtube.com/watch?v=TcjSu3_LMKY
メディアラボ第11期展示「フカシギの数え方」展示解説

「フカシギの数え方」 同じところを2度通らない道順の数
https://www.youtube.com/watch?v=ge8vy4tc_kQ
「フカシギの数え方」 同じところを2度通らない道順の数

メディアラボ第11期展示「フカシギの数え方」インタビュー
https://www.youtube.com/watch?v=SfC0W1TQcVg
メディアラボ第11期展示「フカシギの数え方」インタビュー

日本科学未来館第11期メディアラボ展示「フカシギの数え方」
http://www-erato.ist.hokudai.ac.jp/html/php/sub_html.php?id=19

フロンティア法:BDD/ZDDを用いた 高速なグラフ列挙索引化アルゴリズム
湊 真一 北海道大学 情報科学研究科 / JST ERATO 2012年8月9日
https://www.ieice.org/~netsci/wp-content/uploads/2012/08/NetSci201208_Minato.pdf

同じ所を2度通らない道順の数
http://shogo82148.github.io/letscount/

おねぇさぁぁぁぁぁん! 日本科学未来館のアニメに狂気が宿っていると話題に
https://nlab.itmedia.co.jp/nl/articles/1209/11/news104.html

おねえさんのコンピュータを作ってみた
https://shogo82148.github.io/blog/2012/09/22/letscount/

vim

Vimおねえさんといっしょ!みんなで数えてみよう!: pla.log
http://pla.asablo.jp/blog/2012/09/30/6588034

perl

「フカシギの数え方」をPerlで解く
http://hiratara.hatenadiary.jp/entry/20120916/1347796826

VB(Visual Basic)

僕も組み合わせ爆発の凄さをみんなに伝えたくなりました^0^!
https://www.nicovideo.jp/watch/sm18920750
https://box.yahoo.co.jp/guest/viewer?sid=box-l-dohryx5swstii3sh27xxkh535i-1001&uniqid=476500bf-e1ff-4810-8ee6-0777e11a4c92&viewtype=detail

PHP

『フカシギの数え方』 おねえさんといっしょ! PHPで数えてみよう!
https://sisidovski.hatenablog.com/entry/2012/09/13/023947
https://github.com/sisidovski/CombinationalExplosion

java

2012-10-19 おねえさんを組み合わせ爆発から救う:完結編おねえさんは星になった
https://nowokay.hatenablog.com/entry/20121019/1350607290

python

ZDDを自作して数え上げお姉さんを救ってみた
https://qiita.com/cabernet_rock/items/01c48dd06178ba0768f9

C++ + python

おねえさんのコンピュータを作ってみた

2012年9月15日土曜日「フカシギの数え方」の問題を解いてみた
http://handasse.blogspot.com/2012/09/blog-post.html

Graphillion

Graphillion: 数え上げおねえさんを救え / Don't count naively
https://www.youtube.com/watch?v=R3Hp9k876Kk
Graphillion: 数え上げおねえさんを救え / Don't count naively

「フカシギの数え方」から広がる世界 ~離散構造処理の現在と今後の展望~
湊 真一 北海道大学 大学院 情報科学研究科 教授
http://www.kecl.ntt.co.jp/openhouse/2014/talk/invite2/talk_minato.pdf

オープンハウス2013:基調講演「フカシギの数え方― 組合せ爆発に立ち向かう最先端アルゴリズム技術」湊真一
https://www.youtube.com/watch?v=8xqEBQc1nTo
オープンハウス2013:基調講演「フカシギの数え方― 組合せ爆発に立ち向かう最先端アルゴリズム技術」湊真一

サイエンティスト・トーク「フカシギの不思議」
https://www.youtube.com/watch?v=QVVHEZCdY_k
サイエンティスト・トーク「フカシギの不思議」

参考資料(reference)

graphillionを使ってみた
https://qiita.com/cabernet_rock/items/50f955afc16287244154

dockerで

zsh
 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を加えて出力するように。

gra.py
# 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))

実行結果は

docker/ubuntu
# python3 gra.py
12
2
0.25122714042663574
3266598486981642

9を12にしたらKilledで終わらなかった。10,11でもkilled.メモリを使い果たしているかも。

主記憶16GBだがdockerに割り当てが少ないかも。

dockerに12GBに割り当てて10で実行したら、12時間たつがまだkilledにはなっていない。

docker 作成と登録

なお、上記docker hubへ登録したものは次のように作成した。

zsh
$ docker run -v /tmp/work:/tmp/work -it ubuntu /bin/bash

起動したら

docker/ubuntu
# 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 への登録は

zsh
$ 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の著作の新版でも取り上げている題材です。

http://www.lab2.kuis.kyoto-u.ac.jp/minato/index-j.html

Knuthの名著"The Art of Computer Programming"(Vol.4, Fascicle 1, 2009年)において, 湊が考案したデータ構造「ZDD」 が項目として詳しく掲載された(日本人初)

51sFANaYORL._SX352_BO1,204,203,200_.jpg

https://www.amazon.co.jp/dp/4048930559/

日本のプログラマが、この題材をよりよくプログラミングすることにより、技術の伝搬速度を高めようとするための試みです。

ありとあらゆる言語で記述してみて、分かりやすく、応用しやすい記述を模索します。

文書履歴(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午後

このエントリーをはてなブックマークに追加

https://b.hatena.ne.jp/guide/bbutton

kaizen_nagoya
I'm a network designer.I work on TOPPERS SmallestSetProfile Kernel,MISRA-C, STARC RTL Design StyleGuide (Verilog-HDL),HAZOP,ISO/IEC15504(AutomotiveSPICE),ISO26262. I was an editor on ISO/IEC 15504.
https://researchmap.jp/blogs/blog_entries/view/81777/f691323917cc4ea12caf0b03b34c8ea0?frame_id=442673
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away