3D-12 障害物のある場合の警備員経路問題に関する研究
スポンサーリンク
概要
- 論文の詳細を見る
警備員経路問題とは, 与えられた領域内の全ての地点を一人の警備員が警備するための最短経路を求める問題である. これまでに, 与えられる多角形領域が(障害物がない)単純多角形である場合が詳しく研究され, 時間計算量と空間計算量がO (n^2)のアルゴリズム[swrl]が提案されている. 一方, より現実的である障害物がある場合の最短経路問題は, NP_hardであることが知られており[owr], これまで有力な手法が知られていなかった. 本論文では, 部屋の内部に障害物がある場合に, 障害物と部屋の間にスリット(切り込み)を入れることによって警備員の経路の方向を限定し, 多項式時間で経路を導く近似解決を提案する.
- 一般社団法人情報処理学会の論文
- 1999-03-09
著者
-
池田 諭
東京農工大学工学部情報コミュニケーション工学科
-
中森 眞理雄
東京農工大学
-
中森 眞理雄
東京農工大 大学院共生科学技術研究院
-
中森 眞理雄
東京農工大学 工学府情報工学専攻
-
中森 真理雄
東京農工大学工学部数理情報工学科
-
池田 諭
東京農工大学工学部
-
上野 由美子
東京農工大学大学院工学研究科アルゴリズム工学研究室
-
池田 諭
東京農工大・工
関連論文
- (48) 情報系専門学科のカリキュラムのアイデンティティと評価方法(第4セッション 教育評価方法)
- 半導体露光装置におけるディストーション調整の最適化(機械力学,計測,自動制御)
- 選択グラフの性質とフローショップスケジューリング問題(アルゴリズム一般)
- 困難な問題の双線形計画問題を用いたモデル化手法
- 論理式充足可能性,整数計画,および双線形計画について
- 作業場所が小さいマージソートと計算量の評価
- 作業領域が小さいマージソート
- トランスポジショングラフにおける素な経路
- 排他的論理和を含む論理式に対する充足可能性問題
- 特集「情報教育〜理論・評価・発展〜」の編集にあたって