权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

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

基本信息

批准号：
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」にそれぞれ掲載された．その後，上記の論文執筆の際に得られた数々の知見に基づき，これまでの各アルゴリズム手法の一般化を行った．具体的には，「制約充足遷移問題」と呼ばれる問題に対して，入力グラフの構造や頂点に割当て可能な値の種類数などに着目したいくつものアルゴリズムを与えた．制約充足遷移問題はリスト点彩色，グラフ準同型，論理式充足可能性，最短路といった理論計算機科学の根幹を為す様々な問題に対する遷移問題を包含している．そのため，本研究のアルゴリズムは数多くの遷移問題に適用できるものとなっている．さらに，それらの結果と対比を為すいくつかの計算困難性を証明し，制約充足遷移問題の計算の複雑さを網羅的に解析した．上記の内容は，情報処理学会アルゴリズム研究会にて発表済であり，証明の厳密化と結果の補完を行った論文を次年度にも国際会議に投稿予定である．また，「支配集合遷移問題」や「非決定性制約論理」といった個別の遷移問題に対しても研究を行い，現在論文の執筆が進行中である．

Theoretical computer science is divided into two fields, and in recent years, special attention has been paid to the topic of "migration problem". The condition of migration is different. The conditions for migration are often discussed. This study aims to develop a general approach to migration problems. This year's paper is published in the academic journal "Theoretical Computer Science" and "IEICE Transactions on Information and Systems". After that, the paper was written in the paper to obtain the basic knowledge of the number, and the generalization of the method of each category. Specifically, the problem of "constraint adequacy migration" is called "problem of constraint adequacy migration." constraints sufficient migration problems including dot color, quasi-isotype, logical formula sufficient possibility, shortest path, theoretical computer science root and root migration problems This paper studies how to solve the problem of migration of multi-species. In addition, the computational difficulty of the result and the ratio are proved, and the computational complexity of the constraint sufficient migration problem is analyzed. The content of the above note is that the Information Processing Society will publish a report on the results of its research and prove that it is confidential. The paper will be submitted to the next international conference. The paper is currently in progress.