7B-02
グラフ上の協調経路策定問題の計算複雑性
○村岡　功，大澤弘基，伊藤健洋，周　　暁（東北大）
本稿では，グラフ上で同時に移動する複数ロボットの経路策定を扱う．協調経路策定問題とは，ある移動ルールに基づいて，複数台のロボットを初期配置から目標配置まで移動させるために必要な最小のステップ数を計算する問題である．この問題は，一般にNP困難であることが知られている．本稿では，最大次数3以上のグラフでは本問題がNP困難であることを示す一方で，最大次数2以下のグラフでは多項式時間で解けることを示す．
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会