JP2002133351A

JP2002133351A - 最小コスト経路探索装置及びそれに用いる最小コスト経路探索方法

Info

Publication number: JP2002133351A
Application number: JP2000324808A
Authority: JP
Inventors: Kenji Soga; 健二曽我
Original assignee: NEC Corp
Current assignee: NEC Corp
Priority date: 2000-10-25
Filing date: 2000-10-25
Publication date: 2002-05-10
Also published as: KR100402528B1; EP1206144A3; CN1350244A; US20020059213A1; EP1206144A2; KR20020032385A

Abstract

(57)【要約】【課題】出ノード毎に最小コスト経路をコストの小さ
い順に任意の数だけ制限された記憶量の中で求め、高速
に経路の探索が可能な最小コスト経路探索方法を提供す
る。【解決手段】ステップＳ１のコスト予測で中間ノード
からすべての出ノードまでのコストを予測し、ステップ
Ｓ２の経路生成で現在探索中の経路に対して隣接ノード
まで延長した経路を生成する。ステップＳ３の経路記憶
で生成された経路に対して経路チェックを行い、記憶部
が空いていればその経路を記憶する。ステップＳ４の経
路選択ですべての中間ノード及び入ノードで記憶部に記
憶されている経路の中から、未だ選択されていない経路
で、経路コストと最小予測コストとの合計が最小の経路
を現在探索中の経路として選択する。ステップＳ６の経
路出力で出ノードに記憶されている経路を探索結果とし
て出力する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は最小コスト経路探索
装置及びそれに用いる最小コスト経路探索方法に関し、
特にネットワークにおける最小コストの入ノードから出
ノードまでの経路の探索方法に関する。

【０００２】

【従来の技術】従来、この種の最小コスト経路探索方法
としては、ダイクストラ法による探索が一般に知られて
いる。ダイクストラ法は一つの出ノードに対し、最小コ
ストの経路を１本だけ探索する方法である。

【０００３】すなわち、ダイクストラ法はネットワーク
に関する代表的な最適化問題の一つである最短路問題と
して広く使われている数理計画上の手法であり、出発点
のノードから目的点のノードへの経路で最も短くなるも
のを見い出す問題を示す最短路問題を解決する方法であ
る。

【０００４】この場合、出発点のノードから目的点のノ
ードへの最短路をあるノードで分割し、その分割した２
つの最短路がそれぞれの集合内で最短路になるという最
適性の原理を利用して数理的に最短路を求めている。つ
まり、ダイクストラ法は空集合から始めて最短路となる
ノードを一つずつ求めて最短路部分集合を膨らませてい
き、最終的に全部のノードに対して最短路を求める方法
である。

【０００５】また、経路をコストの小さい順にすべて探
索する探索方法の一例が、「交差点内コストを考慮した
道路網における経路探索の手法とそのマルチメディア型
経路案内システムへの応用」（情報処理学会論文誌Ｖｏ
ｌ．３３Ｎｏ．７，１９９２年６月，ｐｐ９７０−９
７９）に記載された方法もある。この探索方法は全ての
経路を探索するために、探索中に経路を記憶しておく方
法である。

【０００６】上記の探索方法では、まずリンクの離脱コ
スト、出リンクに対する入リンク及びコスト差分のリス
トを求め、これを利用して目的点までの最小コスト経路
の木を育てる手法が採られている。

【０００７】

【発明が解決しようとする課題】しかしながら、従来の
探索方法では、ダイクストラ法を用いる場合、一つの出
ノードに対して最小コストの経路を１本だけ探索してい
るので、コストの小さい順に複数の経路を探索すること
ができない。

【０００８】また、探索方法として最小コスト経路の木
を育てる手法を用いる場合には、全ての経路を探索して
いるため、探索中に経路を記憶しておくために必要な記
憶量が多量に必要な上、必要量が探索をしてみないと判
らないという問題がある。特に、枝分かれの多いトポロ
ジでは記憶しておくべき探索途中の経路を記憶すること
ができずに、求めようとした経路が探索から漏れ、経路
がコストの小さい順に求まらない場合もある。

【０００９】そこで、本発明の目的は上記の問題点を解
消し、出ノード毎に最小コスト経路をコストの小さい順
に任意の数だけ制限された記憶量の中で求めることがで
き、高速に経路の探索を行うことができる最小コスト経
路探索装置及びそれに用いる最小コスト経路探索方法を
提供することにある。

【００１０】

【課題を解決するための手段】本発明による最小コスト
経路探索装置は、ネットワークにおける最小コストの入
ノードから出ノードまでの経路を探索する最小コスト経
路探索装置であって、予め中間ノードから前記出ノード
までのコストを予測して求めるコスト予測手段と、前記
入ノードから前記中間ノードまでの途中経路に対して前
記中間ノードに隣接するノードまで経路を延長した経路
を生成する経路生成手段と、記憶する経路数を制御しな
がら経路生成で生成された経路の中で記憶する経路を取
捨選択する経路記憶手段と、前記経路記憶手段で記憶さ
れた経路の中から最適な経路を１つ選択する経路選択手
段と、前記経路記憶手段に記憶されている経路がない時
に探索された経路を出力する経路出力手段とを備えてい
る。

【００１１】本発明による最小コスト経路探索方法は、
ネットワークにおける最小コストの入ノードから出ノー
ドまでの経路を探索する最小コスト経路探索方法であっ
て、予め中間ノードから前記出ノードまでのコストを予
測して求めるステップと、前記入ノードから前記中間ノ
ードまでの途中経路に対して前記中間ノードに隣接する
ノードまで経路を延長した経路を生成するステップと、
記憶する経路数を制御しながらその生成された経路の中
で記憶する経路を取捨選択するステップと、この記憶さ
れた経路の中から最適な経路を１つ選択するステップ
と、記憶されている経路がない時に探索された経路を出
力するステップとを備えている。

【００１２】すなわち、本発明の最小コスト経路探索方
法では、コスト予測で予め中間ノードから出ノードまで
のコストを予測して求め、経路生成で入ノードから中間
ノードまでの途中経路に対して中間ノードに隣接するノ
ードまで経路を延長した経路を生成し、経路記憶で記憶
する経路数を制御しながら経路生成で生成された経路の
中で記憶する経路を取捨選択し、経路選択において経路
記憶で記憶されている経路の中から最適な経路を１つ選
択し、経路生成へ戻る。この場合、経路記憶に記憶され
ている経路がなければ、経路選択で経路の選択を終了
し、経路出力で探索された経路を出力して経路探索を終
了する。

