CD-003
サンプリングと二部決定図を用いたネットワーク信頼性の近似計算

○佐々木勇和・鬼塚　真（阪大）・藤原靖宏（阪大/NTT）

ネットワーク信頼性は曖昧グラフ上での節点間の接続性を評価するための重要な指標である．ネットワーク信頼性の計算は#P完全問題であるため，サンプリングを用いたアプローチによる近似計算が一般的である．本稿では，二部決定図とサンプリングを用いた新たなアプローチを提案する．提案アプローチでは，S²BDDという新たな二部決定図を構築しながら，サンプリングを実施する．提案アプローチはネットワーク信頼性の近似精度を下げることなく，サンプル数を削減可能である．さらに，近似の精度を適応的にコントロールでき，メモリ量が十分な場合では厳密解を計算できる．実データを用いた実験結果より，提案アプローチはサンプリングによるアプローチより最大で51.2倍，二部決定図によるアプローチより最大で512倍の高速であることを示す．