06 2017/07 08
25262728293001
02 030405060708
09 101112131415
1617 1819202122
23 242526 27 2829
30310102030405
Click セミナー

過去のセミナー

開催日2017年4月7日(金曜日)
開催時間16時00分-17時30分
発表者湊 真一 
発表者の紹介北海道大学
タイトル深さ優先フロンティア法とその実装について
 
発表の概要
Knuthが提案したグラフ経路列挙アルゴリズムsimpathは、2点間を結ぶ経路を
列挙索引化したZDDを非常に高速に生成する。これを一般化したZDD生成法を
総称して「フロンティア法」と呼び、本プロジェクトでも多くの応用研究を
行っている。フロンティア法はグラフの各辺に固定した順序をつけ、辺を通るか
どうかをトップダウンに幅優先探索をしながら動的計画法を用いてZDDを生成
するところに特徴がある。本講演では、従来の幅優先ではなく深さ優先に
グラフをたどりながらZDDを生成するフロンティア法のアルゴリズムを提案する。
本手法は既存のBDD処理系と相性が良く、深さ優先でフロンティア法を実行
しながら、同時並行的にBDD処理系にZDDを引き渡すことができ、追加的な
制約条件を与えて絞り込むことも容易であることから、今後の活用が期待される。
開催場所VBL棟 301B
接続サイト神田オフィス