1．は　じ　め　に

　通信や電力，ガス，水道，輸送などの社会インフラはネットワーク形の大規模システムであり，その信頼性を正確に評価する手法は重要である．伝統的に，ネットワークの信頼性は「指定されたノード間の連結確率」によって評価されてきた．これは，「各リンクが独立かつ確率的に故障するとき，ノード間に稼動リンクのみから成るパスが存在する確率」として定義される^(1),(2)．連結性はネットワークが機能するための必要条件となるため，根本的な尺度とみなされる．例を示すと，図1(a)では，各リンクの稼動率をとすると，黒ノードの連結確率はとなる．

　ネットワーク信頼性の概念は単純であるが，正確な評価は計算量的に極めて困難である．例えば，図1(b)のように僅か7リンクのネットワークでも，黒ノードの連結確率はのようにかなり複雑になる．これは，リンク数に対して指数的な故障パターンが存在するためであり，計算複雑性の観点では#P完全というクラスに属する⁽³⁾．何十年にもわたって，数多くのアプローチが研究されてきたが⁽⁴⁾，近年ではBDD（Binary Decision Diagram)⁽⁵⁾というデータ構造を用いた手法^(6)～(8)が最も効率的と考えられている⁽⁴⁾．様々な故障パターンをBDDとしてコンパクトに表し，動的計画法によって連結確率を効率的に計算する^(注1)．

　従来は「独立なリンク故障における連結性」という単純な問題が中心だったが，近年，より複雑な問題での研究が進んでいる．例えば，停電などによりノードも故障する．連結性だけでなく混雑も考慮したい．故障は独立事象とは限らない．信頼性を評価するだけでなく最大化する設計法も欲しい．複数事業者にまたがるネットワークの信頼性も評価したい．本稿では，これらの課題に取り組んだ一連の研究を，二つの着眼点に沿って紹介する．3．ノード故障など複雑な条件でのBDD構築．4．最適設計などのための“bound”としてのBDD利用．

2．ネットワーク信頼性評価とBDD