ある一定の容量の荷物を積むことのできる乗り物を考え、ある道の頂点間で、
荷物を輸送する問題を考える。荷物の集合をそれぞれの出発点の頂点から決め
られた終点の頂点へ、乗り物を使って輸送する場合の最短の道のりを見つける
という問題はモーションプラニングにおける基本的な問題である。全ての荷物
を出発点から終点へ、直接、輸送しなければならないという問題はＮＰ完全で
あることを示した。しかし、輸送の途中の頂点で荷物を落ろせるとして、それ
を後で輸送してもよいとすれば、その問題は線形時間で解ける。しかし、この
問題の設定が道ではなく木であった場合には、輸送の途中の頂点で荷物を落ろ
せても、ＮＰ完全である事も示した。
Back