おねえさんを組み合わせ爆発から救う：完結編おねえさんは星になった - きしだのHatena

おねえさんを組み合わせ爆発から救うために、経路をZDDとして表したら、すっきりと経路情報が扱えました。 http://d.hatena.ne.jp/nowokay/20121018#1350528607 あとは、このZDDを効率よく構築できれば、おねえさんを救えそうです。このZDDの構築には、クヌース先生の開発したSimpathアルゴリズムを使うと非常に効率よく構築できます。 前回生成したZDDを見ると、同じノードにまとまっているものがいくつかあることがわかります。特に後半になるとどんどん同じパターンになるものがまとめられていきます。 つまり、この経路問題のZDDを構築するときには、いかに同じパターンになるものをまとめるかが鍵になるということです。 Simpathでは、辺の端だけに注目して、同じパターンになっていればそれ以降のノードを使いまわすという考え方で、ノードをまとめていきます。 つ

[habuakihiro]

感動的な結末。そして何が悪いってこれが全て悪いｗ＞『私は皆に「組み合わせ爆発のすごさ」を教えたいの！止めないで！』

[machida77]

五十六億七千万年後の未来でお姉さんは弥勒になったのかもしれない…。(組み合わせ爆発暗黒伝）

[y-kawaz]

”しかし、おねえさんは、アルゴリズム以外の技術力は非常に高度なものがあります。自身をロボットにして25万年運用できるほどの！”

[whirl]

「しかし、おねえさんは、アルゴリズム以外の技術力は非常に高度なものがあります」

[monochromekk]

どんなアルゴリズムがあっても、結局おねえさんを救うことは出来ないのか orz

[shimuya]

これ並列計算できるのかしら

[l-liroki]

泣いた

[Show]

結局お姉さんは救われないのか…

[masatoi]

BDD/ZDDに興味が出てきた

[chochonmage]

いずれにせよ、おねえさんは虚空の大顔に。

[khtokage]

全5回の組み合わせ爆発おねえさんを救う旅路も今回で終了。「空に輝く一番明るい星は、経路数を計算するコンピュータになったおねえさん自身なのかもしれません」 おねえさん……

[vid]

おねえぇぇぇさぁぁぁぁぁぁん

[trashtoy]

奥が深い・・・

[futab]

"原子ひとつでひとつのノードの情報を保持したとしても、71マスを計算するには地球と同じくらいの大きさのメモリが必要"

[inurota]

素晴らしい良コンテンツだった。「高速なアルゴリズムを手にいれたら、おねえさんは、やはり限界まで経路を数えるんじゃないでしょうか」

[houyhnhm]

そこでHadoopとか。適当。

[kaipu1224]

面白かったです。自力では6x6が限界でした(´・ω・｀)

[machupicchubeta]

algorythm

[TakamoriTarou]

完結編。メモリが4倍になるという事は、うちのマシンなら13×13までは何とか計算できるのかな－。大変勉強になりました。どこかで試させていただく。