【００１３】このようにして、任意の数の経路をコスト
の小さい順に制限された記憶量の中で求めることができ
る。また、コスト予測にて予めコストを予測し、経路記
憶で記憶する経路数を制限することによって、経路探索
時間を短縮している。

【００１４】

【発明の実施の形態】次に、本発明の実施例について図
面を参照して説明する。図１は本発明の一実施例による
最小コスト経路探索装置の構成を示すブロック図であ
る。図１において、本発明の一実施例による最小コスト
経路探索装置はコスト予測部１と、経路生成部２と、経
路記憶部３と、経路選択部４と、経路出力部５と、記憶
部６とから構成されている。

【００１５】コスト予測部１は中間ノードからすべての
出ノードまでのコストを予測する。経路生成部２は現在
探索中の経路に対して隣接ノードまで延長した経路を生
成する。経路記憶部３は経路生成部２で生成された経路
に対して経路チェックを行い、経路の到達ノードに一定
数まで記憶部６に記憶する。

【００１６】経路選択部４はすべての中間ノード及び入
ノードで記憶されている経路の中から、未だ選択されて
いない経路で、経路コストと最小予測コストとの合計が
最小の経路を現在探索中の経路として選択する。経路出
力部５は出ノードに記憶されている経路を探索結果とし
て出力する。その場合には、全ての出ノードに対して各
ノードに用意した記憶数だけの経路がコストの小さい順
に出力される。

【００１７】図２は本発明の一実施例による最小コスト
経路探索方法の処理動作を示すフローチャートであり、
図３は図１の経路記憶部３の動作を示すフローチャート
である。これら図１〜図３を参照して本発明の一実施例
による最小コスト経路探索方法の処理動作について説明
する。

【００１８】まず、コスト予測部１は中間ノードからす
べての出ノードまでのコストを予測する（図２ステップ
Ｓ１）。この場合、予測した各出ノードまでの予測コス
トの中で最小の値を最小予測コストとして各中間ノード
に記憶しておく。また、予測方法としては、（１）本探
索方法の利用者が入力する方法、（２）ネットワークに
関する代表的な最適化問題の一つである最短路問題とし
て広く使われている数理計画上の手法であるダイクスト
ラ法等によって最小コストを計算する方法、（３）固定
値を入力する方法等が考えられる。

【００１９】続いて、経路生成部２では現在探索中の経
路に対して隣接ノードまで延長した経路を生成する（図
２ステップＳ２）。初回の経路生成では入ノードを現在
探索中の経路として実行する。

【００２０】経路記憶部３では、まず、経路生成部２で
生成された経路に対して経路チェックを行う（図３ステ
ップＳ１１）。経路チェックではその経路が同一ノード
を複数回通過していないかどうかを調べる。

【００２１】同一ノードを複数回通過している場合には
その経路をＮＧとし、該経路の廃棄を行う（図３ステッ
プＳ１２）。また、同一ノードを複数回通過していない
場合にはその経路をＯＫとし、記憶部６の記憶数の確認
を行う（図３ステップＳ１３）。記憶数の確認では該経
路の到達ノードに記憶されている経路の数を確認する。
ここで、経路はその経路の到達ノードに一定数まで記憶
部６に記憶され、その数はトポロジ上のすべてのノード
で一定であるとする。

【００２２】記憶数に空きがある場合には、該経路の記
憶を行い、経路の道筋および経路コストとして該経路上
のリンクの通過コストの合計を記憶する（図３ステップ
Ｓ１４）。記憶数に空きが無い場合には、最大コスト経
路の廃棄を行う（図３ステップＳ１５）。最大コスト経
路の廃棄では該経路及び該経路の到達ノードに記憶され
ている経路のなかで経路コストが最大の経路を廃棄す
る。

【００２３】記憶されていた経路が廃棄された場合に
は、そのできた空きに該経路の道筋及び経路コストを記
憶する。上記の処理動作を経路生成部２で生成された全
ての経路に対して繰り返し実行する（図３ステップＳ１
１〜Ｓ１６）。

【００２４】経路選択部４ではすべての中間ノード及び
入ノードで記憶部６に記憶されている経路の中から、未
だ選択されていない経路で、経路コストと最小予測コス
トとの合計が最小の経路を現在探索中の経路として選択
する（図２ステップＳ４）。選択できた場合には（図２
ステップＳ５）、ステップＳ１の経路生成に戻る。

【００２５】選択できなかった場合には経路出力部５に
進み、経路出力部５で出ノードに記憶されている経路を
探索結果として出力し（図２ステップＳ６）、上記の経
路探索を終了する。上記の経路探索では全ての出ノード
に対して、記憶部６において各ノードに用意した記憶数
だけの経路がコストの小さい順に出力される。

【００２６】図４は本発明の一実施例で適用するトポロ
ジの例を示す図であり、図５は図４に示すトポロジに対
してダイクストラ法を用いて算出した予測コストを示す
図である。これら図１と図４と図５とを参照して本発明
の一実施例による最小コスト経路探索方法の具体的な処
理動作について説明する。

【００２７】図４においては入ノードをａ、出ノードを
ｂ，ｃとし、中間ノードをＡ，Ｂ，Ｃ，Ｄ，Ｅとしてい
る。また、リンクのそばに記した数字はリンクの通過コ
ストである。例えば、ノードａとノードＡとの間のリン
クを通過する時にはコスト「１」が掛かることを示して
いる。また、各ノードに記憶できる経路の数は２とす
る。

【００２８】まず、コスト予測部１では各中間ノードで
の出ノードまでの予測コストを与え、最小予測コストを
記憶する。例えば、ダイクストラ法を用いて予測する
と、図５に示すようになる。経路生成部２では初回の経
路生成となるので、入ノードａが現在探索中の経路とな
り、ａの隣接ノードＡまで延長した経路ａ→Ａが生成さ
れる。

【００２９】経路記憶部３では経路ａ→Ａの経路チェッ
クが行われる。経路ａ→Ａは複数回通過するノードがな
いためＯＫとなる。記憶数の確認では該経路の到達ノー
ドであるノードＡに記憶されている経路がないので、該
経路の記憶に進み、記憶部６のノードＡに経路ａ→Ａ及
びその経路コスト「１」が記憶される。

