ZDD入門-お姉さんを救う方法
3. 前回のあらすじ • 前回のランダムフォレスト(竹迫さん)は 決定木を「特徴をランダムに選んで、決 定しきらなくても適当に打ち切って、と にかくたくさん作って多数決！」だった • 今回も決定木だが「特徴を全部使って、 巨大な決定木をつくるぞ！」という話 3 4. 決定木が表現するもの • 0/1の特徴がたくさん与えられて0/1を返す関数 • 具体例： • 論理式(項が特徴、式の値が返り値) • 部分集合の族(各頂点が部分集合xに含まれる かどうかが特徴、その部分集合が族に含まれ るかどうかが返り値) 4
BDD/ZDDを基盤とする 離散構造と演算処理系の最近の展開 Recent Topics on Discrete Structures and Algebraic Operations Based on BDDs/ZDDs 湊 真一 Shin-ichi MINATO アブストラクト 二分決定グラフ（BDD: Binary Decision Di
BDD/ZDDを基盤とする 離散構造と演算処理系の最近の展開 Recent Topics on Discrete Structures and Algebraic Operations Based on BDDs/ZDDs 湊 真一 Shin-ichi MINATO アブストラクト 二分決定グラフ（BDD: Binary Decision Diagram）は，論理関数を効率良く表現するデータ構造の一種であ る．BDD に関する処理技法は主に VLSI 設計技術の分野で 1990 年代に発展したものであるが，近年ではデータマイニング や知識発見の分野でも効果的に活用されるようになってきている．中でも，ゼロサプレス型 BDD（ZDD: Zero-suppressed BDD）と呼ばれる BDD の変化形は，データベース解析の多くの問題で見られるような「疎な組合せの集合」を扱う場合に 特に効果
「フカシギの数え方」の問題を解いてみた
先日、「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のため
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
