実世界ネットワーク最適化問題に対する高性能アルゴリズムの開発

开发针对现实世界网络优化问题的高性能算法

基本信息

批准号：
14780230
负责人：
宮野英次
金额：
$ 2.18万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2004
项目状态：
已结题

项目摘要

移動系に対する経路選択を考えた場合には,最適な経路を決定するための重要な情報である網構造が時間と共に変化し,動的環境の変化に対応可能なスケーラビティを重視した技術を確立することが必要である.このような要求に応えるため,各ノードが動くことによりノード間の距離,網の形状が時々刻々と変化し,さらには,ノードに巡回時間の制約を考えたネットワーク網上での移動ノード巡回最適化問題として定式化し,アルゴリズムの開発を行った.1.平面上にn個のノードが与えられ,各ノードは一定の速さであらかじめ定められた曲線上を動き回る.また,巡回可能となる開始時刻と巡回不可能となる終了時刻が決められている.巡回者は,平面上の原点を出発して,正確に1個のノードを訪れて,原点に戻る.この動作を繰り返して,できるだけ多くのノードを巡回するような巡回ノード個数の最適化(最大化)問題として定式化する.この問題の計算複雑さの検討を行い,ノードが一般の曲線上を移動する場合にはNP困難であることを示した.また,移動体が同心円周上を移動するように限定してもNP困難であることを証明し,1.582近似アルゴリズムの存在も示した.2.同様の条件の下で,n個のすべてのノードが等速直線移動し,さらには,すべてのノードが巡回者の速さよりも速い場合には,O(nα(n)log n)時間の最適な巡回アルゴリズムが設計可能であることを示した.ここでα(n)はアッカーマンの逆関数である.しかし,巡回者よりも遅いノードがある場合には,例えノードが等速直線移動をするような非常に強い制限を考えたとしても,NP困難となってしまうことを証明した。

在考虑移动系统的路线选择时，网络结构是确定最佳路线，随时间变化的重要信息，并且有必要建立一种强调可扩展性的技术，该技术可以适应动态环境中的变化。为了满足这些要求，每个节点的移动，节点与网络形状之间的距离不时变化，并且在网络网络上，节点是在网络网络上作为移动节点环状优化问题的配方，考虑到环环上的约束，并开发了算法。1。 n个节点在平面上给出，每个节点以一定速度在预定曲线上移动。另外，可能循环的开始时间和无法循环的结束时间。 Pathner在平面上启动原点，完全访问一个节点，然后返回到原点。重复此操作，并将其作为优化（最大化）的循环节点数量的问题，该问题循环尽可能多。我们检查了该问题的计算复杂性，并表明当节点在一般曲线上移动时，NP很困难。我们还证明，即使移动体在同心圆上移动，也很困难，并且还表明存在1.582近似算法。2。在类似的条件下，所有n个节点都线性移动，即使所有节点的移动速度都比环状节点的速度快，o（nα（n）log我们都可以设计出一个最佳的环状算法，可以设计α（n）是ackermann的逆函数。但是，我们证明即使节点慢于骑自行车，即使节点非常强，也很难以恒定的速度线性移动，np也变得困难。

项目成果

期刊论文数量（8）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

下入佐真一: "移動系における最大個数巡回アルゴリズム"京都大学数理解析研究所講究録・計算機科学基礎理論の新展開. (印刷中). (2004)

Shinichi Shimoirisa：“移动系统中的最大循环算法”，京都大学数学科学研究所，计算机科学基础理论的新发展（2004 年出版）。

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

作業時間制約付き移動物体回収問題のNP困難性

工作时间约束的运动物体检索问题的 NP 难度

DOI：
发表时间：
2004
期刊：
作業時間制約付き移動物体回収問題のNP困難性 12-1A-01
影响因子：
0
作者：
下入佐真一;朝廣雄一;宮野英次
通讯作者：
宮野英次

長野正明: "容量制限がある場合のボール回収アルゴリズム"電気関係学会九州支部連合大会論文集. 09-1A-07 (2003)

Masaaki Nagano：“存在容量限制时的球恢复算法”日本电气工程师九州分会会议记录 09-1A-07 (2003)。

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

下入佐真一: "容量を制限した場合の移動物体巡回問題"京都大学数理解析研究所講究録・計算機科学基礎理論の新展開. 1325. 15-20 (2003)

Shinichi Shimoirisa：“容量有限时的移动物体循环问题”京都大学数学科学研究所Kokyuroku，计算机科学基础理论的新发展1325. 15-20 (2003)。

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

移動系における最大個数巡回アルゴリズム

移动系统中循环算法的最大数量

DOI：
发表时间：
2004
期刊：
数理解析研究所講究録 1325
影响因子：
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：
发表时间：
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，宮野英次