Study on developing enumeration algorithms based on a supergraph technique

基于超图技术的枚举算法开发研究

基本信息

批准号：
22K17849
负责人：
和佐州洋
金额：
$ 3万
依托单位：
Hosei University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2025-03-31
项目状态：
未结题

项目摘要

理論計算機科学における重要な問いとして，「実行可能解はいくつ存在するか」が挙げられる．この文脈において，解の個数を計数する問題と全ての解を実際に出力する問題の2つの観点で研究が進められているが，本研究では，後者を列挙問題と呼び，これに関して研究を行う．列挙問題は理論・応用両面において頻出する問題である．例えば，ユーザーが自身の嗜好を正確に定義できない場合，例えば夕食でどのレストランに行くか決める時などでは，ある程度候補となる対象を列挙し，その後実際にユーザーが目で見て自身の嗜好に適った対象を選ぶ，というような状況で列挙は重要な役割を果たす．このような状況では，効率良いアルゴリズムが提供されることは非常に重要である．これまで列挙アルゴリズムを構成するための様々なフレームワークやメタアルゴリズムが開発されてきたが，その適用範囲は限定されており，より汎用的な構築技法の確立が課題となっている．さらにそのようなフレームワークの適用限界についても全く明らかでない．本研究では，(1) スパース化を用いた解グラフ技法と呼ばれるフレームワークの拡張，および，(2) 局所的な構造に着目したメタアルゴリズムの開発を目的として研究を行う．令和4年度は，この内 (1) に注力した．その結果，k-辺連結全域グラフに関してアルゴリズムの開発が見込めそうだという結論に達した．これは2辺連結誘導グラフとは少し異なるが，このアイディアを応用して，2辺連結誘導グラフの列挙につなげて行く計画である．

理论计算机科学中的一个重要问题是“存在多少可行解决方案？”在这种情况下，研究以两种方式进行：一个问题，它计算解决方案数量和实际输出所有解决方案的问题。在这项研究中，后者被称为枚举问题，对此进行了研究。枚举问题是理论和应用方面经常出现的问题。例如，如果用户无法准确定义自己的偏好，例如，在决定要去晚餐的餐厅时，请在某种程度上列举候选人，然后用户实际上选择了通过查看他们的偏好的目标。在这种情况下，提供有效的算法非常重要。到目前为止，已经开发了用于构建枚举算法的各种框架和元算象，但是其应用的范围有限，并且建立更一般的建筑技术已成为一个挑战。此外，此类框架的应用限制根本不清楚。在这项研究中，我们将进行研究，目的是（1）使用稀疏化扩展称为解决方案图技术的框架，以及（2）开发着针对局部结构的元算法。在2022财政年度，我们重点关注（1）。结果，我们得出的结论是，对于K-侧全范围图有可能开发算法。这与双面连接的指南图有点不同，但是我们计划应用此想法将其链接到双面连接的指南图的枚举。

项目成果

期刊论文数量（5）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Linear-Delay Enumeration for Minimal Steiner Problems

最小 Steiner 问题的线性延迟枚举

DOI：
10.1145/3517804.3524148
发表时间：
2022
期刊：
PODS '22: Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
影响因子：
0
作者：
Kobayashi Yasuaki;Kurita Kazuhiro;Wasa Kunihiro
通讯作者：
Wasa Kunihiro

Constant amortized time enumeration of Eulerian trails

欧拉轨迹的常数摊销时间枚举