【００３０】経路選択部４では入ノード、中間ノードに
記憶されている経路がノードＡの経路ａ→Ａだけであ
り、この経路は未だ選択されていないので、この経路が
現在探索中の経路となり、経路生成部２に戻る。

【００３１】２度目の経路生成では経路ａ→Ａを現在探
索中の経路として、経路ａ→Ａ→Ｂ、経路ａ→Ａ→Ｃ、
経路ａ→Ａ→ａの３本の経路が生成される。経路記憶で
は経路チェックにて経路ａ→Ａ→ａがノードａを２度通
っているのでＮＧとなり、該経路の廃棄が行われる。経
路数の確認で空きがあるため、該経路の記憶で経路ａ→
Ａ→Ｂ（経路コスト＝４）、経路ａ→Ａ→Ｃ（経路コス
ト＝２）がそれぞれノードＢ、ノードＣに記憶される。

【００３２】ここで、まだ選択されておらず入ノード、
中間ノードに記憶されている経路は、ノードＢに記憶さ
れている経路ａ→Ａ→Ｂ（経路コスト＋最小予測コスト
＝６）、ノードＣに記憶されている経路ａ→Ａ→Ｃ（経
路コスト＋最小予測コスト＝５）である。経路選択では
この中で経路コストと最小予測コストとの合計が最も小
さい経路ａ→Ａ→Ｃを現在探索中の経路とし、経路生成
に戻る。

【００３３】３度目の経路生成では、経路ａ→Ａ→Ｃを
現在探索中の経路として、経路ａ→Ａ→Ｃ→Ｅ、経路ａ
→Ａ→Ｃ→Ｂ、経路ａ→Ａ→Ｃ→Ａの３本の経路が生成
される。経路記憶では経路チェックにて経路ａ→Ａ→Ｃ
→ＡがノードＡを２度通っているのでＮＧとなり、該経
路の廃棄が行われる。経路数の確認で空きがあるため、
該経路の記憶で経路ａ→Ａ→Ｃ→Ｅ（経路コスト＝
６）、経路ａ→Ａ→Ｃ→Ｂ（経路コスト＝３）がそれぞ
れノードＥ、ノードＢに記憶される。

【００３４】ここで、まだ選択されておらず入ノード、
中間ノードに記憶されている経路は、ノードＢに記憶さ
れている経路ａ→Ａ→Ｂ（経路コスト＋最小予測コスト
＝６）、経路ａ→Ａ→Ｃ→Ｂ（経路コスト＋最小予測コ
スト＝５）、ノードＥに記憶されている経路ａ→Ａ→Ｃ
→Ｅ（経路コスト＋最小予測コスト＝７）である。経路
選択ではこの中で経路コストと最小予測コストとの合計
が最も小さい経路ａ→Ａ→Ｃ→Ｂを現在探索中の経路と
し、経路生成に戻る。

【００３５】４度目の経路生成では、経路ａ→Ａ→Ｃ→
Ｂを現在探索中の経路として、経路ａ→Ａ→Ｃ→Ｂ→
ｃ、経路ａ→Ａ→Ｃ→Ｂ→Ｄ、経路ａ→Ａ→Ｃ→Ｂ→
Ａ、経路ａ→Ａ→Ｃ→Ｂ→Ｃの４本の経路が生成され
る。経路記憶では経路チェックにて経路ａ→Ａ→Ｃ→Ｂ
→ＡがノードＡを、経路ａ→Ａ→Ｃ→Ｂ→ＣがノードＣ
をそれぞれ２度通っているのでＮＧとなり、該経路の廃
棄が行われる。経路数の確認で空きがあるため、該経路
の記憶で経路ａ→Ａ→Ｃ→Ｂ→ｃ（経路コスト＝５）、
経路ａ→Ａ→Ｃ→Ｂ→Ｄ（経路コスト＝４）がそれぞれ
ノードｃ、ノードＤに記憶される。

【００３６】ここで、まだ選択されておらず入ノード、
中間ノードに記憶されている経路は、ノードＢに記憶さ
れている経路ａ→Ａ→Ｂ（経路コスト＋最小予測コスト
＝６）、ノードＥに記憶されている経路ａ→Ａ→Ｃ→Ｅ
（経路コスト＋最小予測コスト＝７）、ノードＤに記憶
されている経路ａ→Ａ→Ｃ→Ｂ→Ｄ（経路コスト＋最小
予測コスト＝７）である。経路選択ではこの中で経路コ
ストと最小予測コストとの合計が最も小さい経路ａ→Ａ
→Ｂを現在探索中の経路とし、経路生成に戻る。

【００３７】５度目の経路生成では、経路ａ→Ａ→Ｂを
現在探索中の経路として、経路ａ→Ａ→Ｂ→ｃ、経路ａ
→Ａ→Ｂ→Ｄ、経路ａ→Ａ→Ｂ→Ａ、経路ａ→Ａ→Ｂ→
Ｃの４本の経路が生成される。経路記憶では経路チェッ
クにて経路ａ→Ａ→Ｂ→ＡがノードＡを２度通っている
のでＮＧとなり、該経路の廃棄が行われる。経路数の確
認で空きがあるため、該経路の記憶で経路ａ→Ａ→Ｂ→
ｃ（経路コスト＝６）、経路ａ→Ａ→Ｂ→Ｄ（経路コス
ト＝５）、経路ａ→Ａ→Ｂ→Ｃ（経路コスト＝５）がそ
れぞれノードｃ、ノードＤ、ノードＣに記憶される。

【００３８】ここで、まだ選択されておらず入ノード、
中間ノードに記憶されている経路は、ノードＣに記憶さ
れている経路ａ→Ａ→Ｂ→Ｃ（経路コスト＋最小予測コ
スト＝８）、ノードＥに記憶されている経路ａ→Ａ→Ｃ
→Ｅ（経路コスト＋最小予測コスト＝７）、ノードＤに
記憶されている経路ａ→Ａ→Ｃ→Ｂ→Ｄ（経路コスト＋
最小予測コスト＝７）、経路ａ→Ａ→Ｂ→Ｄ（経路コス
ト＋最小予測コスト＝８）である。経路選択ではこの中
で経路コストと最小予測コストとの合計が最も小さい経
路ａ→Ａ→Ｃ→Ｅを現在探索中の経路とし、経路生成に
戻る。

