IL-001
Optimizing Network Reliability via Best-first Search over Decision Diagrams

○西野正彬・井上　武・安田宜仁（NTT）・湊　真一（京大）・永田昌明（NTT）

信頼性が高い通信ネットワークを設計することは重要である。しかしながら、そのようなネットワークを設計するためには、それ自体が指数時間かかると考えられているネットワーク信頼性評価問題を指数回解く必要があるため、計算に膨大な時間がかかる。我々はネットワーク信頼性に関する2種類の最適化問題、すなわち予算制約つき信頼性最大化問題と信頼性制約つきコスト最小化問題に対して厳密な最適解を与えることができるアルゴリズムを考案した。提案法は二分決定グラフを用いて、信頼性評価およびA* 探索でのヒューリスティック関数評価を効率化し、既存法よりも１０倍以上大規模なネットワークに対しても最適解を求めることを可能とした。