情報圧縮に基づく遷移問題の汎用的アルゴリズムの開発

基于信息压缩的转移问题通用算法的开发

基本信息

批准号：
16J02175
负责人：
畑中達彦
金额：
$ 1.22万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2016
资助国家：
日本
起止时间：
2016-04-22 至 2019-03-31
项目状态：
已结题

项目摘要

理論計算機科学分野の中でも近年特に注目を浴びている題材の1つに「遷移問題」がある．遷移問題とは，ある条件を満たす解から局所的な変更操作を繰り返して別の解へ「遷移」することを目的としている．ただし，遷移の過程でも常に条件を満たす解となっていなければならない．本研究では，遷移問題に対する汎用的なアルゴリズム手法の開発を目的としている．本年度はまず，前年度「点彩色遷移問題」及び「リスト点彩色遷移問題」を対象に行った研究成果をまとめた2本の論文が，査読付き学術雑誌「Theoretical Computer Science」と「IEICE Transactions on Information and Systems」にそれぞれ掲載された．その後，上記の論文執筆の際に得られた数々の知見に基づき，これまでの各アルゴリズム手法の一般化を行った．具体的には，「制約充足遷移問題」と呼ばれる問題に対して，入力グラフの構造や頂点に割当て可能な値の種類数などに着目したいくつものアルゴリズムを与えた．制約充足遷移問題はリスト点彩色，グラフ準同型，論理式充足可能性，最短路といった理論計算機科学の根幹を為す様々な問題に対する遷移問題を包含している．そのため，本研究のアルゴリズムは数多くの遷移問題に適用できるものとなっている．さらに，それらの結果と対比を為すいくつかの計算困難性を証明し，制約充足遷移問題の計算の複雑さを網羅的に解析した．上記の内容は，情報処理学会アルゴリズム研究会にて発表済であり，証明の厳密化と結果の補完を行った論文を次年度にも国際会議に投稿予定である．また，「支配集合遷移問題」や「非決定性制約論理」といった個別の遷移問題に対しても研究を行い，現在論文の執筆が進行中である．

近年来在理论计算机科学领域受到特别关注的主题之一是“过渡问题”。过渡问题的目的是通过重复局部改变操作，从满足一定条件的解“过渡”到另一个解。然而，解决方案必须始终满足过渡过程中的条件。本研究的目的是开发一种用于转换问题的通用算法方法。今年，两篇总结前一年关于“点颜色过渡问题”和“列表点颜色过渡问题”研究成果的论文分别发表在同行评审学术期刊《理论计算机科学》和《IEICE Transactions on Information and系统”分别。之后，我们根据撰写上述论文时获得的大量发现，概括了之前的每种算法方法。具体来说，对于一个称为“约束满足转移问题”的问题，我们开发了许多算法，重点关注输入图的结构以及可以分配给顶点的值类型的数量。约束满足转移问题包括构成理论计算机科学基础的各种问题的转移问题，例如列表点着色、图同态、逻辑公式的可满足性和最短路径。因此，本研究的算法可以应用于许多转移问题。此外，我们还论证了与这些结果相比的一些计算困难，并全面分析了约束满足转移问题的计算复杂性。上述内容已经在日本信息处理学会算法研究组上进行了展示，我们计划在明年的国际会议上提交一篇有更严格证明和补充结果的论文。我们还在对“支配集转移问题”和“非确定性约束逻辑”等个体转移问题进行研究，目前正在撰写论文。