【００３９】尚、経路ａ→Ａ→Ｃ→Ｂ→Ｄ及び経路ａ→
Ａ→Ｃ→Ｅは経路コスト＋最小予測コスト＝７で同点で
ある。同点の場合にはその中から任意に選択するものと
する。

【００４０】６度目の経路生成では、経路ａ→Ａ→Ｃ→
Ｅを現在探索中の経路として、経路ａ→Ａ→Ｃ→Ｅ→
ｂ、経路ａ→Ａ→Ｃ→Ｅ→Ｄ、経路ａ→Ａ→Ｃ→Ｅ→Ｃ
の３本の経路が生成される。経路記憶では経路チェック
にて経路ａ→Ａ→Ｃ→Ｅ→ＣがノードＣを２度通ってい
るのでＮＧとなり、該経路の廃棄が行われる。経路数の
確認で空きがあるため、該経路の記憶で経路ａ→Ａ→Ｃ
→Ｅ→ｂ（経路コスト＝７）がノードｂに記憶される。

【００４１】一方、記憶数の確認でノードＤに記憶され
るべき経路ａ→Ａ→Ｃ→Ｅ→Ｄ（経路コスト＝９）につ
いては、既にノードＤに上限である２つの経路が記憶さ
れているため、最大コスト経路の廃棄が行われる。この
場合、比較の対称となる経路は経路ａ→Ａ→Ｃ→Ｂ→Ｄ
（経路コスト＝４）、経路ａ→Ａ→Ｂ→Ｄ（経路コスト
＝５）、経路ａ→Ａ→Ｃ→Ｅ→Ｄ（経路コスト＝９）で
あり、経路コスト最大の経路ａ→Ａ→Ｃ→Ｅ→Ｄが廃棄
され、残りの経路がノードＤに記憶される。

【００４２】ここで、まだ選択されておらず入ノード、
中間ノードに記憶されている経路は、ノードＣに記憶さ
れている経路ａ→Ａ→Ｂ→Ｃ（経路コスト＋最小予測コ
スト＝８）、ノードＤに記憶されている経路ａ→Ａ→Ｃ
→Ｂ→Ｄ（経路コスト＋最小予測コスト＝７）、経路ａ
→Ａ→Ｂ→Ｄ（経路コスト＋最小予測コスト＝８）であ
る。経路選択ではこの中で経路コストと最小予測コスト
との合計が最も小さい経路ａ→Ａ→Ｃ→Ｂ→Ｄを現在探
索中の経路とし、経路生成に戻る。

【００４３】７度目の経路生成では、経路ａ→Ａ→Ｃ→
Ｂ→Ｄを現在探索中の経路として、経路ａ→Ａ→Ｃ→Ｂ
→Ｄ→Ｂ、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅの２本の経路が
生成される。経路記憶では経路チェックにて経路ａ→Ａ
→Ｃ→Ｂ→Ｄ→ＢがノードＢを２度通っているのでＮＧ
となり、該経路の廃棄が行われる。経路数の確認で空き
があるため、該経路の記憶で経路ａ→Ａ→Ｃ→Ｂ→Ｄ→
Ｅ（経路コスト＝７）がノードＥに記憶される。

【００４４】ここで、まだ選択されておらず入ノード、
中間ノードに記憶されている経路は、ノードＣに記憶さ
れている経路ａ→Ａ→Ｂ→Ｃ（経路コスト＋最小予測コ
スト＝８）、ノードＥに記憶されている経路ａ→Ａ→Ｃ
→Ｂ→Ｄ→Ｅ（経路コスト＋最小予測コスト＝８）、ノ
ードＤに記憶されている経路ａ→Ａ→Ｂ→Ｄ（経路コス
ト＋最小予測コスト＝８）である。経路選択ではこの中
で経路コストと最小予測コストとの合計が最も小さい経
路ａ→Ａ→Ｂ→Ｃを現在探索中の経路とし、経路生成に
戻る。

【００４５】尚、経路ａ→Ａ→Ｂ→Ｃ、経路ａ→Ａ→Ｃ
→Ｂ→Ｄ→Ｅ、経路ａ→Ａ→Ｂ→Ｄは経路コスト＋最小
予測コスト＝８で同点である。同点の場合にはその中か
ら任意に選択するものとする。

【００４６】８度目の経路生成では、経路ａ→Ａ→Ｂ→
Ｃを現在探索中の経路として、経路ａ→Ａ→Ｂ→Ｃ→
Ｂ、経路ａ→Ａ→Ｂ→Ｃ→Ｅ、経路ａ→Ａ→Ｂ→Ｃ→Ａ
の３本の経路が生成される。経路記憶では経路チェック
にて経路ａ→Ａ→Ｂ→Ｄ→ＢがノードＢを、経路ａ→Ａ
→Ｂ→Ｃ→ＡがノードＡをそれぞれ２度通っているので
ＮＧとなり、該経路の廃棄が行われる。

【００４７】また、記憶数の確認でノードＥに記憶され
るべき経路ａ→Ａ→Ｂ→Ｃ→Ｅ（経路コスト＝９）につ
いては、既にノードＥに上限である２つの経路が記憶さ
れているため、最大コスト経路の廃棄が行われる。この
場合、比較の対称となる経路は経路ａ→Ａ→Ｃ→Ｅ（経
路コスト＝６）、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ（経路コ
スト＝７）、経路ａ→Ａ→Ｂ→Ｃ→Ｅ（経路コスト＝
９）であり、経路コスト最大の経路ａ→Ａ→Ｂ→Ｃ→Ｅ
が廃棄され、残りの経路がノードＥに記憶される。

【００４８】ここで、まだ選択されておらず入ノード、
中間ノードに記憶されている経路は、ノードＥに記憶さ
れている経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ（経路コスト＋最
小予測コスト＝８）、ノードＤに記憶されている経路ａ
→Ａ→Ｂ→Ｄ（経路コスト＋最小予測コスト＝８）であ
る。経路選択ではこの中で経路コストと最小予測コスト
との合計が最も小さい経路ａ→Ａ→Ｂ→Ｄを現在探索中
の経路とし、経路生成に戻る。

