Research on Integrated Techniques of Enumeration and Optimization Based on Discrete Structure Manipulation Systems

基于离散结构操纵系统的枚举与优化集成技术研究

基本信息

批准号：
20H00605
负责人：
湊真一
金额：
$ 28.12万
依托单位：
Kyoto University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (A)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2025-03-31
项目状态：
未结题

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20H00605/
关键词：
アルゴリズム離散構造演算処理系列挙索引化

项目摘要

本年度の研究実績の概要は以下の通りである。(i) 列挙と最適化の統合的アルゴリズム技法の研究と体系化：グラフの最短路問題のように、組合せ問題のアイテムにコストが定義されているときに、コスト総和が所与の閾値以下となるような実行可能解を列挙することは、多くの実用的な応用を持つ汎用的で重要な問題である。このような一般的なコスト制約つき組合せ問題に対して、ZDDを用いて大量の解を高速に全列挙する「区間メモ化技法」を前年度に考案したが、これを実装し実験により有効性を確認した。本研究結果は研究代表者自らが筆頭著者として国内研究会および国際ワークショップで発表した。(ii) 離散構造処理系の基盤アルゴリズムの実装とソフトウェアの整備：BDD/ZDDをベースとする離散構造処理系のアルゴリズムは、原則として「BDDパッケージ」と呼ばれるソフトウェアライブラリとして公開されている。前年度からに開発している高速列挙アルゴリズムの実装もこのパッケージに追加されており、改良を進めている。(iii) 関連分野との連携および応用分野への発展：本研究が呼び水となり、学術変革(A)「アルゴリズム基盤」および学術変革(B)「組合せ遷移」が昨年度後半に相次いで採択され、理論計算機科学を中心とする研究者コミュニティの発展が期待される。学術変革(A)(B)および各分野の第一線で活躍する研究者と研究協力者として定期的に会合し連携を深めた。

今年研究结果的概述如下。（i）用于枚举和优化的综合算法技术的研究和系统化：与图形最短的路径问题一样，列举可行的解决方案，在这些解决方案中，成本的总和低于给定的阈值，而当组合问题中的项目定义成本是许多实际应用的一般和重要问题。在上一年，我们设计了一种“间隔纪念技术”，该技术使用ZDD快速列出了大量的解决方案，以解决此类一般的成本限制组合问题，并实施了这项技术，并通过实验确认了其有效性。这项研究的结果是在国内研究小组和国际研讨会上作为主要作者提出的。（ii）实施用于离散结构处理系统和软件维护的基础算法：基于BDD/ZDD的离散结构处理系统的算法通常以称为“ BDD软件包”的软件库发表。自上一年还添加了此软件包以来，已经开发了高速枚举算法的实施，并正在进行改进。（iii）与相关领域和发展中的相关领域的合作：这项研究将成为发展学术转型的催化剂（a）“算法基金会”和学术转型（b）“在去年下半年进行过渡”，并且预计研究人员社区的发展主要是基于理论计算机科学的。我们定期与活跃于学术转型（a）（b）的研究人员和每个领域的最前沿的研究人员会面，以加深我们的合作。

项目成果

期刊论文数量（61）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Algorithmic Enumeration of Surrounding Polygons

周围多边形的算法枚举

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
K. Yamanaka;T. Horiyama;Y. Okamoto;R. Uehara;T. Yamauchi
通讯作者：
T. Yamauchi

解集合プログラミングを用いたハミルトン閉路遷移問題の解法

使用解集规划求解哈密顿循环转移问题

DOI：
发表时间：
2023
期刊：
影响因子：
0
作者：
平手貴大;番原睦則;井上克巳;盧暁南;鍋島英知;宋剛秀;田村直之
通讯作者：
田村直之

解集合プログラミングに基づく組合せ遷移ソルバーの実装方式に関する考察

基于解集规划的组合转移求解器实现方法的思考

DOI：
发表时间：
2021
期刊：
影响因子：
0
作者：
山田悠也;湊真一;番原睦則
通讯作者：
番原睦則

チャネリング制約を用いたalldifferent 制約の SAT 符号化

使用通道约束对所有不同约束进行 SAT 编码

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
小菅脩司;宋剛秀;田村直之;番原睦則
通讯作者：
番原睦則

DAG-Pathwidth: Graph Algorithmic Analyses of DAG-Type Blockchain Networks

DAG-Pathwidth：DAG 型区块链网络的图算法分析

DOI：
10.1587/transinf.2022fcp0007
发表时间：
2023
期刊：
IEICE Transactions on Information and Systems
影响因子：
0.7
作者：
Shoji Kasahara;Jun Kawahara;Shin-ichi Minato;Jumpei Mori
通讯作者：
Jumpei Mori

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 }}

湊真一其他文献

Efficient Database Analysis Using VSOP Calculator Based on Zero-suppressed BDDs

使用基于零抑制 BDD 的 VSOP 计算器进行高效数据库分析

DOI：
发表时间：
2006
期刊：
Frontiers in Artificial Intelligence, Joint JSAI 2005 Workshop Post-Proceedings LNAI 4012
影响因子：
0
作者：
湊真一;有村博紀;Bjorn Hoffmeister and Thomas Zeugmann;S. Minato;S. Minato
通讯作者：
S. Minato

Development of Distributed Virtual Disk System Using Online Storage for Ubiquitous Computing Environment

普适计算环境下利用在线存储的分布式虚拟磁盘系统的开发

DOI：
发表时间：
2007
期刊：
Proc. of SACSIS2007, IPSJ/IEICE/JSSST
影响因子：
0
作者：
Bjorn Hoffmeister;Thomas Zeugmann;S.Minato;湊真一;Shin-ichi Minato;湊真一;野尻祐亮;野尻祐亮;野尻祐亮;藤井敦;Yusuke Nojiri
通讯作者：
Yusuke Nojiri