Pat

J-GLOBAL ID：200903086301216014

複数の最適解を求めるグラフ最短経路探索方法及び装置

Inventor： 丸山 宏 ,  武田 浩一
Applicant, Patent owner： インターナシヨナル・ビジネス・マシーンズ・コーポレイシヨン
Agent (1)： 頓宮 孝一 (外4名)
Gazette classification：公開公報
Application number (International application number)：1991211293
Publication number (International publication number)：1993046590
Application date： Jul. 30, 1991
Publication date： Feb. 26, 1993
Summary：

【要約】【目的】最適性の保証された複数個の解を高速に発見するグラフ探索手法を提供する。【構成】グラフの最短経路を求める手法として、まず、頂点間の辺に実数値のコストが付いた有向グラフの任意の頂点と終点tとの最短コストを算出し、次に、前記有向グラフGの始点sからの部分経路を、始点sからのコストの累積g(Xi)と、残りの経路の前記最短コストh(Xi)との和f(Xi)に基づき、設定された解析条件に従って下位を枝刈りしながら、a,a+1のごとく終点tに向けて逐次的に経路展開し、探索が終了した時点で保持されている上位N個の最適な経路を出力する。【効果 】本発明によれば、予め残りの経路の最短コストを算出し、これに始点からのコストの累積を加えつつ、解析条件に従って複数(N)の経路について展開するため、解の複数性と最適性が同時に確保され、しかも下位のコスト値の経路を枝刈りしながら逐次的に展開するため、処理の高速性も確保される。

Claim (excerpt)：

入力手段、演算処理手段、記憶手段及び出力手段を備えたグラフ探索装置によって、与えられたグラフについて経路を探索し、出力するグラフ探索方法において、前記入力手段によって、頂点間の辺に実数値のコストが付いた有向グラフGと、その中の特定の2頂点を始点s及び終点tとして与えるグラフ入力ステップと、複数の経路を解析するための条件を入力する条件設定ステップと、前記有向グラフGを前記記憶手段に記憶するグラフ保持ステップと、前記演算処理手段により、前記有向グラフGの任意のノードと終点tとの最短コストを算出する最短コスト算出ステップと、前記演算処理手段により、前記有向グラフGの始点sからの部分経路を、始点sからのコストの累積と、残りの経路の前記最短コストとの和に基づき、前記設定条件にしたがって下位の経路を枝刈りしながら、逐次的に展開する経路展開ステップと、展開された複数の前記部分経路を前記記憶手段に保持するための部分経路保持ステップと、探索が終了した時点で前記記憶手段に保持されている前記複数の部分経路を前記出力手段に出力する解経路出力ステップを有する、ことを特徴とするグラフ探索方法。

IPC (3)：

G06F 15/20 ,  G06F 15/31 ,  G06F 15/36