警備員巡回路問題と動物園巡回路問題に対する近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
警備員巡回路問題とは, 与えられた多角形Pに対し, Pの任意の点が巡回路上の少なくとも1点から見えるような最短の巡回路を見つけることである.最短警備員巡回路を求めるO(n^4)時間のアルゴリズムが既に報告されたが, そのアルゴリズムは複雑で実用に堪えるものではない.一般的に, O(n log n)時間で警備員巡回路問題を多角形P内にある線分の集合を訪れる最短路を求める問題に帰着することができる.本論文では, その線分の集合を訪れる(警備員)巡回路を求める線形時間のアルゴリズムを提案する.求められた巡回路の長さが最短警備員巡回路の長さの√<2>倍に越えないことが保証される.提案されたアルゴリズムは簡単で実現しやすい.更に, この近似手法は, 警備員巡回路問題の変形版である, 動物園巡回路問題にも適用できる.これまでに, 動物園巡回路問題に対する近似度6のアルゴリズムが提案されていた.我々の結果は今までの結果を大幅に改善した.
- 2001-07-27
著者
関連論文
- Web上での広域コラボレーションにもとづく多次元画像診断支援システムの開発 : カメラコントロールによる広域コラボレーションの実現法(可視化・モデリング技術)(関連学会との共催によるバイオメディカルイメージング連合フォーラム)
- Web上での広域コラボレーションにもとづく多次元画像診断支援システムの開発 : 管腔臓器の領域抽出からドローネ三角形分割によるモデリングまで(可視化・モデリング技術)(関連学会との共催によるバイオメディカルイメージング連合フォーラム)
- Web3Dによる画像診断支援システムの開発-その2
- Web3Dによる画像診断支援システムの開発-その1
- Web3Dによる画像診断支援システムの開発(その1) (第31回可視化情報シンポジウム講演論文集) -- (一般講演 可視化の応用 2)
- 警備員巡回路問題と動物園巡回路問題に対する近似アルゴリズム
- 警備員経路アルゴリズムの時間解析について
- チェーンガイドによる多角形の捜索アルゴリズム(セッション1)
- Κ-探索者による単純多角形の探索問題について
- ストレートウォーカーブル多角形におけるエッジガードについて
- 動物園経路問題に関する新しいアルゴリズム