期限付き移動物体に対する回収アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
本稿では, 実用的な応用問題を形式化した以下のようなスケジューリング問題を考える. 問題の入力として, 一度に回収可能な数をk以下としたロボット・アームと, n個の移動物体が与えられる. 移動物体にはそれぞれの初期位置, 移動の速さ, 移動軌跡, 回収期間が決められている. 容量制約を持つロボット・アームによりそれぞれの回収期間内にできるだけ多くの移動物体を掴み, 決められた場所まで回収するような移動経路(の集合)を求めることを目的とする. 本稿では, k=1の場合に, すべての物体がロボット・アームより大きな速さで等速直線移動する場合には, O(nα(n)log n)の最大回収アルゴリズムが存在することを示す. ここで, α(n)は逆アッカーマン関数とする. しかし, もしある物体がロボット・アームよりも遅い場合にはNP困難となることを示す.
- 2005-03-11
著者
-
宮野 英次
九州工業大学大学院情報工学研究院
-
朝廣 雄一
九州産業大学情報科学部
-
朝廣 雄一
九州産業大学情報科学部情報科学科
-
下入佐 真一
九州工業大学大学院情報工学研究科
-
宮野 英次
九州工業大学
関連論文
- 直径d部分グラフ最大化問題の計算複雑さ
- 移動ロボットによる長尺物運搬問題に対する分散アルゴリズム (計算モデルとアルゴリズム)
- 最大出次数最小化問題の各種グラフクラスに対する計算複雑さ
- 直径d部分グラフ最大化問題の近似について
- 完全二分木の直線埋め込みについて
- 最大支配問題
- グラフの最小出次数最大化問題
- 最小マンハッタンネットワーク問題の近似について (理論計算機科学の深化と応用)
- 最小ブロック転送問題の近似可能性と近似不可能性
- バンプ探索における解の精度(セッション1)
- バンプ探索における解の精度(セッション1)
- 守備特訓に喘ぐ外野手のための捕球経路問題 (計算機科学基礎理論の新展開)
- サイクルグラフ上での地図作成問題に対する重み付き最近傍アルゴリズム
- 試問予定表作成問題の計算複雑さ
- 移動物体回収問題 : ロボットに効率良く物体を回収させるアルゴリズムの設計のために(学生/教養のページ)
- 移動物体回収問題
- ブックマーク問題の近似について
- 正則グラフに対する密な部分グラフ問題
- 一様メトリックにおけるソーティングバッファ問題のNP困難性
- 顧客データベースにおけるbump huntingとその精度
- バンプ探索における解の精度
- 最大重み付き出次数を最小化するグラフ有向化問題の近似(不)可能性
- Bump hunting 問題における極値統計の応用(日本計算機統計学会 第19回シンポジウム)
- 最大出次数を最小化するグラフ有向化について
- 期限付き移動物体に対する回収アルゴリズム
- 資源増加を許したOVSF符号割当問題に対する2競合アルゴリズム
- 頂点数を最大とする正則誘導連結部分グラフ問題の計算複雑さ (コンピュテーンョン)
- 資源増加を許したOVSF符号割当問題に対する(1 + ε)-競合アルゴリズム
- 最大支配問題
- タイル縁に上書きルールを用いた敷き詰め問題
- タイル縁に上書きルールを用いた敷き詰め問題
- 効率の良い罫線描画について
- トーラス上の局所多数決と大域多数決
- 折線上を移動する物体に対する回収問題の困難性
- 期限付き移動物体に対する回収アルゴリズム
- 移動系における最大個数巡回アルゴリズム (計算機科学基礎理論の新展開)
- 容量を制限した場合の移動物体巡回問題 (計算機科学基礎理論の新展開)
- 頂点数を最大とする正則誘導連結部分グラフ問題の計算複雑さ
- メタ戦略アルゴリズムに対するロバストな並列化 (計算機科学基礎理論の新展開)
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
- ターミナル数5の成分素シュタイナー木最大化問題に対する近似アルゴリズム
- 距離d独立頂点集合問題の計算複雑さ
- 密な部分グラフ問題のNP完全性とそのSAT例題生成への応用
- AIMジェネレータによるバックトラック及び局所探索SATアルゴリズムの評価
- 次数指定した最大正則誘導部分グラフ探索問題(一般)