妨害者のいる場合の最短経路問題

山口 一章  荒木 俊郎  柏原 敏伸  

誌名
電子情報通信学会論文誌 A   Vol.J79-A   No.11   pp.1866-1876
発行日: 1996/11/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5707
論文種別: 論文
専門分野: グラフとネットワーク
キーワード: 
最短経路,  アルゴリズム,  P-SPACE-complete,  2人ゲーム,  ネットワーク,  経路制御,  

本文: PDF(582.8KB)>>
論文を購入




あらまし: 
出発地,目的地なる2頂点stが指定されたグラフG=(VE),妨害数なる正整数k,各辺の(正の)重みl(・)が与えられている.このとき,2人の競技者P1とP2が以下のルールに従ってゲームを行う.P1はsを出発点地とし,1回に一つの辺をたどって目標地点tまで行こうとする.P2は自分の手番にいくつかの辺を切断する.P2の切断できる辺の数はゲームを通じてk本までとする.P1,P2ともグラフ全体が見えているものとする.P1は自分の通る辺の長さの和(道のり)ができるだけ小さくなるようにし,P2はできるだけ大きくなるようにする.本論文では,2人が最善を尽くしたときの道のりをOnk-1mn log n))(m=|E|,n=|V|)時間で求め得ることを示す.また,2人が最善を尽くしたときの道のりが与えられたある正整数以下であるか否かを判定する問題はすべての辺の長さを1とした場合でもP-SPACE-completeであることを示す.