2024-03-29T22:36:22Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001963042023-11-17T02:17:36Z06504:09795:09803
グラフ上の協調経路策定問題の計算複雑性jpnソフトウェア科学・工学http://id.nii.ac.jp/1001/00196214/Conference Paperhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=196304&item_no=1&attribute_id=1&file_no=1Copyright (c) 2019 by the Information Processing Society of Japan東北大東北大東北大東北大村岡, 功大澤, 弘基伊藤, 健洋周, 暁本稿では,グラフ上で同時に移動する複数ロボットの経路策定を扱う.協調経路策定問題とは,ある移動ルールに基づいて,複数台のロボットを初期配置から目標配置まで移動させるために必要な最小のステップ数を計算する問題である.この問題は,一般にNP困難であることが知られている.本稿では,最大次数3以上のグラフでは本問題がNP困難であることを示す一方で,最大次数2以下のグラフでは多項式時間で解けることを示す.AN00349328第81回全国大会講演論文集201911911922019-02-282019-05-28