動的に変化する空間内における高品質な経路の探索手法に関する研究

动态变化空间中高质量路径搜索方法研究

基本信息

批准号：
15700021
负责人：
朝廣雄一
金额：
$ 1.6万
依托单位：
Kyushu Sangyo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

项目摘要

本年度は、複数の物体が移動する空間において、それらの物体を効率よく巡回するロボットの経路を求める問題に対して、計算複雑さの解析とアルゴリズムの開発を行った。まずロボットの容量が1(1つの物体に接触したらスタート地点に戻る必要がある)の時に、巡回対象の物体の移動経路について場合1:直線の場合場合2:折れ線の場合を考察した。場合1については、物体の移動速度がロボットよりも速い場合には、多項式時間O(n log n)で解けることを示した。ここでnは移動物体の個数である。また、物体の移動に時間制約がついている、すなわち物体はある時刻に出現し、ある時刻まで移動するというような条件を課しても同様に多項式時間O(n log n)で解けることを示した。一方で、物体の移動速度がロボットよりも遅い場合には、NP困難となることを示した。場合2については、各物体の経路である折れ線の頂点数(すなわち物体が移動中に曲がる回数)が1個以上あると、MAXSNP困難となることを示した。また近似比2の近似アルゴリズムを開発した。他には、ロボットの容量には制約がないが、直線上しか移動出来ないという条件下での問題についても考察した。例えば、与えられた軌道上を動く場合には、巡回できる物体数を最大にするアルゴリズムが、O(n log n)時間で動作することを示した。またこのロボットの軌道については、無限に可能性があるが、巡回できる物体数を最大にできる軌道の選択も多項式時間O(n^3 log n)で可能であることを示した。さらに、複数のロボットを同時に利用する場合に必要となる、仕事割り当て手法に関連するいくつかの結果も得た。

今年，我们分析了计算复杂性，并开发了算法，以解决在多个对象移动的空间中有效巡逻机器人的路径的问题。首先，当机器人的容量为1时（如果与一个对象接触，则需要返回起点）时，我们讨论了对象的运动路径为巡逻1：直线2的情况2：断线的情况。对于情况1，我们表明，如果对象的移动速度比机器人的移动速度快，则可以用多项式时间O（n log n）求解。在这里，n是移动对象的数量。还显示出对象的运动是时间的限制，即即使强加条件使对象出现在一定时间并移至一定时间，也可以在多项式时间o（n log n）上求解。另一方面，当对象的移动速度比机器人的移动速度慢时，NP变得困难。在情况2中，可以表明，如果线的一个或多个是每个对象的路径的顶点（即，移动时对象弯曲的次数），则很难MAXSNP。我们还为近似值2开发了一种近似算法。关于机器人容量没有限制的问题，还提出了其他考虑因素，但是只有机器人才能直线移动。例如，我们已经表明，在移动给定轨道上时，可以在O（n log n）次时最大化可以在O（n log n）次的对象数量的算法。此外，尽管该机器人的轨迹有无限的可能性，但还表明，在多项式时间o（n^3 log n）中，允许最大数量可以巡逻的对象数量的轨迹选择。此外，同时获得多个机器人时，需要进行一些与工作分配技术有关的结果。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

How to Collect Balls Moving in the Euclidean Plane

如何收集在欧几里得平面上移动的球

DOI：
发表时间：
期刊：
Discrete Applied Mathematics (to appear)
影响因子：
0
作者：
Y.Asahiro;T.Horiyama;K.Makino;H.Ono;T.Sakuma;M.Yamashita
通讯作者：
M.Yamashita

Graph Orientation Algorithms to minimize the Maximum Outdegree

DOI：
10.1142/s0129054107004644
发表时间：
2006-12
期刊：
影响因子：
0
作者：
Y. Asahiro;Eiji Miyano;H. Ono;K. Zenmyo
通讯作者：
Y. Asahiro;Eiji Miyano;H. Ono;K. Zenmyo

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

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

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

Pickup and Delivery for Moving Objects on Broken Lines

折线上移动物体的拾取和交付

DOI：
发表时间：
2005
期刊：
Proc.9th Italian Conference on Theoretical Computer Science, Lecture Notes in Computer Science 3701
影响因子：
0
作者：
Y.Asahiro;E.Miyano;S.Shimoirisa
通讯作者：
S.Shimoirisa

Y.Asahiro, M.Ishibashi, M.Yamashita: "Independent and Cooperative Parallel Search Methods for the Generalized Assignment Problem"Optimization Methods and Software. 18・2. 129-141 (2003)

Y.Asahiro、M.Ishibashi、M.Yamashita：“广义分配问题的独立和协作并行搜索方法”18・2（2003）。

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：
发表时间：
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.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次
通讯作者：
野々上夏葵，江藤宏，宮野英次

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

关于最小块传输问题

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，宮野英次

接続制限付きハブ空港配置問題に対するNP困難性

连接有限的枢纽机场布局问题的 NP 难度

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