二分決定グラフによる探索型組合せ問題の解法での組合せ的爆発抑制法

• 奥乃, 博

書誌事項

タイトル別名

• Reducing Combinatorial Explosions in Solving Search - Type Combinatorial Problems with Binary Decision Diagrams
• 人工知能

抄録

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

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 35 (5), 739-753, 1994-05-15

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

キーワード

• 論文

詳細情報

• CRID: 1050845762817910144
• NII論文ID: 110002722709
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00014228/
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles