m回の買い物イベント(トランザクション)があったとする n種類の商品:があったとする Tは買い物イベントの集合とする。買い物イベントのデータベースとも言う はT、すべての買い物イベントによって購入されたアイテムの「のべ総数」であり、買い物イベントデ…

加算演算子 + これは集合で言えば、Union irb(main):002:0> require 'zdd' => true irb(main):003:0> univ = ZDD::itemset("a b c d e f g") => a b c d e f g irb(main):004:0> a = ZDD::itemset("a") => a irb(main):005:0> b = ZDD::itemset("b") => b ir…

2.1 ZDDライブラリをrequireで取り込む $ irb として対話モードで始めてみる 対話モードになったら、まず、zddをgemで入れた先をLOAD_PATHする > $LOAD_PATH.push("/home/ryamada/.gem/ruby/2.2.0/gems/zdd-1.0.0-linux/lib/nysol/") その上で > require 'zd…

nysol_zddのインストールはこちらを参考に rubyの本当の基礎 $ ruby myrb.rb と実行することもできるし 対話モードは $ irb とすればよい 対話モードを終了するには > quit rubyの調べもの

nysolにZDDがある。それはrubyのラッパーになっているらしい rubyは初めてだけれども、やってみる Linux (Manjaro)で始める 『ZDD Ruby Package Documentation』

個のサンプルがある 個々のサンプルは長さのベクトルでその要素は 通りのベクトルが作れる そこから個の相互に異なるサンプルを取る、その場合の数は この本の長0,1ベクトルを、0,1分岐木の「あり、なし」としてとらえ、ZDD表現するとする それは制約付き整…

from graphillion import GraphSet import pickle from itertools import chain import networkx as nx import matplotlib.pyplot as plt # ユニバースの要素数nに # [(1,2),(2,3),...,(n-1,n)]というユニバースとする n = 50 universe = [] for i in range(…

PythonのGraphillionモジュールではユニバースと呼ぶ全体グラフを定めた上で、サブフラフの集合をZDDデータ構造として持つ その持ち方をしているのがGraphSetクラス それが実際にどういう持ち方をしているのかを確認したい 実際GraphSetクラスのオブジェクト…

昨日の記事で、pythonのGraphillionパッケージを使ってみた 大まかなことが見えたので、整理し直して、チュートリアルの例から少し離れて、自分なりにGraphillionを使ってみるつもりで書いてみる python自体にも不慣れなので、その辺りも確認しながら まず、…

超高速グラフ列挙アルゴリズム?〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ?作者: ERATO 湊離散構造処理系プロジェクト,湊真一出版社/メーカー: 森北出版発売日: 2015/04/08メディア: 単行本（ソフトカバー）この商品を含むブログ (4件) を見る…

ZDDとSimPathをやってみた(こちら) ZDDは「平面的なグラフ」で特に効果があるそうだ これは、いかにもそんな印象もあるけれど、その背景って…? 『平面分離定理』 頂点数nの平面(に描ける)グラフは、３つの頂点集合に分けることができて、その分け方ではフロ…

ZDDは組み合わせの圧縮表現 Simpathはグラフの経路全網羅のためのZDD構築のアルゴリズム(こちら) アルゴリズムの説明をしてもらったけれど、どうやるのだか分らなかったのでRで、べたべたに書いてみることにする グラフがある を定める とエッジに順序を定め…

論理学をつくる作者: 戸田山和久出版社/メーカー: 名古屋大学出版会発売日: 2000/10/10メディア: 単行本購入: 27人 クリック: 330回この商品を含むブログ (108件) を見る これを『ぱらぱらめくる』ことへのイントロ こちらやこちらで知識をグラフ・ハイパー…

Swarm intelligence(こちらとか)では、各所で勝手に「よかれ」と思ったことをやる その上で、いつの間にやら、効率的な状態にしてしまいたい ZDD(こちら)では組合せ爆発を圧縮してある 圧縮にあたっては、「使いまわせるノード」は使いまわす Swarm intellig…

CUDDのパッケージをとって来よう ホームパージ 圧縮ファイル Windowsでmakeやgccを動かすためにCygwinを入れよう Cygwinを入れるとLINUXコマンドがWindowsのコマンドプロンプトで動くようになる！のですね(こちらやこちら) Cygwinを入れるのもずいぶん久しぶ…

昨日、ZDDでクリークを列挙する話を書いた グラフ情報(隣接関係の情報)からクリークを列挙するのは大変だ その大変さは、0/1のべき乗をZDD化するより、グラフ情報からZDD化する方が難しい(らしい)ことと関係しそうだ 超立方格子上の点のハミング距離に適当に…

ZDDについて勉強中 グラフのクリークの演算がありそうなCUDDというのがある PDF ダウンロードなどのサイト ダウンロード用圧縮ファイル置き場が見つかりにくいけれど... こちら PDFにある記載 Graph operators Cudd_zddCliques: Finds the set of all clique…

xは行の真偽値表(２列) library(igraph) bzdd <- function(x,type="zdd"){ v <- c(x) K <- log(length(v),2) # グラフに描くときに、判断分岐の高さごとにy軸座標を与えたいので、その値 lay.y <- c() for(i in 1:K){ lay.y <- c(lay.y,rep(i,2^(i-1))) } # …

置換集合向けの決定木ダイアグラムpiDD 資料１ 資料２ BDD/ZDDは組み合わせ集合の空間の部分をうまく表現する仕組み BDDの構成アルゴリズム BDDをべたべたにRで書いてみようこちら piDDは置換(順列)の集合の空間の部分をうまく表現する仕組み(らしい) ルービ…

ZDD:ゼロ抑制BDD 組合せ論で力を発揮する に行きつく経路が多いときに有用である BDDと違う点 節点の解釈が違う 終点ははないこともある 節点からの２本のエッジが同一のノードに接続することもある 節点数が節約されることがある BDDではノードが「Primitiv…

日本語総説はこちら 組合せ発散に対する、この方法の効果はこちらの動画と実行例コードで BDD:binary decision diagram 個の２分岐がの場合を作る。それを表したのが二分決定木(binary decision tree) BDDは二分決定木を簡略したグラフ の３分岐の「○、×」が…