【００４９】尚、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ、経路ａ
→Ａ→Ｂ→Ｄは経路コスト＋最小予測コスト＝８で同点
である。同点の場合にはその中から任意に選択するもの
とする。

【００５０】９度目の経路生成では、経路ａ→Ａ→Ｂ→
Ｄを現在探索中の経路として、経路ａ→Ａ→Ｂ→Ｄ→
Ｂ、経路ａ→Ａ→Ｂ→Ｄ→Ｅの２本の経路が生成され
る。経路記憶では経路チェックにて経路ａ→Ａ→Ｂ→Ｄ
→ＢがノードＢを２度通っているのでＮＧとなり、該経
路の廃棄が行われる。

【００５１】記憶数の確認にてノードＥに記憶されてい
る経路が既に上限の２つに達しているため、最大コスト
経路の廃棄３５が行われる。この場合、比較の対称とな
る経路は経路ａ→Ａ→Ｃ→Ｅ（経路コスト＝６）、経路
ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ（経路コスト＝７）、経路ａ→
Ａ→Ｂ→Ｄ→Ｅ（経路コスト＝８）であり、経路コスト
最大の経路ａ→Ａ→Ｂ→Ｄ→Ｅが廃棄され、残りの経路
がノードＥに記憶される。

【００５２】ここで、まだ選択されておらず入ノード、
中間ノードに記憶されている経路は、ノードＥに記憶さ
れている経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ（経路コスト＋最
小予測コスト＝８）だけであり、経路選択ではこの経路
を現在探索中の経路とし、経路生成に戻る。

【００５３】１０度目の経路生成では、経路ａ→Ａ→Ｃ
→Ｂ→Ｄ→Ｅを現在探索中の経路として、経路ａ→Ａ→
Ｃ→Ｂ→Ｄ→Ｅ→ｂ、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ→
Ｄ、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ→Ｃの３本の経路が生
成される。経路記憶では経路チェックにて経路ａ→Ａ→
Ｃ→Ｂ→Ｄ→Ｅ→ＣがノードＣを、経路ａ→Ａ→Ｃ→Ｂ
→Ｄ→Ｅ→ＤがノードＤをそれぞれ２度通っているので
ＮＧとなり、該経路の廃棄が行われる。経路数の確認で
空きがあるため、該経路の記憶で経路ａ→Ａ→Ｃ→Ｂ→
Ｄ→Ｅ→ｂ（経路コスト＝８）がノードｂに記憶され
る。ここで、まだ選択されておらず、入ノード、中間ノ
ードに記憶されている経路は無くなり、経路出力５が行
われる。

【００５４】経路出力では、出ノードｂに記憶されてい
る経路ａ→Ａ→Ｃ→Ｅ→ｂ、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→
Ｅ→ｂと、出ノードｃに記憶されている経路ａ→Ａ→Ｃ
→Ｂ→ｃ、経路ａ→Ａ→Ｂ→ｃとの２本ずつが出力され
る。上述したように動作することで、確かに、出ノード
ｂ，ｃに対してそれぞれ指定した本数の２本ずつの経路
がコストの小さい順に出力されている。

【００５５】このように、中間ノード、出ノードに探索
途中の経路を記憶する時に、記憶する経路数を制御しな
がら記憶する経路を適切に選択することによって、出ノ
ード毎に最小コスト経路をコストの小さい順に任意の数
だけ制限された記憶量の中で求めることができる。ま
た、予めコスト予測を行い、探索途中の経路の記憶数を
制限して探索範囲を狭めることによって、高速に経路の
探索を行うことができる。

【００５６】次に、本発明の他の実施例による最小コス
ト経路探索方法について説明する。本発明の他の実施例
による最小コスト経路探索方法は図３に示す経路記憶の
処理における記憶する経路数及び記憶する経路の選択を
変更し、求まる経路の性質を変えている以外は上述した
本発明の一実施例による最小コスト経路探索方法と同様
であり、その装置構成は本発明の一実施例と同様であ
る。

【００５７】本発明の他の実施例では記憶することがで
きる経路数をトポロジ全体で一定数としている。この変
更によって、出ノード全体でコストの小さい順に任意の
数の経路が求まるようになる。以下、本発明の他の実施
例の動作について説明する。尚、本発明の他の実施例に
よるコスト予測及び経路生成の動作は上述した本発明の
一実施例と同様である。

【００５８】本発明の他の実施例における経路記憶で
は、まず経路生成で生成された経路に対して経路チェッ
クが行われる。経路チェックではその経路が同一ノード
を複数回通過していないかを調べる。同一ノードを複数
回通過している場合にはその経路をＮＧとし、該経路の
廃棄を行う。

【００５９】同一ノードを複数回通過していない場合に
はその経路をＯＫとし、記憶数の確認を行う。記憶数の
確認ではトポロジ全体で記憶されている経路の数を確認
する。記憶数に空きがある場合には該経路の記憶を行
い、経路の道筋及び経路コストと最小予測コストとの合
計を記憶する。

【００６０】記憶数に空きが無い場合には最大コスト経
路の廃棄を行う。最大コスト経路の廃棄では該経路及び
該経路の到達ノードに記憶されている経路であり、かつ
到達ノードが入ノード、中間ノードである経路の中で経
路コストと最小予測コストとの合計が最大の経路を廃棄
し、記憶されていた経路が廃棄された場合にはそのでき
た空きに該経路の道筋及び経路コストと最小予測コスト
との合計を記憶する。これを経路生成で生成された全て
の経路に対して繰り返し実行する。

【００６１】本発明の他の実施例における経路選択では
トポロジ全体で記憶されている経路の中から、到達ノー
ドが入ノード、中間ノードである経路の中から経路コス
トと最小予測コストとの合計が最小の経路を現在探索中
の経路として選択する。選択された経路は記憶から抜い
ておく。選択できた場合には経路生成に戻る。選択でき
なかった場合には経路出力に進む。

【００６２】本発明の他の実施例における経路出力では
トポロジ全体で記憶されている経路で到達ノードが出ノ
ードである経路を探索結果として出力し、経路探索を終
了する。このように、本発明の他の実施例における経路
探索では用意した記憶数だけの経路がトポロジ全体でコ
ストの小さい順に出力される。

【００６３】次に、図４に示すトポロジの例を用いて本
発明の他の実施例による最小コスト経路探索方法の処理
動作について具体的に説明する。本実施例ではトポロジ
全体で記憶することができる経路の数を４とする。

【００６４】まず、コスト予測は上記の本発明の一実施
例と同じ動作であり、本発明の他の実施例においてもダ
イクストラ法を用いると、図５に示すような内容とな
る。経路生成では初回の経路生成となるので、入ノード
ａが現在探索中の経路となり、入ノードａの隣接ノード
Ａまで延長した経路ａ→Ａが生成される。

【００６５】経路記憶では経路ａ→Ａの経路チェックが
行われる。経路ａ→Ａは複数回通過するノードがないた
めにＯＫとなる。記憶数の確認ではトポロジ全体で記憶
されている経路はないので、該経路の記憶に進み、ノー
ドＡに経路ａ→Ａ及びその経路コスト「１」と最小予測
コスト「４」との合計「５」が記憶される。

【００６６】経路選択ではトポロジ全体で記憶されてい
る経路が経路ａ→Ａだけであり、この経路は到達ノード
Ａが中間ノードであるので、この経路を記憶から抜くと
ともに、現在探索中の経路として経路生成に戻る。

【００６７】２度目の経路生成では、経路ａ→Ａを現在
探索中の経路として、経路ａ→Ａ→Ｂ、経路ａ→Ａ→
Ｃ、経路ａ→Ａ→ａの３本の経路が生成される。経路記
憶では経路チェックにて経路ａ→Ａ→ａがノードａを２
度通っているのでＮＧとなり、該経路の廃棄が行われ
る。経路数の確認で空きがあるため、該経路の記憶で経
路ａ→Ａ→Ｂ（経路コスト＋最小予測コスト＝６）、経
路ａ→Ａ→Ｃ（経路コスト＋最小予測コスト＝５）が記
憶される。

【００６８】ここで、記憶されている経路は経路ａ→Ａ
→Ｃ（経路コスト＋最小予測コスト＝５）、経路ａ→Ａ
→Ｂ（経路コスト＋最小予測コスト＝６）である。経路
選択ではこの中で経路コストと最小予測コストとの合計
が最も小さい経路ａ→Ａ→Ｃを記憶から抜くとともに、
現在探索中の経路として経路生成に戻る。

【００６９】３度目の経路生成では、経路ａ→Ａ→Ｃを
現在探索中の経路として、経路ａ→Ａ→Ｃ→Ａ、経路ａ
→Ａ→Ｃ→Ｂ、経路ａ→Ａ→Ｃ→Ｅの３本の経路が生成
される。経路記憶では経路チェックにて経路ａ→Ａ→Ｃ
→ＡがノードＡを２度通っているのでＮＧとなり、該経
路の廃棄が行われる。経路数の確認で空きがあるため、
該経路の記憶で経路ａ→Ａ→Ｃ→Ｂ（経路コスト＋最小
予測コスト＝５）、経路ａ→Ａ→Ｃ→Ｅ（経路コスト＋
最小予測コスト＝７）が記憶される。

【００７０】ここで、記憶されている経路は経路ａ→Ａ
→Ｃ→Ｂ（経路コスト＋最小予測コスト＝５）、経路ａ
→Ａ→Ｂ（経路コスト＋最小予測コスト＝６）、経路ａ
→Ａ→Ｃ→Ｅ（経路コスト＋最小予測コスト＝７）であ
る。経路選択ではこの中で経路コストと最小予測コスト
との合計が最も小さい経路ａ→Ａ→Ｃ→Ｂを記憶から抜
くとともに、現在探索中の経路として経路生成に戻る。

【００７１】４度目の経路生成では、経路ａ→Ａ→Ｃ→
Ｂを現在探索中の経路として、経路ａ→Ａ→Ｃ→Ｂ→
Ａ、経路ａ→Ａ→Ｃ→Ｂ→Ｃ、経路ａ→Ａ→Ｃ→Ｂ→
ｃ、経路ａ→Ａ→Ｃ→Ｂ→Ｄの４本の経路が生成され
る。経路記憶では経路チェックにて経路ａ→Ａ→Ｃ→Ｂ
→ＡがノードＡを、経路ａ→Ａ→Ｃ→Ｂ→ＣがノードＣ
をそれぞれ２度通っているのでＮＧとなり、該経路の廃
棄が行われる。経路数の確認で空きがあるため、該経路
の記憶で経路ａ→Ａ→Ｃ→Ｂ→ｃ（経路コスト＋最小予
測コスト＝５）、経路ａ→Ａ→Ｃ→Ｂ→Ｄ（経路コスト
＋最小予測コスト＝７）が記憶される。

【００７２】ここで、記憶されている経路は経路ａ→Ａ
→Ｃ→Ｂ→ｃ（経路コスト＋最小予測コスト＝５）、経
路ａ→Ａ→Ｂ（経路コスト＋最小予測コスト＝６）、経
路ａ→Ａ→Ｃ→Ｅ（経路コスト＋最小予測コスト＝
７）、経路ａ→Ａ→Ｃ→Ｂ→Ｄ（経路コスト＋最小予測
コスト＝７）である。経路選択ではこの中で経路コスト
と最小予測コストとの合計が最も小さく、到達ノードが
中間ノードである経路ａ→Ａ→Ｂを記憶から抜くととも
に、現在探索中の経路として経路生成に戻る。

【００７３】５度目の経路生成では、経路ａ→Ａ→Ｂを
現在探索中の経路として、経路ａ→Ａ→Ｂ→Ａ、経路ａ
→Ａ→Ｂ→Ｃ、経路ａ→Ａ→Ｂ→ｃ、経路ａ→Ａ→Ｂ→
Ｄの４本の経路が生成される。経路記憶では経路チェッ
クにて経路ａ→Ａ→Ｂ→ＡがノードＡを２度通っている
のでＮＧとなり、該経路の廃棄が行われる。経路数の確
認で空きが足りないため、最大コスト経路の廃棄が実行
される。

