並列タイトル等グラフ部分構造を扱う新規索引構造と高速コンパイル法に関する研究
一般注記Knowledge compilation has been intensely studied in the field of artificial intelligence.Knowledge compilation is, roughly describing, take some data with “certain” property,then change it into a data structure, which supports varieties of queries or transformation. Here, the data structure is called tractable indexing structure and the process to change the data into tractable indexing structure is called compilation. Among the tractable indexing structures, BDD is the most fundamental and has been studied for a long time.Recently, there have been two directions in the subsequent studies based on BDDs.The first direction is to enable succinctness. Darwiche et al. presented a knowledge compilation map. In knowledge compilation map, some superset structures of BDD are proposed. While the index size of BDDs are bounded with path-width of the input CNF, these superset structures in knowledge compilation map is bound with tree-width of the input CNF.The second direction is the application to graph-substructure. ZDD is a tractable indexing structure that changed the default value of BDD from “do not care” to “does not exist”. This property of ZDD called zero-suppression makes ZDD to be appropriate to represent a set of family, especially graph-substructures. As an efficient compilation method of ZDD, frontier-based search is known.An important issue of today is how to redesign ZDD and frontier-based search to achieve more efficient compilation of graph-substructures. ZSDD is a remarkable preceding work to cope with this task. ZSDD is an extension of ZDD and more succinct than ZDD in general. As a result, ZSDD’s compilation method runs faster than that of ZDD’s. However, since ZSDD is strongly structured, its compilation method become more complicated than ordinal frontier-based search. As a result, the overhead of computation is inevitable. The key issue to make the compilation much faster is how to reduce the overhead of computation.In this thesis, we introduce a new tractable indexing structure and a compilation method for graph-substructures. Our tractable indexing structure is called structured Z-d-DNNF and its compilation method is called merging frontier-based search. Since our structure is less structured than ZSDD, the capability of our structure to support query or transformation is lower than that of ZSDD. However, as trade-off, its simple structure makes the compilation method more efficient. With the theoretical analysis and the experimental result, we show that our compilation method runs faster than the previous method in many cases.In Chapter 3, we introduce our structure, structured Z-d-DNNF. We introduced zero-suppression to structured Z-d-DNNF same as ZDDs or ZSDDs. In addition, we present a new system of tractable indexing structure called zero-suppressed knowledge compilation map. It is a system of structures that has adopted zero-suppression to the whole structures of knowledge compilation map. Zero-suppressed knowledge compilation map has ZDD as basis instead of BDD. In Chapter 4 and Chapter 5, we prose our compilation method, merging frontier-based search. Merging frontier-based search is an extension of conventional frontier-based search. Unlike ordinal ZDD, we must “merge” the states of searching branches to compile structured Z-d-DNNF. We apply our compilation method to the independent set in Chapter 4 and s-t paths in Chapter 5. Finally, in Chapter 6, we conclude this thesis and discuss the future work.
(主査) 教授 吉岡 真治, 教授 有村 博紀, 教授 堀山 貴史
情報科学研究科(情報理工学専攻)
コレクション(個別)国立国会図書館デジタルコレクション > デジタル化資料 > 博士論文
受理日(W3CDTF)2020-11-10T19:58:22+09:00
連携機関・データベース国立国会図書館 : 国立国会図書館デジタルコレクション