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包”的软件库。自去年以来开发的高速枚举算法的实现也已添加到此软件包中，并且正在进行改进。（三）与相关领域合作，向应用领域发展：以本研究为推动，下半年相继采取学术转型（A）“算法基础”和学术转型（B）“组合转型”去年，理论界预计将发展出一个以计算机科学为中心的研究人员社区。我们作为研究合作者定期会面，并加深了与活跃在各个领域学术转型 (A) 和 (B) 最前沿的研究人员的合作。