| 03 |
ネットワーク構造に関する様々な質問に答えますゼロサプレス型項分岐決定グラフを用いたグラフ構造索引 
|
|---|
| どんな研究 |
ネットワーク構造に関する情報を小さく表現する部分構造索引を用いて、効率的に特定の構造を発見したり、数を数えたりする方法を研究しています。 部分構造索引を用いると、通信網や道路網などの、ネットワーク構造をもつ多様な問題を効率的に解くことができます。 |
|---|---|
| どこが凄い |
新しい部分構造索引であるゼロサプレス型項分岐決定グラフ（ZSDD）、およびZSDDを効率的に構築するアルゴリズムを考案しました。考案した技術を用いるとこれまでよりも小さな索引を構築できます。索引を小さくしたぶんだけ多様な問題をより高速に解決できます。 |
| めざす未来 |
アルゴリズムの改良は、計算機の性能向上だけでは容易に達成できない、計算の劇的な高速化をもたらします。考案したアルゴリズムを利用しやすい形で整備することにより、応用問題でより良い解を発見できるようになるなど、効率的な社会の実現に貢献します。 |
[1] M. Nishino, N. Yasuda, S. Minato, M. Nagata, “Zero-suppressed Sentential Decision Diagrams,” in Proc. 30th AAAI Conference on Artificial Intelligence (AAAI 16), 2016.
[2] M. Nishino, N. Yasuda, S. Minato, M. Nagata, “Compiling Graph Substructures into Sentential Decision Diagrams,” in Proc. 31st AAAI Conference on Artificial Intelligence (AAAI 17), 2017.
[3] Y. Nakahata, M. Nishino, J. Kawahara, S. Minato, “Enumerating All Subgraphs Under Given Constraints using Zero-suppressed Sentential Decision Diagrams,” in Proc. 18th Symposium on Experimental Algorithms (SEA 2020), 2020.
西野 正彬 （Masaaki Nishino） 協創情報研究部 言語知能研究グループ
Email: cs-openhouse-ml@hco.ntt.co.jp