【００７４】この場合、コスト比較の対象となる経路は
経路ａ→Ａ→Ｃ→Ｅ（経路コスト＋最小予測コスト＝
７）、経路ａ→Ａ→Ｃ→Ｂ→Ｄ（経路コスト＋最小予測
コスト＝７）、経路ａ→Ａ→Ｂ→Ｃ（経路コスト＋最小
予測コスト＝８）、経路ａ→Ａ→Ｂ→Ｄ（経路コスト＋
最小予測コスト＝８）であり、他に記憶されている経路
ａ→Ａ→Ｃ→Ｂ→ｃ（経路コスト＋最小予測コスト＝
５）及びここで記憶しようとしている経路ａ→Ａ→Ｂ→
ｃ（経路コスト＋最小予測コスト＝６）は到達ノードが
出ノードであるため、廃棄の候補とはならない。

【００７５】したがって、コスト比較の対象となる経路
の内、記憶できるのは２つの経路だけで、残りの経路ａ
→Ａ→Ｂ→Ｃ（経路コスト＋最小予測コスト＝８）、経
路ａ→Ａ→Ｂ→Ｄ（経路コスト＋最小予測コスト＝８）
は最大コスト経路の廃棄で廃棄される。

【００７６】ここで、記憶されている経路は経路ａ→Ａ
→Ｃ→Ｂ→ｃ（経路コスト＋最小予測コスト＝５）、経
路ａ→Ａ→Ｂ→ｃ（経路コスト＋最小予測コスト＝
６）、経路ａ→Ａ→Ｃ→Ｅ（経路コスト＋最小予測コス
ト＝７）、経路ａ→Ａ→Ｃ→Ｂ→Ｄ（経路コスト＋最小
予測コスト＝７）である。経路選択ではこの中で経路コ
ストと最小予測コストとの合計が最も小さく、到達ノー
ドが中間ノードである経路ａ→Ａ→Ｃ→Ｅを記憶から抜
くとともに、現在探索中の経路として経路生成に戻る。
尚、経路ａ→Ａ→Ｃ→Ｅ、経路ａ→Ａ→Ｃ→Ｂ→Ｄは経
路コスト＋最小予測コスト＝７で同点である。同点の場
合にはその中から任意に選択するものとする。

【００７７】６度目の経路生成では、経路ａ→Ａ→Ｃ→
Ｅを現在探索中の経路として、経路ａ→Ａ→Ｃ→Ｅ→
Ｃ、経路ａ→Ａ→Ｃ→Ｅ→ｂ、経路ａ→Ａ→Ｃ→Ｅ→Ｄ
の３本の経路が生成される。経路記憶では経路チェック
にて経路ａ→Ａ→Ｃ→Ｅ→ＣがノードＣを２度通ってい
るのでＮＧとなり、該経路の廃棄が行われる。経路数の
確認で空きが足りないため、最大コスト経路の廃棄が実
行される。

【００７８】この場合、コスト比較の対象となる経路は
経路ａ→Ａ→Ｃ→Ｂ→Ｄ（経路コスト＋最小予測コスト
＝７）、経路ａ→Ａ→Ｃ→Ｅ→Ｄ（経路コスト＋最小予
測コスト＝１２）であり、他に記憶されている経路ａ→
Ａ→Ｃ→Ｂ→ｃ（経路コスト＋最小予測コスト＝５）、
経路ａ→Ａ→Ｂ→ｃ（経路コスト＋最小予測コスト＝
６）及びここで記憶しようとしている経路ａ→Ａ→Ｃ→
Ｅ→ｂ（経路コスト＋最小予測コスト＝７）は到達ノー
ドが出ノードであるため、廃棄の候補とはならない。

【００７９】したがって、コスト比較の対象となる経路
の内、記憶できるのは１つの経路だけで、残りの経路ａ
→Ａ→Ｃ→Ｅ→Ｄ（経路コスト＋最小予測コスト＝１
２）は最大コスト経路の廃棄で廃棄される。

【００８０】ここで、記憶されている経路は経路ａ→Ａ
→Ｃ→Ｂ→ｃ（経路コスト＋最小予測コスト＝５）、経
路ａ→Ａ→Ｂ→ｃ（経路コスト＋最小予測コスト＝
６）、経路ａ→Ａ→Ｃ→Ｅ→ｂ（経路コスト＋最小予測
コスト＝７）、経路ａ→Ａ→Ｃ→Ｂ→Ｄ（経路コスト＋
最小予測コスト＝７）である。経路選択ではこの中で経
路コストと最小予測コストとの合計が最も小さく、到達
ノードが中間ノードである経路ａ→Ａ→Ｃ→Ｂ→Ｄを記
憶から抜くとともに、現在探索中の経路として経路生成
に戻る。

【００８１】７度目の経路生成では、経路ａ→Ａ→Ｃ→
Ｂ→Ｄを現在探索中の経路として、経路ａ→Ａ→Ｃ→Ｄ
→Ｅ、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｂの２本の経路が生成
される。経路記憶では経路チェックにて経路ａ→Ａ→Ｃ
→Ｂ→Ｄ→ＢがノードＢを２度通っているのでＮＧとな
り、該経路の廃棄が行われる。経路数の確認で空きがあ
るため、該経路の記憶が実行され、経路ａ→Ａ→Ｃ→Ｂ
→Ｄ→Ｅ（経路コスト＋最小予測コスト＝８）が記憶さ
れる。

【００８２】ここで、記憶されている経路は経路ａ→Ａ
→Ｃ→Ｂ→ｃ（経路コスト＋最小予測コスト＝５）、経
路ａ→Ａ→Ｂ→ｃ（経路コスト＋最小予測コスト＝
６）、経路ａ→Ａ→Ｃ→Ｅ→ｂ（経路コスト＋最小予測
コスト＝７）、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ（経路コス
ト＋最小予測コスト＝８）である。経路選択ではこの中
で経路コストと最小予測コストとの合計が最も小さく、
到達ノードが中間ノードである経路ａ→Ａ→Ｃ→Ｂ→Ｄ
→Ｅを記憶から抜くとともに、現在探索中の経路として
経路生成に戻る。

【００８３】８度目の経路生成では、経路ａ→Ａ→Ｃ→
Ｂ→Ｄ→Ｅを現在探索中の経路として、経路ａ→Ａ→Ｃ
→Ｂ→Ｄ→Ｅ→Ｃ、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ→ｂ、
経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ→Ｄの３本の経路が生成さ
れる。経路記憶では経路チェックにて経路ａ→Ａ→Ｃ→
Ｂ→Ｄ→Ｅ→ＣがノードＣを、経路ａ→Ａ→Ｃ→Ｂ→Ｄ
→Ｅ→ＤがノードＤをそれぞれ２度通っているのでＮＧ
となり、該経路の廃棄が行われる。経路数の確認で空き
があるため、該経路の記憶が実行され、経路ａ→Ａ→Ｃ
→Ｂ→Ｄ→Ｅ→ｂ（経路コスト＋最小予測コスト＝８）
が記憶される。

