多重解像度補間メッシュに基づく経路探索手法

摘要

大規模グラフにおける経路探索の高速化を目的として，ネットワークの持つ階層構造を利用した解法が研究されている．本論文では階層構造間のフラクタルに着目した高速経路探索手法を提案する．本論文はフラクタルとして3Dモーフィングのデータ構造に用いられている多重解像度補間メッシュを利用し，低解像度層からのトップダウン方式の探索アルゴリズムを与える．このとき探索する層が高解像度になるほど探索される経路数が増加し，計算時間に影響が出る．この課題に対して分枝限定法によって最短になり得ない経路を発見し、その経路は以降の探索を中止とする．これによって探索の効率化を図る．また実際のネットワークは必ずしもメッシュ構造をしていない．この課題に対しては，与えられたグラフより近似的にメッシュを生成する手法を提案することにより解決する．数値実験により提案探索アルゴリズムが問題の規模にかかわらず，安定した計算時間で探索できることを示す．また実際のネットワークより近似的に生成したメッシュ上での探索を行い，近似解が高速に求まることを示す．