サイクルグラフ上での地図作成問題に対する重み付き最近傍アルゴリズム

概要

論文の詳細を見る
グラフ上での地図作成問題とは,探索者が未知のグラフの全ての頂点を訪問することによりグラフ構造を調査する問題である.探索者は辺の存在とその長さをその端点を訪れるまで判らないとする.探索者は,できるだけ短い経路を通ることにより全ての頂点と辺を調査して,出発点まで戻って来なければならない.本問題に対する最も単純な方法の一つは,最近傍アルゴリズム(NN)であり,まだ訪れていない頂点の中で探索者の現在の場所から最も近い場所に移動する戦略である.重み付き最近傍アルゴリズム(WNN)は,NNの拡張であり,ある重み付きの距離により次の移動場所を決める.平面グラフにおいては,重み3であるWNNが16競合であることが知られている.本稿ではサイクルグラフについては,NNの競合比が1.5となること,その解析が厳密であることを示す.また,サイクルグラフに対してはWNNの中でNNが最適であることを示す.さらに,本問題に対しては,1.25競合よりも良いアルゴリズムが存在しないことを示す.
社団法人電子情報通信学会の論文
2006-11-27