【００８４】ここで、記憶されている経路は経路ａ→Ａ
→Ｃ→Ｂ→ｃ（経路コスト＋最小予測コスト＝５）、経
路ａ→Ａ→Ｂ→ｃ（経路コスト＋最小予測コスト＝
６）、経路ａ→Ａ→Ｃ→Ｅ→ｂ（経路コスト＋最小予測
コスト＝７）、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ→ｂ（経路
コスト＋最小予測コスト＝８）である。経路選択では記
憶されている経路の中で到達ノードが中間ノードである
経路がないため、経路出力に進む。

【００８５】経路出力では憶されている経路ａ→Ａ→Ｃ
→Ｂ→ｃ、経路ａ→Ａ→Ｂ→ｃ、経路ａ→Ａ→Ｃ→Ｅ→
ｂ、経路ａ→Ａ→Ｃ→Ｂ→Ｄ→Ｅ→ｂの４本が出力され
る。このように動作することで、確かに、全ての出ノー
ドの中からコストの小さい順に、経路が指定した本数の
４本まで出力されている。

【００８６】

【発明の効果】以上説明したように本発明によれば、ネ
ットワークにおける最小コストの入ノードから出ノード
までの経路を探索する際に、予め中間ノードから前記出
ノードまでのコストを予測して求め、ノードから中間ノ
ードまでの途中経路に対して中間ノードに隣接するノー
ドまで経路を延長した経路を生成し、記憶する経路数を
制御しながら経路生成で生成された経路の中で記憶する
経路を取捨選択し、記憶された経路の中から最適な経路
を１つ選択し、記憶されている経路がない時に探索され
た経路を出力することによって、出ノード毎に最小コス
ト経路をコストの小さい順に任意の数だけ制限された記
憶量の中で求めることができ、高速に経路の探索を行う
ことができるという効果がある。

【図面の簡単な説明】

【図１】本発明の一実施例による最小コスト経路探索装
置の構成を示すブロック図である。

【図２】本発明の一実施例による最小コスト経路探索方
法の処理動作を示すフローチャートである。

【図３】図１の経路記憶部の動作を示すフローチャート
である。

【図４】本発明の一実施例で適用するトポロジの例を示
す図である。

【図５】図４に示すトポロジに対してダイクストラ法を
用いて算出した予測コストを示す図である。

【符号の説明】

１コスト予測部２経路生成部３経路記憶部４経路選択部５経路出力部６記憶部

Claims

【特許請求の範囲】

【請求項１】ネットワークにおける最小コストの入ノ
ードから出ノードまでの経路を探索する最小コスト経路
探索装置であって、予め中間ノードから前記出ノードま
でのコストを予測して求めるコスト予測手段と、前記入
ノードから前記中間ノードまでの途中経路に対して前記
中間ノードに隣接するノードまで経路を延長した経路を
生成する経路生成手段と、記憶する経路数を制御しなが
ら経路生成で生成された経路の中で記憶する経路を取捨
選択する経路記憶手段と、前記経路記憶手段で記憶され
た経路の中から最適な経路を１つ選択する経路選択手段
と、前記経路記憶手段に記憶されている経路がない時に
探索された経路を出力する経路出力手段とを有すること
を特徴とする最小コスト経路探索装置。
【請求項２】前記コスト予測手段は、外部から入力さ
れるコストを予測コストとするようにしたことを特徴と
する請求項１記載の最小コスト経路探索装置。
【請求項３】前記コスト予測手段は、数理計画上の手
法であるダイクストラ法によって最小コストを計算する
ようにしたことを特徴とする請求項１記載の最小コスト
経路探索装置。
【請求項４】前記コスト予測手段は、予め設定された
固定値を予測コストとするようにしたことを特徴とする
請求項１記載の最小コスト経路探索装置。
【請求項５】前記経路記憶手段は、前記ノード毎に前
記記憶する経路数を制限するようにしたことを特徴とす
る請求項１から請求項４のいずれか記載の最小コスト経
路探索装置。
【請求項６】前記経路記憶手段は、全てのノードに対
して前記記憶する経路数を制限するようにしたことを特
徴とする請求項１から請求項４のいずれか記載の最小コ
スト経路探索装置。
【請求項７】ネットワークにおける最小コストの入ノ
ードから出ノードまでの経路を探索する最小コスト経路
探索方法であって、予め中間ノードから前記出ノードま
でのコストを予測して求めるステップと、前記入ノード
から前記中間ノードまでの途中経路に対して前記中間ノ
ードに隣接するノードまで経路を延長した経路を生成す
るステップと、記憶する経路数を制御しながらその生成
された経路の中で記憶する経路を取捨選択するステップ
と、この記憶された経路の中から最適な経路を１つ選択
するステップと、記憶されている経路がない時に探索さ
れた経路を出力するステップとを有することを特徴とす
る最小コスト経路探索方法。
【請求項８】前記コストを予測して求めるステップ
は、外部から入力されるコストを予測コストとするよう
にしたことを特徴とする請求項７記載の最小コスト経路
探索方法。
【請求項９】前記コストを予測して求めるステップ
は、数理計画上の手法であるダイクストラ法によって最
小コストを計算するようにしたことを特徴とする請求項
７記載の最小コスト経路探索方法。
【請求項１０】前記コストを予測して求めるステップ
は、予め設定された固定値を予測コストとするようにし
たことを特徴とする請求項７記載の最小コスト経路探索
方法。
【請求項１１】前記経路を取捨選択するステップは、
前記ノード毎に前記記憶する経路数を制限するようにし
たことを特徴とする請求項７から請求項１０のいずれか
記載の最小コスト経路探索方法。
【請求項１２】前記経路を取捨選択するステップは、
全てのノードに対して前記記憶する経路数を制限するよ
うにしたことを特徴とする請求項７から請求項１０のい
ずれか記載の最小コスト経路探索方法。