マルチ基準グラフ探索における制御メカニズムとしてのスカイライン・ファースト探索

Abstract

多基準グラフ探索において経路は、パレート優越（Pareto dominance）によって比較されます。これは、どの経路が非支配（non-dominated）であるかを識別する順序付けですが、次にどの経路を展開すべきか、また探索をいつ停止できるかについては何も述べません。そのため、既存手法は外部の仕組みに依存しがちです。たとえばヒューリスティック、スカラー化（scalarization）、あるいは集団（population）ベースの探索などです。一方でパレート優越は、枝刈りや順位付けといった受動的な役割に閉じ込められていました。 本論文は、制約付きコストモデル、有限のコスト格子、マルコフ的遷移、そして非ゼロの進捗指標の下では、パレート幾何（Pareto geometry）だけでスケジューリングと停止の両方を駆動できることを示します。具体的には、最初のパレート層（第一パレート層）だけから抽出する、つまりスカイライン（skyline）を用いると、離散的な完了ポテンシャル（discrete completion potential）に対する決定的な降下が誘導されます。これにより、解の完了へ向けた単調な進捗が保証されます。並行して、ベクトル下界証明書（vector lower-bound certificate）が停止条件を与え、あらかじめ定めた解の数を必要とせずに、残りのすべての探索経路（traversal）に対する優越のカバー（dominance coverage）を保証します。 本解析により、決定的なポテンシャル降下、優越のカバーによって認証される決定的な停止、コスト格子幾何によって誘導される層幅の一様な上界、そしてスカイライン内での貪欲なコスト空間の分散（greedy cost-space dispersion）が確立されます。得られる枠組みは、スカラー化、ヒューリスティックによる誘導、あるいは確率モデルを用いずに動作し、パレート優越の位置づけを受動的なフィルタから、探索を駆動する決定的な要因へと作り替えます。