最短路算法の実際的評価と新バケット法

概要

論文の詳細を見る
最短路問題はネットワーク・フロー問題の中でも最も頻繁に現われる問題であり、その解法の歴史も長い。そして、近年では、実用的な立場も含めた算法の研究が大幅に進み、有用な成果があげられている。本論文では、ネットワークの1点(入口)から他の全ての点への最短路を求める問題(枝の長さは非負とする)を取り上げ、計算機実験に基づいて、既に提案された各種算法の性質をより詳しく解明するとともに、新たにバケットを有効に利用する算法(可変バケット法と呼ぶ)を提案し、その有用性を確かめている。計算機実験の対象とした既存の算法は、ラベル修正法(いわゆるポテンシャル法)のF1FO法、two-way sequence法、そしてラベル確定法(いわゆるDijkstra法)のヒープ法、1水準、及び2水準バケット法である。計算機実験における試験ネットワークとしては、ランダム・ネットワーク、格子状ネットワークといった人為的なものと、実際の道路網(首都圏、甲府市、関東地方)とを用いた。また、関東地方道路網のデータについては、枝の長さを"加工"したものを用いて、それにより、各種算法の性質を明らかにすることを試みた。ラベル確定法の中では、バケットを利用した1水準(2水準)バケット法が有効であることが知られていたが、この方法は、計算の手間が非位相的なパラメタ(枝の長さ)に大いに依存するという欠点があった。ここで提案する可変バケット法の特徴は、算法の必要とするバケットの総数が、枝の長さとは無関係に、ネットワ一クの点の数の定数倍で抑えられることである。その代わり、可変バケット法は厳密な意味でのラベル確定法ではなくなり、1つのバケットで管理している一点に関して、さらに何れかの最短路算法を用いなければならない(通常、この部分問題は規模が小さく、性質がよいので高速に解ける)。また、この部分問題を解くのにラベル修正法を用いた場合、可変バケット法はラベル修正法の不安定要因をバケットにより抑えた方法ともみなせる。計算機実験を通じて得た結論は次の通りである。ラベル修正法のtWO-Way Sequence法はかなりの場合(特に、不規則要因の少ない道路網)に有効な方法であるが、ネットワークが複雑さを増すと極度に遅くなりうる。その点、ラベル確定法は安定しており、特に、1水準バケット法は、two-way sequence法と比べて、時間的に殆んど劣らない。但し、非常に長い最短路、又は極端に短い枝がある場合、1水準バケット法は、有効でなくなる。ここで提案した可変バケット法は、ネットワークの構造、枝の長さの変化に対して頑健であり、しかも常に最も速い算法のクラスに属している。すなわち、安定して速いといえる。
社団法人日本オペレーションズ・リサーチ学会の論文

最短路算法の実際的評価と新バケット法

スポンサーリンク

概要

著者

関連論文

スポンサーリンク