おねえさんを組み合わせ爆発から救うために、経路をBDDとして表しました。 http://d.hatena.ne.jp/nowokay/20121017#1350435805 ところで、「F」に至る経路で、ある辺を通るとした場合に即「F」となっているものが半分あります。 その節点を使うとしたときに、結果が偽になるのであれば、それは節点ごと不要だと言えます。そこで、そのような節点は省略してしまいます。 このような図を、ゼロ抑制BDD(Zero suppressed BDD)、略してZDDと呼びます。 「F」をすべて省略することもできます。ただし、BDDとは違って、どちらでも同じ結果になる場合も、それぞれの接続を表示する必要があります。 そうすると、2x2マスの経路でも、次のように表すことができます。かなり節点の数が減っていることがわかります。 「T」に至るパスの数が、経路の数です。 さまざまな