圧縮索引構造を用いた汎用的かつ実用的な多様な解の発見アルゴリズム

一种使用压缩索引结构寻找多种解决方案的通用且实用的算法

• 批准号: 22K17851
• 负责人: 中畑 裕
• 金额: $ 2.91万
• 依托单位: Nara Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2026-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-22K17851/
• 关键词: 多様性最大化; 列挙; 組合せ最適化; 決定グラフ; ZDD

本研究では実世界の最適化問題に対し，多様な解を列挙する実用的なアルゴリズムを開発する.最適化問題では通常，アルゴリズムは単一の最適解を出力する.しかし実用上は，モデルに書ききれない曖昧な制約があり，最適解1つでは不十分なことがある.そこで多様な解を列挙できれば有用だが，多くの問題はNP困難であることが知られている.そこで本研究では，大規模な組合せ集合を圧縮して表現できる索引構造を用いて汎用的かつ実用的なアルゴリズムの開発を目指す.本研究の成果は理論と実用のギャップを埋めるという学術的意義に加え，Web検索，推薦 システム，データベースといった幅広い分野での応用が期待される.本年度は，多様性最大化に対するゼロサプレス型二分決定グラフ（ZDD）を用いた近似手法の検討を行った．解の集合がZDDで表されている場合，線形重み最大の解を見つけることはZDDのサイズに対する線形時間でできる.この性質を用いて，解の集合を表すZDDが与えられたとき，ZDDのサイズに対する多項式時間で動作する多様性最大化に対する制度保証付き近似アルゴリズムを設計した.ZDDのサイズは最悪の場合は入力サイズに対して指数的に大きくなるが，実用的な多くの場合では十分圧縮が効くので，このアプローチは多様性最大化に対する統一的かつ効率的な近似手法になりうると考えている.研究成果について，国内会議および国際会議での発表を検討している．

This study aims to explore the practical application of multi-solution optimization problems in the world. Optimization problem is usually a problem of optimization solution. The optimal solution is 1. The problem of multiple solutions is NP difficult. In this paper, we propose a new approach to the development of large-scale combinatorial set compression and performance index structures. The results of this study are theoretical and practical, and academic significance is added. Web search, recommendation, and application are expected. This year, we will discuss the diversity maximization method by using the approximate method. When the set of solutions is ZDD, the maximum solution of linear weight is ZDD. The properties of ZDD are used to represent the set of solutions. ZDD is designed to maximize the multiplicity of polynomial time operations. ZDD is designed to maximize the multiplicity of polynomial time operations.ZDD is designed to maximize the multiplicity of polynomial time operations. This paper discusses the approximation method of uniform efficiency in maximizing diversity. Research results are discussed in the development of domestic and international conferences.

项目成果

ZDD-based algorithmic framework for solving shortest reconfiguration problems

基于ZDD的解决最短重构问题的算法框架

• DOI: 10.1007/978-3-031-33271-5_12
• 发表时间: 2023
• 期刊: Proceedings of the 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2023), Lecture Notes in Computer Science (LNCS)
• 作者: Takehiro Ito;Jun Kawahara;Yu Nakahata;Takehide Soh;Akira Suzuki;Junichi Teruyama and Takahisa Toda
• 通讯作者: Junichi Teruyama and Takahisa Toda

時間変化するネットワークに対する二分決定グラフを用いた信頼性評価法

时变网络二元决策图可靠性评估方法

• 发表时间: 2022
• 作者: 有薗舜;中畑裕;笠原正治
• 通讯作者: 笠原正治

Reconfiguring (non-spanning) arborescences

重新配置（非跨越）树状结构

• DOI: 10.1016/j.tcs.2022.12.007
• 发表时间: 2023
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Takehiro Ito;Yuni Iwamasa;Yasuaki Kobayashi;Yu Nakahata;Yota Otachi;Kunihiro Wasa
• 通讯作者: Kunihiro Wasa

Independent set reconfiguration on directed graphs

有向图上的独立集重构

• 发表时间: 2022
• 期刊: Proc. of 47th International Symposium on Mathematical Foundations of Computer Science, Leibniz International Proceedings in Informatics
• 作者: Takehiro Ito;Yuni Iwamasa;Yasuaki Kobayashi;Yu Nakahata;Yota Otachi;Masahiro Takahashi;Kunihiro Wasa
• 通讯作者: Kunihiro Wasa