ZDD 超高速グラフ列挙アルゴリズム 著者:湊 真一

羽藤：下の0, 1は何を示しているのか
石井：可能性がある/ない
羽藤：クリークの時は？
石井：同じ経路を二度通らずに行ければ1
羽藤：二分木にしている意味は？
石井：各リンクを通る/通らない
どういう風なグラフを考えた時でも絶対に網羅できる
取得するか、選ぶか否かの2通り

石井：charge:棚に仕入れる
上の図と下の図
cを取った取ってないと、λを取ってないを1つのグラフで表す
<上の{}に入っているものが、下にたどっていって実現できれば1、できなければ0>

質問
羽藤：何に使うかのイメージはあるか
石井：行動モデルで経路選択をしているときにどういう経路を通るかをZDDで、というのはわかるが…
羽藤：価値関数を計算するときに一番いい気がするが
価値関数の計算は将来起こる経路の期待値、逆行列を用いて計算しているが一番時間がかかる
ありうる活動パターンはグラフ理論で構成できる、計算スピードが上がって表現しやすくなる
駐車場だとどうか？
渡邉：アルゴリズムは理解できたが、経路列挙以外でどう使うかイメージできない
羽藤：経路列挙は深い
渡邉：今の駐車場に停める停めないで効用を計算できる
羽藤：熊野みたいに自宅再建だと、集団移転、みたいに書ける
仮設で3,4年などとなると経路が増える　選択肢が狭まる、こういう方法が有効
あらかじめ経路を列挙しているから経路探索しなくてよい、がこのアルゴリズムの一番便利なところ
自分の計算アルゴリズムを考えるときにこういう方法があるということを覚えておくとよい
米澤：全部の経路をプリズムでの時空間ネットワークで考えればいいのでは？
石井：それも経路数を減らすための方法
羽藤：実装できそう？
石井：コードをいじっていないので何とも…
羽藤：何度も繰り返すから、ノード数によってはこれの方が早い　ハミルトン閉路、オンデマンドバスのルート選択だとこれが一番早い