著者

奥乃 博

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.35, no.5, pp.739-753, 1994-05-15

被引用文献数

8

---

二分決定グラフ(BDD)で組合せ問題の全解を同時に求めることを検討する。この問題での課題は、計算途中で生じる組合せ的爆発を避け、同じ計算機資源のもとでできるだけ大きな問題が解ける手法を開発することである。従来から知られていたBDDの問題点は、最終ノード数を最小にする最適変数順序を求めることである。本稿では、組合せ問題にBDDを適用する場合には最大ノード数が重要であること、および、それが変数順序だけでなく制約組合せ順序の影響を受けることを指摘する。次に、最大ノード数を最小にする制約順序と変数順序の最適解を見つけるアルゴリズムCCVOを提案する。さらに、最大ノード数が大き過ぎて計算ができない場合には、オンライン版分割統治法を使用する解法を提案し、その分割ヒューリスティックを提案する。これらの手法により、12?Queensを128Mbyte主記憶で解くことができ、また、分割統治法により13?Queensと4次の魔法陣を解くことができた。二分決定グラフでは途中結果がすべて保存されているので、オンライン型分割統治法による解法は、オフライン型分割統治法よりも高速である・