- 辺に適当な順(例えば、sからの幅優先順)をつけ、それらを e1,・・・,em とします。
- 解である s-t パスは辺の集合として表すことができます。
- Simpath は、s-t パスを表現する辺集合をすべて集めたもの(=集合族)を考え、そのような集合族を表現する ZDD を直接トップダウン的に構築するアルゴリズムであると言えます。
※ここで構築するZDD は、共有することが可能なノードでも共有されていないことがあるので、厳密には ZDD の定義に反します。このような ZDD を PZDD(Pseudo ZDD)と呼ぶことにします。
最新コメント