層状ネットワークにおける段階的な最適化問題に関する研究

分层网络逐步优化问题研究

基本信息

批准号：
22K11915
负责人：
朝廣雄一
金额：
$ 2.66万
依托单位：
Kyushu Sangyo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2022
资助国家：
日本
起止时间：
2022-04-01 至 2027-03-31
项目状态：
未结题

项目摘要

本研究では，層状のネットワーク上における組合せ最適化問題に取り組むことを目的としている．例えば，文字列で表されるデータ（例えばユーザの行動に関する時系列データや発見したDNAの列など）が２台のデバイスからサーバに送られて，サーバ側では，それらの共通部分を求めたいことがある．このように複数の文字列データから共通部分を求める場合には，何をもって共通な部分であると捉えるかによって，様々な問題設定がある．例えば，共通な部分文字列のうち最長なものだったり，さらに最長な共通部分文字列に出現する文字数を制限したい場合もあったりなどする．今年度は，それらのうち，2つの文字列から出現文字数が制限された最長な共通部分文字列を探す問題，2つの文字列のうち片方の文字列にいくつかの文字を追加することで他方の文字列との共通部分列をできるだけ長くする問題，2つの文字列から共通な部分文字列を探したいが，そのときその共通部分列に含まれる文字を事前に指定された文字集合とできるだけ重複させたい問題，などの問題について考察した．得られた結果としては，これらの問題は厳密には異なる問題であるが，多項式時間をかけて問題間の変形操作を行うことで，ある一つの指数時間アルゴリズムですべての問題を解決できることを示した．またその指数時間アルゴリズムとして，既知のものよりも，高速なアルゴリズムを開発した．以上のような研究成果を，査読付き国際会議 Annual Symposium on Combinatorial Pattern Matching ならびに国内研究集会電気・情報関係学会九州支部連合大会において公表した．

这项研究旨在解决分层网络上的组合优化问题。例如，以字符串表示的数据（例如，有关用户行为或发现的DNA序列的时间序列数据）是从两个设备发送到服务器的，在服务器端，可能有必要在它们之间找到共同的部分。当以这种方式从多个字符串数据计算出一个常见的部分时，可以根据被认为是常见的部分设置各种问题。例如，它可能是最长的常见子字符串，或者您可能需要限制出现在最长常见子字符串中的字符数。今年，我们讨论了诸如在两个字符串中出现的最长数量的字符，在两个字符串中添加几个字符的问题，以使共同的子字符串与另一个字符串尽可能长时间，以及从两个字符串中找到一个常见的基因的问题，而从两个字符串中找到一个常见的基础，但试图将其用来订阅中包含的字符，以使其与另一个字符串相同，以使其与另一条字符串相同。获得的结果表明，尽管这些问题是严格不同的问题，但所有问题都可以通过在多项式时间内进行问题之间进行转换操作来解决。此外，我们开发了一种指数时间算法，该算法比已知的算法快。上述研究结果发表在经过同行评审的国际国际会议组合模式匹配年度研讨会和电气与信息关系协会九州分会的日本研究会议上。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

重複なし最長共通部分列に関する全列挙法を用いた評価

使用完整枚举方法评估无重复的最长公共子序列

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
加藤悠宇汰;大場春佳;水野信也;戴銘紳，朝廣雄一，宮野英次
通讯作者：
戴銘紳，朝廣雄一，宮野英次

Polynomial-time equivalences and refined algorithms for longest common subsequence variants

DOI：
10.1016/j.dam.2024.04.006
发表时间：
2024-08-15
期刊：
DISCRETE APPLIED MATHEMATICS
影响因子：
1.1
作者：
Asahiro，Yuichi;Jansson，Jesper;Utashima，Tadatoshi
通讯作者：
Utashima，Tadatoshi

University of Alberta(カナダ)

阿尔伯塔大学（加拿大）

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

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

朝廣雄一其他文献

最大・最小支配ツアー問題の計算複雑さ

最大-最小支配旅游问题的计算复杂度

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次
通讯作者：
野々上夏葵，江藤宏，宮野英次

重複無し最長共通部分列問題の計算時間

无重复的最长公共子序列问题的计算时间

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆
通讯作者：
歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆

最小ブロック転送問題について

关于最小块传输问题

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次;柳植竜，朝廣雄一，Guohui Lin，宮野英次;寺原一平，江藤宏，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，斎藤寿樹，鈴木顕，八木田剛;八木田剛，朝廣雄一，宮野英次
通讯作者：
八木田剛，朝廣雄一，宮野英次

C5フリー正則グラフ上での誘導マッチング問題に対する近似アルゴリズム

C5自由正则图引导匹配问题的逼近算法

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次;柳植竜，朝廣雄一，Guohui Lin，宮野英次
通讯作者：
柳植竜，朝廣雄一，Guohui Lin，宮野英次

初期解からの変更数を制限した最適化問題

对初始解决方案进行有限数量更改的优化问题

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次
通讯作者：
税所航平，宮野英次