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

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

基本信息

批准号：
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のサイズは最悪の場合は入力サイズに対して指数的に大きくなるが，実用的な多くの場合では十分圧縮が効くので，このアプローチは多様性最大化に対する統一的かつ効率的な近似手法になりうると考えている.研究成果について，国内会議および国際会議での発表を検討している．

在这项研究中，我们开发了实用算法，这些算法列举了各种解决现实世界优化问题的解决方案。在优化问题中，算法通常输出一个最佳解决方案。但是，实际上，模型中无法写出一些模棱两可的约束，最佳解决方案可能不够。列举各种解决方案很有用，但是众所周知，许多问题很难NP。因此，在这项研究中，我们旨在使用可以通过压缩大量组合来表达的索引结构来开发通用和实用算法。除了填补理论与实践之间的差距的学术意义外，这项研究的结果还应在各种领域（例如Web搜索，推荐系统和数据库）中应用。今年，我们使用零抑制的二分法决策图（ZDD）研究了一种近似方法，以最大程度地提高多样性。如果将解决方案集表示为ZDD，则可以在ZDD的大小的线性时间内找到具有最大线性重量的溶液。使用此属性，我们设计了一种在制度上保证的近似算法，以最大化的多样性，该算法在ZDD的大小中以多项式时间运行，鉴于代表解决方案集的ZDD。尽管在最坏的情况下，对于输入大小的ZDD的大小呈指数较大，但在许多实际情况下，它已充分压缩，因此我们认为这种方法可以是多样性最大化的统一和有效的近似方法。我们正在考虑有关我们研究结果的国内和国际会议的演讲。

项目成果

期刊论文数量（7）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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)
影响因子：
0
作者：
Takehiro Ito;Jun Kawahara;Yu Nakahata;Takehide Soh;Akira Suzuki;Junichi Teruyama and Takahisa Toda
通讯作者：
Junichi Teruyama and Takahisa Toda

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

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

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
有薗舜;中畑裕;笠原正治
通讯作者：
笠原正治

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

有向图上的独立集重构

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

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

中畑裕其他文献

動的計画法に基づく Simple Polygonization 列挙アルゴリズムの実験的評価

基于动态规划的Simple Polygonization枚举算法实验评估

DOI：
发表时间：
2021
期刊：
影响因子：
0
作者：
中畑裕;堀山貴史;湊真一;山中克久
通讯作者：
山中克久

禁止細分で特徴づけられる部分グラフの列挙索引化

以禁止细分为特征的子图的枚举索引

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
中畑裕;川原純;堀山貴史;湊真一
通讯作者：
湊真一

グラフ集合を圧縮して活用するためのデータ構造とアルゴリズム

用于压缩和利用图集的数据结构和算法

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
中畑裕;川原純;堀山貴史;笠原正治;川原純
通讯作者：
川原純

ZDDを用いた組合せ遷移ソルバー

使用 ZDD 的组合转换求解器

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
伊藤健洋;川原純;中畑裕;宋剛秀;鈴木顕;照山順一;戸田貴久
通讯作者：
戸田貴久

非肥満男性の脂肪機能異常（低アディポネクチン血症と脂肪インスリン抵抗性の併存）は，脂肪肝や筋インスリン抵抗性と関連する

非肥胖男性的脂肪功能异常（低脂联素血症和脂肪胰岛素抵抗共存）与脂肪肝和肌肉胰岛素抵抗有关

DOI：
发表时间：
2020
期刊：
影响因子：
0
作者：
伊藤健洋;川原純;中畑裕;宋剛秀;鈴木顕;照山順一;戸田貴久;木屋舞，田村好史，竹野影海，染谷由希，筧佐織，佐藤元律，山崎望，門脇聡，鈴木瑠璃子，古川康彦，杉本大介，加賀英義，船山崇，佐藤博亮，河盛隆造，綿田裕孝
通讯作者：
木屋舞，田村好史，竹野影海，染谷由希，筧佐織，佐藤元律，山崎望，門脇聡，鈴木瑠璃子，古川康彦，杉本大介，加賀英義，船山崇，佐藤博亮，河盛隆造，綿田裕孝