(57)【特許請求の範囲】
【請求項１】
ネットワークのトポロジに対応した探索木において、始点ノードから終点ノードまでの経路の候補を探索する探索部と、
前記探索部によって探索された前記始点ノードから第ｎノード（ｎは自然数）までのホップ長と、前記第ｎノードから前記終点ノードまでの最短経路によるホップ長との加算値が、設定ホップ長を超える経路については、前記第ｎノードから前記終点ノードまでの経路を前記探索部による探索の候補から除外する制御部と、を備える、経路探索装置。
【請求項２】
前記経路の候補の探索は、前記加算値が前記設定ホップ長以下である経路について、前記第ｎノードから前記終点ノードへ向かう方向に接続された第ｎ＋１ノードが存在する場合に、前記始点ノードから前記第ｎ＋１ノードを経由する前記終点ノードまでの経路に対して行なわれる、請求項１に記載の経路探索装置。
【請求項３】
前記第ｎ＋１ノードが前記終点ノードである場合に、前記始点ノードから前記第ｎノードを経由する前記終点ノードまでの経路を、経路探索の結果として決定する決定部を備える、請求項２に記載の経路探索装置。
【請求項４】
前記経路を探索候補から除外する制御は、前記ホップ長とは異なる第１のコスト値について、前記始点ノードから前記第ｎノードまでの第１のコスト値と、前記第ｎノードから前記終点ノードまでの最短経路における第１のコスト値との第１の和が、第１の基準コスト値を超える経路に対して行なわれる、請求項２又は３に記載の経路探索装置。
【請求項５】
前記経路の候補の探索は、前記加算値が前記設定ホップ長以下であり、前記第１の和が前記第１の基準コスト値以下である場合に、前記始点ノードから前記第ｎ＋１ノードを経由する前記終点ノードまでの経路に対して行なわれる、請求項４に記載の経路探索装置。
【請求項６】
前記経路を探索候補から除外する制御は、前記第１の和が前記第１の基準コスト値と等しい場合に、前記ホップ長及び前記第１のコスト値とは異なる第２のコスト値について、前記始点ノードから前記第ｎノードまでの第２のコスト値と、前記第ｎノードから前記終点ノードまでの最短経路における第２のコスト値との第２の和が、第２の基準コスト値を超える経路に対して行なわれる、請求項４又は５に記載の経路探索装置。
【請求項７】
前記経路の候補の探索は、前記第１の和が前記第１の基準コスト値と等しく、前記第２の和が前記第２の基準コスト値以下である場合に、前記始点ノードから前記第ｎ＋１ノードを経由する前記終点ノードまでの経路に対して行なわれる、請求項６に記載の経路探索装置。
【請求項８】
前記経路の候補の探索が前記第ｎノードから前記第ｎ＋１ノードへ進むに応じて、前記始点ノードから前記第ｎノードまでの探索した経路を表示装置に表示させる表示処理部を備える、請求項２〜７のいずれか１項に記載の経路探索装置。
【請求項９】
前記表示処理部は、前記制御部によって前記経路の探索が前記探索部による探索の候補から除外されたことを示す情報を前記表示装置に表示させる、請求項８に記載の経路探索装置。
【請求項１０】
経路探索装置による経路探索方法であって、
ネットワークのトポロジに対応した探索木において、始点ノードから終点ノードまでの経路の候補を探索し、
前記探索された前記始点ノードから第ｎノード（ｎは自然数）までのホップ長と、前記第ｎノードから前記終点ノードまでの最短経路によるホップ長との加算値が、設定ホップ長を超える経路については、前記第ｎノードから前記終点ノードまでの経路を前記探索の候補から除外する、経路探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に記載する技術は、経路探索装置及び経路探索方法に関する。
【背景技術】
【０００２】
通信経路の設計及び設定を一元管理するネットワークシステムにおいて、オペレータからの経路構築（「経路探索」と称してもよい。）の要求に応じて、オペレータの要求品質を満たす始点ノードから終点ノードまでの通信経路を探索する技術がある。
【０００３】
ホップ長等の条件を満たす経路探索を実現する方法として、ダイクストラ法が知られている。ダイクストラ法は、リンク毎に定義されたメトリック値に対して、経路上のメトリック値の和が最小になる単一の経路を特定する。「メトリック値」は、「指標」や「コスト値」と称してもよい。
【０００４】
メトリック値は、例えば、経路長（「ホップ長」や「ホップ数」と称してもよい。）である。「ホップ長」とは、例えば、始点ノードから終点ノードに到達するまでに経由するノードの数である。
【０００５】
経路候補を抽出する方法としては、深さ優先探索法がある。「深さ優先探索法」は、開始ノードをルート（「根」と称してもよい。）とした探索木を生成し、設定されたホップ長（別言すれば、深さ）まで順次探索する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平７−１６２４１５号公報
【特許文献２】特開平６−９７９６４号公報
【特許文献３】特開２００８−５４２１１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述した「深さ優先探索法」を大規模なネットワークにおいて適用しようとすると、探索対象の経路数（別言すれば、探索空間）が膨大となり、計算時間が膨大になってしまう恐れがある。
【０００８】
１つの側面では、本明細書に記載する技術は、ある条件を満たすネットワークの経路の探索時間を短縮することを目的とする。
【課題を解決するための手段】
【０００９】
１つの側面において、経路探索装置は、探索部と制御部とを備える。探索部は、ネットワークのトポロジに対応した探索木において、始点ノードから終点ノードまでの経路の候補を探索する。制御部は、前記探索部によって探索された前記始点ノードから第ｎノード（ｎは自然数）までのホップ長と、前記第ｎノードから前記終点ノードまでの最短経路によるホップ長との加算値が、設定ホップ長を超える経路については、前記第ｎノードから前記終点ノードまでの経路を前記探索部による探索の候補から除外する。
【発明の効果】
【００１０】
１つの側面として、ある条件を満たすネットワークの経路の探索時間を短縮することができる。
【図面の簡単な説明】
【００１１】
【図１】第１実施形態の経路探索システムの機能的な構成例を示すブロック図である。
【図２】ネットワークのトポロジを例示する図である。
【図３】探索木による深さ優先探索法を説明する図である。
【図４】探索木による深さ優先探索法を説明するフローチャートである。
【図５】第１実施形態の経路探索装置における経路探索例を説明する図である。
【図６】探索木のノードについて説明する図である。
【図７】第１実施形態の経路探索装置における経路探索例を説明するフローチャートである。
【図８】第１実施形態における経路探索例の探索時間を比較例の探索時間と比較する図である。
【図９】第１実施形態における経路探索例の探索時間を比較例の探索時間と比較する図である。
【図１０】第２実施形態の経路探索装置における経路探索例を説明する図である。
【図１１】第２実施形態の経路探索装置における経路探索例を説明するフローチャートである。
【図１２】第２実施形態の経路探索装置における経路探索例を説明するフローチャートである。
【図１３】第３実施形態の経路探索装置における経路探索例を説明する図である。
【図１４】第３実施形態の経路探索装置における経路探索例を説明するフローチャートである。
【図１５】第３実施形態の経路探索装置における経路探索例を説明するフローチャートである。
【図１６】第４実施形態の経路探索装置における探索プロセスの画面表示例を説明する図である。
【図１７】第４実施形態の経路探索装置における探索プロセスの画面表示例を説明する図である。
【図１８】第４実施形態の経路探索装置における探索プロセスの画面表示例を説明する図である。
【図１９】第４実施形態の経路探索装置における探索プロセスの画面表示例を説明する図である。
【図２０】第４実施形態の経路探索装置における探索プロセスの画面表示例を説明するフローチャートである。
【発明を実施するための形態】
【００１２】
以下、図面を参照して実施の形態を説明する。ただし、以下に示す実施形態はあくまでも例示に過ぎず、実施形態で明示しない種々の変形例や技術の適用を排除する意図はない。すなわち、本実施形態は、その趣旨を逸脱しない範囲で種々変形して実施することができる。
【００１３】
また、各図は、図中に示す構成要素のみを備えるという趣旨ではなく、他の構成要素を含むことができる。以下、図中において、同一の符号を付した部分は特に断らない限り、同一若しくは同様の部分を示す。
【００１４】
〔Ａ〕第１実施形態
〔Ａ−１〕システム構成例
図１は、第１実施形態の経路探索システム１００の機能的な構成例を示すブロック図である。図２は、ネットワーク３のトポロジを例示する図である。
【００１５】
図１に示す経路探索システム１００は、例示的に、図２に例示するようなネットワーク３に備えられる始点ノードから終点ノードまでの１又は複数の経路を探索する。経路の探索は、経路探索システム１００に備えられる経路探索装置１によって実行されてよい。
【００１６】
図２に示すネットワーク３は、例示的に、１つの始点ノード（図２の“始”を参照）と１つの終点ノード（図２の“終”を参照）を備える。また、ネットワーク３は、始点ノードから終点ノードまでの経路において、複数の中間ノードを備えてよい。図２に示す例において、ネットワーク３は、５つの中間ノード＃１〜＃５（図２の“１”〜“５”を参照）を備えてよい。
【００１７】
以下、「始点ノード」と「終点ノード」と複数の「中間ノード」とをまとめて、単に「ノード」と称する場合がある。また、以下、「中間ノード＃１〜＃５」を単に「ノード＃１〜＃５」と称する場合がある。各ノードは、例示的に、互いに通信可能に接続される。中間ノードに付加される番号「＃１〜＃５」は、「ノードＩＤ（識別子）」と称してもよい。
【００１８】
ノードは、例示的に、通信装置や中継装置等の種々の装置である。
【００１９】
始点ノードは、例示的に、データを送信する際に、データの送信元となるノードである。終点ノードは、例示的に、始点ノードから送信されるデータの宛先となるノードである。中間ノードは、例示的に、始点ノードから終点ノードへ送信されるデータが経由するノードである。「データ」は、「信号」や「情報」と称してもよい。
【００２０】
なお、図２に示す始点ノード、終点ノード及び中間ノードは便宜的に定められたものであり、データの送信元と宛先とに応じて、いずれかのノードが始点ノード、終点ノード又は中間ノードと称されてよい。
【００２１】
経路探索システム１００は、図１に示すように、例示的に、経路探索装置１及びオペレータ端末２を備える。経路探索装置１とオペレータ端末２とは、通信可能に接続されてよい。
【００２２】
オペレータ端末２は、例示的に、入力装置２１及び表示装置２２を備える。
【００２３】
入力装置２１は、例えば、キーボードやマウス、トラックボールであってよい。オペレータは、入力装置２１を介して、オペレータ端末２に対する各種の入力操作を行なってよい。オペレータは、入力装置２１を介して、オペレータ端末２に対して、経路探索装置１に経路探索の要求をするための情報（以下、「経路探索要求」と称する場合がある。）を入力してよい。
【００２４】
経路探索要求は、例えば、ネットワーク３のトポロジに関する情報や探索条件、始点ノード及び終点ノードに関する情報、要求帯域を含んでよい。
【００２５】
ネットワーク３のトポロジに関する情報は、ネットワーク３に備える複数のノードに関する情報や各ノード間のリンクに関する情報を含んでよい。
【００２６】
探索条件は、始点ノードから終点ノードまでの経路におけるホップ長（別言すれば、経由するノードの数）の許容値であってよい。探索条件は、始点ノードから終点ノードまでの最短経路（別言すれば、最短ホップ長）に基づいて定められてよい。
【００２７】
始点ノード及び終点ノードに関する情報は、始点ノード及び終点ノードを特定するための情報であってよい。
【００２８】
要求帯域は、始点ノードから終点ノードまでの経路における通信速度（単位は例えばｂｐｓ）であってよい。
【００２９】
表示装置２２は、例えば、液晶ディスプレイやＣＲＴ（Cathode Ray Tube）、電子ペーパーディスプレイであってよい。表示装置２２は、オペレータ等に対する各種情報を表示してよい。表示装置２２は、経路探索要求に応じて経路探索装置１によって探索された１又は複数の経路候補を表示してよい。
【００３０】
なお、入力装置２１及び表示装置２２は組み合わされてもよく、例えば、タッチパネルでもよい。
【００３１】
経路探索装置１は、例えば、ソフトウェアによってネットワーク３を制御するＳＤＮ（Software Defined Networking）マネージャであってよい。経路探索装置１は、図１に示すように、ＣＰＵ（Central Processing Unit）１１、メモリ１２、及び、記憶装置１３を備えてよい。
【００３２】
記憶装置１３は、例示的に、データを読み書き可能に記憶する装置であり、例えば、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）が用いられてよい。記憶装置１３は、ネットワーク３の各ノード間の最短ホップ長に関する情報を記憶してよい。「最短ホップ長に関する情報」は、例示的に、ダイクストラ法を用いて、ネットワーク３の経路探索の開始に先立って生成されてよい。
【００３３】
メモリ１２は、例示的に、ＲＯＭ（Read Only Memory）及びＲＡＭ（Random Access Memory）を含む記憶装置である。メモリ１２のＲＯＭには、ＢＩＯＳ（Basic Input/Output System）等のプログラムが書き込まれてよい。メモリ１２のソフトウェアプログラムは、ＣＰＵ１１に適宜に読み込まれて実行されてよい。また、メモリ１２のＲＡＭは、一次記録メモリあるいはワーキングメモリとして利用されてよい。
【００３４】
ＣＰＵ１１は、例示的に、種々の制御や演算を行なう処理装置であり、メモリ１２に格納されたＯＳ（Operating System）やプログラムを実行することにより、種々の機能を実現する。すなわち、ＣＰＵ１１は、図１に示すように、探索部１１１、制御部１１２、決定部１１３、及び、表示処理部１１４として機能してよい。
【００３５】
なお、これらの探索部１１１、制御部１１２、決定部１１３、及び、表示処理部１１４としての機能を実現するためのプログラムは、例えばフレキシブルディスク、ＣＤ（ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷ等）、ＤＶＤ（ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＤＶＤ−Ｒ、ＤＶＤ＋Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ＋ＲＷ、ＨＤ  ＤＶＤ等）、ブルーレイディスク、磁気ディスク、光ディスク、光磁気ディスク等の、コンピュータ読取可能な記録媒体に記録された形態で提供されてよい。そして、コンピュータ（本実施形態ではＣＰＵ１１）は上述した記録媒体から図示しない読取装置を介してプログラムを読み取って内部記録装置または外部記録装置に転送し格納して用いてよい。また、プログラムを、例えば磁気ディスク，光ディスク，光磁気ディスク等の記憶装置（記録媒体）に記録しておき、記憶装置から通信経路を介してコンピュータに提供してもよい。
【００３６】
探索部１１１、制御部１１２、決定部１１３、及び、表示処理部１１４としての機能を実現する際には、内部記憶装置（本実施形態ではメモリ１２）に格納されたプログラムがコンピュータ（本実施形態ではＣＰＵ１１）によって実行されてよい。また、記録媒体に記録されたプログラムをコンピュータが読み取って実行してもよい。
【００３７】
ＣＰＵ１１は、例示的に、経路探索装置１全体の動作を制御する。経路探索装置１全体の動作を制御するための装置は、ＣＰＵ１１に限定されず、例えば、ＭＰＵ（Micro Processing Unit）やＤＳＰ（Digital Signal Processor），ＡＳＩＣ（Application Specific Integrated Circuit），ＰＬＤ（Programmable Logic Device），ＦＰＧＡ（Field Programmable Gate Array）のいずれか１つであってもよい。また、経路探索装置１全体の動作を制御するための装置は、ＣＰＵ，ＭＰＵ，ＤＳＰ，ＡＳＩＣ，ＰＬＤ及びＦＰＧＡのうちの２種類以上の組み合わせであってもよい。
【００３８】
なお、ＣＰＵ１１の探索部１１１、制御部１１２、決定部１１３、及び、表示処理部１１４としての機能については、図５〜図７の説明と併せて、後述する。
【００３９】
図３は、探索木による深さ優先探索法を説明する図である。図３においては、図２に示したネットワーク３における始点ノードから終点ノードまでの経路探索について、探索木による深さ優先探索法を用いて説明する。
【００４０】
探索木による深さ優先探索法を用いた経路探索は、図１に示した経路探索装置１によって行なわれてもよい。
【００４１】
最初に、オペレータによって、始点ノードから終点ノードまでの最短ホップ長に基づいた探索範囲が設定される（図３の符号Ａ１参照）。図２に示したネットワーク３において、始点ノードから終点ノードまでの最短ホップ長は、“３”である。そこで、オペレータは、例えば、最短ホップ長“３”にマージンとしてのホップ長“１”を加算した４ホップを、探索範囲として設定してよい。別言すれば、オペレータは、始点ノードから終点ノードまでのホップ長が４ホップ以下となる経路が探索されるように、設定を行なってよい。
【００４２】
次に、図２に示したネットワーク３のトポロジに対応した探索木が例えばメモリ１２において展開されてよい（図３の符号Ａ２参照）。探索木は、親ノード（別言すれば、「根ノード」）としての始点ノードを頂点として、葉ノードとしての始点ノード、終点ノード及び中間ノードを含んでよい。
【００４３】
なお、図３の符号Ａ２に示す探索木においては、深さが“３”の位置に存在するノードの一部と、深さが“４”の位置に存在するノードの図示を省略している。ここで、「深さ」は、探索木の頂点に位置する始点ノードの深さを“０”とした場合における、探索木の頂点に位置する始点ノードからのホップ長を示す。
【００４４】
深さ“４”まで探索木の探索が完了すると、探索結果が得られてよい（図３の符号Ａ３参照）。図３においては、４つの経路が探索結果として得られた例を示している。第１の経路は始点ノードから中間ノード＃１、＃２を経由して終点ノードに到達する経路であり、第２の経路は始点ノードから中間ノード＃３、＃１、＃２を経由して終点ノードに到達する経路である。また、第３の経路は始点ノードから中間ノード＃３、＃４、＃５を経由して終点ノードに到達する経路であり、第４の経路は始点ノードから中間ノード＃３、＃４、＃２を経由して終点ノードに到達する経路である。
【００４５】
次に、探索木による深さ優先探索法を用いた経路探索例を、図４に示すフローチャート（ステップＳ１〜Ｓ５）に従って説明する。
【００４６】
経路探索装置１は、オペレータ端末２から経路探索要求を受信する（ステップＳ１）。
【００４７】
経路探索装置１は、経路探索要求に基づき、ホップ長条件や始点ノード及び終点ノードに関する情報等の経路探索条件を設定する（ステップＳ２）。
【００４８】
経路探索装置１は、探索木による深さ優先探索法を用いて、設定されたホップ長条件によるホップ長の範囲において、始点ノードから終点ノードまでの経路候補を全パターン抽出する（ステップＳ３）。
【００４９】
経路探索装置１は、抽出した経路候補の中から、設定されたメトリック値が最良となる経路を１つ選択する（ステップＳ４）。
【００５０】
経路探索装置１は、選択した経路を用いてデータの伝送が行なわれるように、ネットワーク３を設定する（ステップＳ５）。
【００５１】
このように、探索木による深さ優先探索法を用いた経路探索においては、オペレータによって設定されたホップ長範囲を満たす全ての経路候補が抽出される。
【００５２】
しかしながら、深さ優先探索法を大規模なネットワークにおいて適用しようとすると、探索対象の経路数（別言すれば、探索空間）が膨大となり、計算時間が膨大になる可能性がある。
【００５３】
そこで、第１実施形態の経路探索装置１は、例示的に、始点ノードから終点ノードまでの全ての経路のうち、オペレータによって設定されたホップ長範囲を満たさないことが予測される経路の探索を途中で打ち切ってよい。「ホップ長範囲」は、「設定ホップ長」や「探索範囲」と称してもよい。
【００５４】
図１に示したＣＰＵ１１の探索部１１１は、例示的に、ネットワーク３のトポロジに対応した探索木において、始点ノードから終点ノードまでの経路の候補を探索する。探索部１１１は、深さ優先探索法を用いて、経路の候補を探索してよい。
【００５５】
探索部１１１は、ホップ長条件が満たされる経路について、ノードｎから終点ノードへ向かう方向に接続されたノードｎ＋１が存在する場合に、始点ノードからノードｎ＋１を経由する終点ノードまでの経路に対して、経路の候補を探索してもよい。
【００５６】
「ｎ」は、自然数であり、深さ優先探索法によって探索されたノードの順序を示す数である。つまり、ノードｎの次に探索されるノードはノードｎ＋１であり、自然数「ｎ」は１つのノードに対して複数回対応づけられてよい。
【００５７】
「ホップ長条件」の一例は、始点ノードからノードｎまでのホップ長と、ノードｎから終点ノードまでの最短ホップ長との加算値が、設定ホップ長以下であるという条件である。「ホップ長条件」が満たされるかの判定は、例示的に、制御部１１２によって行なわれてよい。
【００５８】
制御部１１２は、例示的に、始点ノードからノードｎまでのホップ長と、ノードｎから終点ノードまでの最短ホップ長との加算値が、設定ホップ長以下であるかを判定する。別言すれば、制御部１１２は、ホップ長条件が満たされるかを判定してよい。
【００５９】
制御部１１２は、ホップ長条件が満たされない経路については、ノードｎから終点ノードまでの経路を探索候補から除外してよい。
【００６０】
制御部１１２は、ノードｎについてホップ長条件が満たされない場合に、ノードｎの親ノードに接続され、経路候補の探索を未実施のノードについて、探索部１１１に経路探索をさせてよい。
【００６１】
決定部１１３は、例示的に、ノードｎ＋１が終点ノードである場合に、始点ノードからノードｎを経由する終点ノードまでの経路を、経路探索の結果として決定する。
【００６２】
表示処理部１１４は、例示的に、決定部１１３によって経路探索の結果として決定された経路を、オペレータ端末２が備える表示装置２２に表示させる。
【００６３】
〔Ａ−２〕動作例
図５は、第１実施形態の経路探索装置１における経路探索例を説明する図である。
【００６４】
最初に、始点ノードから終点ノードまでの最短ホップ長に基づいた探索範囲が、オペレータ端末２を介して経路探索装置１に設定されてよい（図５の符号Ｂ１参照）。図２に示したネットワーク３において、始点ノードから終点ノードまでの最短ホップ長は、“３”である。そこで、オペレータは、例えば、最短ホップ長“３”にマージンとしてのホップ長“１”を加算した４ホップを、探索範囲として設定してよい。別言すれば、オペレータは、始点ノードから終点ノードまでのホップ長が４ホップ以下となる経路が探索されるように、設定を行なってよい。
【００６５】
制御部１１２は、ノードｎにおいて、探索継続判定を行なってよい（図５の符号Ｂ２参照）。
【００６６】
制御部１１２は、探索継続判定の判定条件の一例であるｆ（始，ｎ）＋ｇ（ｎ，終）＞探索範囲が満たされる場合に、次ノードｎ＋１以降の探索を探索候補から除外してよい。別言すれば、探索部１１１は、ｆ（始，ｎ）＋ｇ（ｎ，終）＞探索範囲が満たされる場合に、次ノードｎ＋１の探索を行なわなくてよい。ｆ（始，ｎ）は、例示的に、始点ノードからノードｎまでにおいて探索済みの経路におけるホップ長（「探索ホップ長」と称してもよい。）を示す。また、ｇ（ｎ，終）は、例示的に、ノードｎから終点ノードまでの経路における最短ホップ長を示す。
【００６７】
探索部１１１は、探索継続判定の条件の一例であるｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされる場合に、次ノードｎ＋１以降の探索を継続して行なってよい。
【００６８】
探索部１１１は、探索継続判定の結果に従い、ネットワーク３のトポロジに対応した探索木において、始点ノードから終点ノードまでの経路の候補を探索してよい（図５の符号Ｂ３参照）。なお、図５においては、深さが“４”の位置に存在し、探索が行なわれたノードの図示を省略している。
【００６９】
図５において、「×」を示したノードは、次ノード以降の探索が行なわれないことを示す。例えば、始点ノードからノード＃１、＃３を経由する経路において、始点ノードからノード＃３までの探索ホップ長ｆ（始，３）＝２であり、ノード＃３から終点ノードまでの最短ホップ長ｇ（３，終）＝３である。よって、ｆ（始，３）＋ｇ（３，終）＝５となり、探索ホップ長と最短ホップ長との加算値は探索範囲を超える。そこで、ノード＃３の葉ノードに相当する各ノードの探索は、探索候補から除外される。
【００７０】
決定部１１３は、深さ“４”が以下の位置に存在する終点ノードまでの経路を、経路探索の結果として決定してよい（図５の符号Ｂ４参照）。
【００７１】
図５においては、４つの経路が探索結果として得られた例を示している。第１の経路は始点ノードから中間ノード＃１、＃２を経由して終点ノードに到達する経路であり、第２の経路は始点ノードから中間ノード＃３、＃１、＃２を経由して終点ノードに到達する経路である。また、第３の経路は始点ノードから中間ノード＃３、＃４、＃５を経由して終点ノードに到達する経路であり、第４の経路は始点ノードから中間ノード＃３、＃４、＃２を経由して終点ノードに到達する経路である。
【００７２】
表示処理部１１４は、決定部１１３によって決定された経路探索の結果を、オペレータ端末２の表示装置２２に表示させてよい。
【００７３】
次に、第１実施形態の経路探索装置における経路探索例について、図６において説明するノードの名称を用いて、図７に示すフローチャート（ステップＳ１１〜Ｓ２２）に従って説明する。
【００７４】
図６に例示するように、親ノードの配下（別言すれば、深さ方向）には、１又は複数の葉ノードが接続されてよい。葉ノードは、探索済みノードと選択ノードと未探索ノードとに分類されてよい。「探索済みノード」は、探索部１１１による経路探索が完了したノードである。「選択ノード」は、探索部１１１による経路探索が実行中のノードである。「未探索ノード」は、探索部１１１による経路探索が未だ行なわれていないノードである。
【００７５】
探索部１１１は、ネットワーク３の全区間（別言すれば、各ノード間）の最短ホップ長を算出する（図７のステップＳ１１）。算出された全区間の最短ホップ長は、例えば、記憶装置１３に格納されてよい。また、全区間の最短ホップ長の算出は、ネットワーク３の構成変更時等の、経路探索の開始前に、予め行なわれていてもよい。
【００７６】
探索部１１１は、オペレータ端末２を介したオペレータからの経路探索要求を受け付け、経路探索要求に基づいた経路探索条件を設定する（図７のステップＳ１２）。設定された経路探索条件に関する情報は、例えば、記憶装置１３に格納されてよい。経路探索条件に関する情報には、例示的に、探索範囲、始点ノードと終点ノードとに関する情報及びメトリック値が含まれてよい。
【００７７】
探索部１１１は、親ノードを選択ノードに設定する（図７のステップＳ１３）。
【００７８】
探索部１１１は、葉ノードに未探索ノードがあるかを判定する（図７のステップＳ１４）。
【００７９】
葉ノードに未探索ノードがある場合には（図７のステップＳ１４のＹｅｓルート参照）、探索部１１１は、未探索ノードであり、且つ、ノードＩＤが最も小さいノードを次の選択ノードに設定する（図７のステップＳ１５）。
【００８０】
決定部１１３は、現在の選択ノードが終点ノードであるかを判定する（図７のステップＳ１６）。
【００８１】
現在の選択ノードが終点ノードでない場合には（図７のステップＳ１６のＮｏルート参照）、制御部１１２は、探索継続判定の判定条件の一例であるｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされるかを判定する（図７のステップＳ１７）。
【００８２】
ｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされない場合には（図７のステップＳ１７のＮｏルート参照）、制御部１１２は、現在の選択ノードから終点ノードまでの経路を探索候補から除外する。探索部１１１は、現在の選択ノードを探索済みノードに設定し、選択ノードを親ノードに戻す（別言すれば、設定する）（図７のステップＳ１８）。そして、処理は、図７のステップＳ１３へ戻る。
【００８３】
一方、ｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされる場合には（図７のステップＳ１７のＹｅｓルート参照）、探索部１１１は、現在の選択ノードを親ノードに設定する（図７のステップＳ１９）。そして、処理は、図７のステップＳ１３へ戻る。
【００８４】
図７のステップＳ１６において、現在の選択ノードが終点ノードである場合には（図７のステップＳ１６のＹｅｓルート参照）、決定部１１３は、ネットワーク３の全ノードに対する探索が済んでいるかを判定する（図７のステップＳ２０）。
【００８５】
全ノードに対する探索が済んでいる場合には（図７のステップＳ２０のＹｅｓルート参照）、決定部１１３は、探索解（別言すれば、探索した経路）を、例えば記憶装置１３が記憶する情報に登録する（図７のステップＳ２１）。探索解が複数ある場合には、決定部１１３は、メトリック値が最良の探索解を、例えば記憶装置１３が記憶する情報に登録してよい。そして、処理は、終了する。
【００８６】
一方、全ノードに対する探索が済んでいない場合には（図７のステップＳ２０のＮｏルート参照）、探索部１１１は、選択ノードを親ノードに戻す（別言すれば、設定する）（図７のステップＳ２２）。そして、処理は、図７のステップＳ１３へ戻る。
【００８７】
図７のステップＳ１４において、葉ノードに未探索ノードがない場合には（図７のステップＳ１４のＮｏルート参照）、処理は図７のステップＳ２２へ移行する。
【００８８】
このように、第１実施形態において、探索部１１１は、ネットワーク３のトポロジに対応した探索木において、始点ノードから終点ノードまでの経路の候補を探索してよい。また、制御部１１２は、ホップ長条件を満たさない経路については、ノードｎから終点ノードまでの経路を探索候補から除外してよい。「ホップ長条件」の一例とは、始点ノードからノードｎまでのホップ長と、ノードｎから終点ノードまでの最短ホップ長との加算値が、設定ホップ長以下であるという条件である。
【００８９】
これにより、設定ホップ長を超える可能性がある経路の探索を途中で打ち切る（別言すれば、不要な探索を削減する）ことができ、ある条件を満たすネットワーク３の経路の探索時間を短縮することができる。また、ネットワーク３の構成の拡張及び／又は変更を行なうとノード間の経路が変更される可能性があるが、経路探索時間を短縮することができるため、ネットワーク３の構成の拡張及び／又は変更を容易にすることができる。
【００９０】
探索部１１１は、ホップ長条件を満たす経路について、ノードｎから終点ノードへ向かう方向に接続されたノードｎ＋１が存在する場合に、始点ノードからノードｎ＋１を経由する終点ノードまでの経路の候補を探索してよい。
【００９１】
これにより、設定ホップ長以下となる可能性がある経路の探索を適切に継続することができる。
【００９２】
決定部１１３は、ノードｎ＋１が終点ノードである場合に、始点ノードからノードｎを経由する終点ノードまでの経路を、経路探索の結果として決定する。
【００９３】
これにより、始点ノードから終点ノードまでのホップ長が設定ホップ長以下である適切な経路をネットワーク３内から抽出することができる。具体的には、条件を満たす適切な通信経路を高速に探索し、通信経路を抽出することができる。
【００９４】
探索部１１１は、探索木における深さ方向に接続されたノードｎ＋１を優先して経路の候補を探索する。
【００９５】
これにより、ネットワーク３内において始点ノードから終点ノードまでのホップ長が設定ホップ長以下となる経路を漏れなく探索することができ、経路探索装置１の信頼性を向上させることができる。
【００９６】
図８及び図９は、第１実施形態における経路探索例の探索時間を比較例の探索時間と比較する図である。
【００９７】
図８においては、５８３個のノードと７５４本のリンクとが備えられるネットワーク３において、最短ホップ長が３２ホップである始点ノードと終点ノードの組み合わせを３パターン選択し、各パターンの始点ノードから終点ノードまでの経路を探索する場合の探索時間［秒］が例示されている。また、図８においては、設定ホップ長として最短ホップ長又は最短ホップ長に１〜３ホップのいずれかを加算したホップ長が設定され、各設定ホップ長が設定された場合における経路を探索する例が示されている。
【００９８】
図８に例示するように、第１実施形態における経路探索例においては、比較例としての探索木の深さ優先探索法と比較して、１０−５〜１０−４程度の時間で各パターンの経路を探索することができる。
【００９９】
図９においては、１００００個のノードと９９９９本のリンクとが備えられるネットワーク３において、最短ホップ長が２５ホップである始点ノードと終点ノードの組み合わせを３パターン選択し、各パターンの始点ノードから終点ノードまでの経路を探索する場合の探索時間［秒］が例示されている。また、図９においては、設定ホップ長として最短ホップ長又は最短ホップ長に１〜３ホップのいずれかを加算したホップ長が設定され、各設定ホップ長が設定された場合における経路を探索する例が示されている。
【０１００】
図９に例示するように、比較例としての探索木の深さ優先探索法においては、数日計算しても計算が終わらない可能性がある。一方、第１実施形態における経路探索例において、設定ホップ長が最短ホップ長又は最短ホップ長に１ホップを加算したホップ長である場合には、１０秒未満で各パターンの経路を探索することができる。また、第１実施形態における経路探索例において、設定ホップ長が最短ホップ長に２又は３ホップを加算したホップ長である場合には、最大でも１９秒未満で各パターンの経路を探索することができる。
【０１０１】
〔Ｂ〕第２実施形態
〔Ｂ−１〕システム構成例
第２実施形態において、制御部１１２は、探索継続判定において、上述した第１実施形態における探索範囲の判定に加えて、メトリック値の判定を行なってよい。「メトリック値」は、「指標」や「コスト値」と称してもよい。
【０１０２】
メトリック値としては、上述したホップ長以外に、例えば、遅延時間やリンク負荷が挙げられる。「遅延時間」とは、例示的に、あるノードがデータを受信してから送信するまでにかかる時間である。また、「リンク負荷」とは、例示的に、あるリンクの伝送帯域においてデータの伝送が占める割合である。
【０１０３】
オペレータ端末２は、例示的に、オペレータからの入力に基づき、設定メトリック値（「設定コスト値」と称してもよい。）に関する情報を付加した経路探索要求を経路探索装置１へ送信する。設定メトリック値は、オペレータが所望するメトリックの許容値である。例えば、メトリック値として遅延時間が選択される場合には、設定メトリック値には、１０ｍｓ（ミリ秒）が設定される。また、例えば、メトリック値としてリンク負荷が選択される場合には、設定メトリック値には、４０％が設定される。
【０１０４】
制御部１１２は、例示的に、ホップ長とは異なるメトリック値について、始点ノードからノードｎまでのメトリック値と、ノードｎから終点ノードまでの最短経路におけるメトリック値との和が、基準メトリック値以下であるかを判定する。「基準メトリック値」は、「基準コスト値」と称してもよい。
【０１０５】
探索部１１１は、探索済みの１又は複数の経路において、最良（例えば、最小）のメトリック値を、基準メトリック値として設定してよい。また、探索部１１１は、設定メトリック値以下となる始点ノードから終点ノードまでの経路におけるメトリック値を、基準メトリック値の初期値として設定してよい。
【０１０６】
制御部１１２は、ホップ長条件が満たされる場合に、メトリック値の判定を行なってよい。「ホップ長条件」は、上述した第１実施形態と同様に、始点ノードからノードｎまでのホップ長と、ノードｎから終点ノードまでの最短ホップ長との加算値が、設定ホップ長以下であるという条件であってよい。
【０１０７】
制御部１１２は、メトリック値条件が満たされない場合に、ノードｎから終点ノードまでの経路を探索候補から除外してよい。「メトリック値条件」の一例は、始点ノードからノードｎまでのメトリック値と、ノードｎから終点ノードまでの最小のメトリック値との和が、基準メトリック値以下であるという条件である。
【０１０８】
探索部１１１は、ホップ長条件及びメトリック値条件が満たされ、ノードｎから終点ノードへ向かう方向に接続されたノードｎ＋１が存在する場合に、始点ノードからノードｎ＋１を経由する終点ノードまでの経路の候補を探索してよい。
【０１０９】
決定部１１３は、探索部１１１によって探索された始点ノードから終点ノードまでの１又は複数の経路のうち、メトリック値が最良の経路を、ネットワーク３に設定する経路として決定してよい。別言すれば、決定部１１３は、探索部１１１によって最後に探索された始点ノードから終点ノードまでの経路を、ネットワーク３に設定する経路として決定してよい。
【０１１０】
〔Ｂ−２〕動作例
図１０は、第２実施形態の経路探索装置１における経路探索例を説明する図である。
【０１１１】
制御部１１２は、ノードｎにおいて、探索継続判定を行なってよい（図１０の符号Ｃ１参照）。
【０１１２】
制御部１１２は、探索継続判定の条件の一例であるｆ（始，ｎ）＋ｇ（ｎ，終）＞探索範囲が満たされる場合に、次ノードｎ＋１以降の探索を探索候補から除外してよい。別言すれば、探索部１１１は、ｆ（始，ｎ）＋ｇ（ｎ，終）＞探索範囲が満たされる場合に、次ノードｎ＋１の探索を行なわなくてよい。
【０１１３】
制御部１１２は、探索継続判定の条件の一例であるｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされる場合に、メトリック値の判定を行なってよい。
【０１１４】
制御部１１２は、探索継続判定の条件の一例であるｍ（始，ｎ）＋ｐ（ｎ，終）＞基準メトリック値が満たされる場合に、次ノードｎ＋１以降の探索を探索候補から除外してよい。別言すれば、探索部１１１は、ｍ（始，ｎ）＋ｐ（ｎ，終）＞基準メトリック値が満たされる場合に、次ノードｎ＋１の探索を行なわないでよい。ｍ（始，ｎ）は、例示的に、始点ノードからノードｎまでにおいて探索済みの経路におけるメトリック値の和（「探索メトリック値」と称してもよい。）を示す。また、ｐ（ｎ，終）は、例示的に、ノードｎから終点ノードまでの最短経路におけるメトリック値の和を示す。
【０１１５】
また、制御部１１２は、探索継続判定の条件の別例であるＭａｘ（ｍ（始，ｎ），ｐ（ｎ，終））＞基準メトリック値が満たされる場合に、次ノードｎ＋１以降の探索を探索候補から除外してもよい。別言すれば、探索部１１１は、Ｍａｘ（ｍ（始，ｎ），ｐ（ｎ，終））＞基準メトリック値が満たされる場合に、次ノードｎ＋１の探索を行なわなくてよい。Ｍａｘ（ｍ（始，ｎ），ｐ（ｎ，終））は、例示的に、始点ノードからノードｎまでにおいて探索済みの経路における１又は複数のメトリック値と、ノードｎから終点ノードまでの経路における１又は複数のメトリック値とのうち、最大のメトリック値を示す。
【０１１６】
探索部１１１は、探索継続判定の条件の一例であるｍ（始，ｎ）＋ｐ（ｎ，終）≦探索範囲が満たされる場合に、次ノードｎ＋１以降の探索を継続してよい。
【０１１７】
また、探索部１１１は、探索継続判定の条件の別例であるＭａｘ（ｍ（始，ｎ），ｐ（ｎ，終））≦基準メトリック値が満たされる場合に、次ノードｎ＋１以降の探索を継続してもよい。
【０１１８】
探索部１１１は、探索継続判定の結果に従い、ネットワーク３のトポロジに対応した探索木において、始点ノードから終点ノードまでの経路の候補を探索してよい（図１０の符号Ｃ２参照）。なお、図１０においては、深さが“４”及び“５”の位置に存在し、探索が行なわれたノードの図示を省略している。
【０１１９】
図１０において、「×」を示したノードは、次ノード以降の探索が行なわれないことを示す。
【０１２０】
例えば、始点ノードからノード＃１、＃３を経由する経路において、始点ノードからノード＃３までの探索ホップ長ｆ（始，３）＝２であり、ノード＃３から終点ノードまでの最短ホップ長ｇ（３，終）＝３である。よって、ｆ（始，３）＋ｇ（３，終）＝５となり、探索ホップ長と最短ホップ長との加算値は探索範囲である５ホップ以内となる。
【０１２１】
しかしながら、始点ノードからノード＃３までの探索メトリック値ｍ（始，３）＝５ｍｓであり、ノード＃３から終点ノードまでの最短経路におけるメトリック値ｐ（３，終）＝７ｍｓとなる。よって、ｍ（始，３）＋ｐ（３，終）＝１２ｍｓとなり、探索メトリック値とノード＃３から終点ノードまでの最短経路におけるメトリック値との和は基準メトリック値である１０ｍｓを超える。
【０１２２】
そこで、ホップ長は探索範囲であるが、メトリック値が悪化するため、ノード＃３の葉ノードに相当する各ノードの探索は、探索候補から除外される。
【０１２３】
以下、第２実施形態の経路探索装置１における経路探索例を、図１１及び図１２に示すフローチャート（ステップＳ３１〜Ｓ４５）に従って説明する。なお、図１１に、ステップＳ３１〜３６及びＳ４２〜Ｓ４５の処理を示し、図１２に、ステップＳ３７〜Ｓ４１の処理を示す。
【０１２４】
探索部１１１は、ネットワーク３の全区間（別言すれば、各ノード間）の最短ホップ長を算出する（図１１のステップＳ３１）。算出された全区間の最短ホップ長は、例えば、記憶装置１３が記憶してよい。また、全区間の最短ホップ長の算出は、ネットワーク３の構成変更時等の、経路探索の開始前に、予め行なわれていてもよい。
【０１２５】
探索部１１１は、オペレータ端末２を介したオペレータからの経路探索要求を受け付け、経路探索要求に基づいた経路探索条件を設定する（図１１のステップＳ３２）。設定された経路探索条件に関する情報は、例えば、記憶装置１３が記憶してよい。経路探索条件に関する情報には、例示的に、探索範囲、始点ノードと終点ノードとに関する情報及びメトリック値が含まれてよい。
【０１２６】
探索部１１１は、始点ノードから終点ノードまでにおける最短経路のメトリック値を算出し、基準メトリック値に設定する（図１１のステップＳ３３）。設定された基準メトリック値は、例えば、記憶装置１３が記憶してよい。
【０１２７】
探索部１１１は、親ノードを選択ノードに設定する（図１１のステップＳ３４）。
【０１２８】
探索部１１１は、葉ノードに未探索ノードがあるかを判定する（図１１のステップＳ３５）。
【０１２９】
葉ノードに未探索ノードがある場合には（図１１のステップＳ３５のＹｅｓルート参照）、探索部１１１は、未探索ノードであり、且つ、ノードＩＤが最も小さいノードを次の選択ノードに設定する（図１１のステップＳ３６）。
【０１３０】
決定部１１３は、現在の選択ノードが終点ノードであるかを判定する（図１２のステップＳ３７）。
【０１３１】
現在の選択ノードが終点ノードでない場合には（図１２のステップＳ３７のＮｏルート参照）、制御部１１２は、ｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされるかを判定する（図１２のステップＳ３８）。
【０１３２】
ｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされない場合には（図１２のステップＳ３８のＮｏルート参照）、制御部１１２は、現在の選択ノードから終点ノードまでの経路を探索候補から除外する。探索部１１１は、現在の選択ノードを探索済みノードに設定し、選択ノードを親ノードに戻す（別言すれば、設定する）（図１２のステップＳ３９）。そして、処理は、図１１のステップＳ３４へ戻る。
【０１３３】
一方、ｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされる場合には（図１２のステップＳ３８のＹｅｓルート参照）、制御部１１２は、ｍ（始，ｎ）＋ｐ（ｎ，終）≦基準メトリック値が満たされるかを判定する（図１２のステップＳ４０）。
【０１３４】
ｍ（始，ｎ）＋ｐ（ｎ，終）≦基準メトリック値が満たされない場合には（図１２のステップＳ４０のＮｏルート参照）、処理は図１２のステップＳ３９へ移行する。
【０１３５】
一方、ｍ（始，ｎ）＋ｐ（ｎ，終）≦基準メトリック値が満たされる場合には（図１２のステップＳ４０のＹｅｓルート参照）、探索部１１１は、現在の選択ノードを親ノードに設定する（図１２のステップＳ４１）。そして、処理は、図１１のステップＳ３４へ戻る。
【０１３６】
図１２のステップＳ３７において、現在の選択ノードが終点ノードである場合には（図１２のステップＳ３７のＹｅｓルート参照）、決定部１１３は、ネットワーク３の全ノードに対する探索が済んでいるかを判定する（図１１のステップＳ４２）。
【０１３７】
全ノードに対する探索が済んでいる場合には（図１１のステップＳ４２のＹｅｓルート参照）、決定部１１３は、探索解（別言すれば、探索した経路）を、例えば記憶装置１３が記憶する情報に登録する（図１１のステップＳ４３）。探索解が複数ある場合には、決定部１１３は、メトリック値が最良の探索解を、例えば記憶装置１３が記憶する情報に登録してよい。そして、処理は、終了する。
【０１３８】
一方、全ノードに対する探索が済んでいない場合には（図１１のステップＳ４２のＮｏルート参照）、決定部１１３は、得られた経路に対してメトリック値を算出する。また、決定部１１３は、算出したメトリック値を基準メトリック値に設定する（図１１のステップＳ４４）。
【０１３９】
探索部１１１は、選択ノードを親ノードに戻す（別言すれば、設定する）（図１１のステップＳ４５）。そして、処理は、図１１のステップＳ３４へ戻る。
【０１４０】
図１１のステップＳ３５において、葉ノードに未探索ノードがない場合には（図１１のステップＳ３５のＮｏルート参照）、処理は図１１のステップＳ４５へ移行する。
【０１４１】
このように、第２実施形態において、制御部１１２は、ホップ長条件又はメトリック値条件が満たされない場合に、ノードｎから終点ノードまでの経路を探索候補から除外してよい。「ホップ長条件」の一例は、始点ノードからノードｎまでのホップ長と、ノードｎから終点ノードまでの最短ホップ長との加算値が、設定ホップ長以下であるという条件である。「メトリック値条件」の一例は、始点ノードからノードｎまでのメトリック値と、ノードｎから終点ノードまでの最短経路におけるメトリック値との和が、基準メトリック値以下であるという条件である。
【０１４２】
これにより、ホップ長に加えて、メトリック値を基準とした経路探索要求をオペレータが設定した場合においても、ある条件を満たすネットワーク３の経路の探索時間を短縮する時間を低減することができる。
【０１４３】
探索部１１１は、ホップ長条件及びメトリック値条件が満たされ、ノードｎから終点ノードへ向かう方向に接続されたノードｎ＋１が存在する場合に、始点ノードからノードｎ＋１を経由する終点ノードまでの経路の候補を探索してよい。
【０１４４】
これにより、ホップ長に加えて、メトリック値を基準とした経路探索要求をオペレータが設定した場合においても、経路の探索を適切に継続することができる。また、基準メトリック値と各経路のメトリック値とを比較しながら探索木の探索を行なうため、最後に探索した終点ノードを含む経路を最良の経路として容易に決定することができる。
【０１４５】
〔Ｃ〕第３実施形態
〔Ｃ−１〕システム構成例
第３実施形態において、制御部１１２は、探索継続判定において、上述した第１実施形態における探索範囲の判定に加えて、複数のメトリック値の判定を行なってよい。
【０１４６】
制御部１１２は、例示的に、ホップ長についてのホップ長条件と、第１のメトリック値についてのメトリック値条件とが満たされるかを判定する。
【０１４７】
「第１のメトリック値」は、「ホップ長」とは異なる指標である。「ホップ長条件」の一例は、始点ノードからノードｎまでのホップ長と、ノードｎから終点ノードまでの最短ホップ長との加算値が、設定ホップ長以下であるという条件である。「メトリック値条件」の一例は、始点ノードからノードｎまでの第１のメトリック値と、ノードｎから終点ノードまでの最短経路における第１のメトリック値との第１の和が、第１の基準メトリック値以下であるという条件である。
【０１４８】
また、制御部１１２は、例示的に、同値条件が満たされる場合に、始点ノードからノードｎまでの第２のメトリック値と、ノードｎから終点ノードまでの最短経路における第２のメトリック値との第２の和が、第２の基準メトリック値以下であるかを判定する。
【０１４９】
「第２のメトリック値」は、「ホップ長」及び「第１のメトリック値」とは異なる指標である。「同値条件」の一例は、第１の和が第１の基準メトリック値と等しいという条件である。
【０１５０】
制御部１１２は、第１の和が第１の基準メトリック値を超える場合、又は、第２の和が第２の基準メトリック値を超える場合に、ノードｎから終点ノードまでの経路を探索候補から除外してよい。第２のメトリック値についての判定は、第１のメトリック値についての判定がされた後に行なわれてよい。例示的に、第１のメトリック値についての判定は、第２のメトリック値についての判定よりも、優先度が高い。
【０１５１】
探索部１１１は、ホップ長条件が満たされ、第１の和が第１の基準メトリック値未満であり、ノードｎから終点ノードへ向かう方向に接続されたノードｎ＋１が存在する場合、始点ノードからノードｎ＋１を経由する終点ノードまでの経路候補を探索してよい。
【０１５２】
また、探索部１１１は、第２の和が第２の基準メトリック値以下であり、ノードｎから終点ノードへ向かう方向に接続されたノードｎ＋１が存在する場合に、始点ノードからノードｎ＋１を経由する終点ノードまでの経路の候補を探索してよい。
【０１５３】
〔Ｃ−２〕動作例
図１３は、第３実施形態の経路探索装置１における経路探索例を説明する図である。
【０１５４】
制御部１１２は、ノードｎにおいて、探索継続判定を行なってよい（図１３の符号Ｄ１参照）。
【０１５５】
制御部１１２は、探索継続判定の条件の一例であるｆ（始，ｎ）＋ｇ（ｎ，終）＞探索範囲が満たされる場合に、次ノードｎ＋１以降の探索を探索候補から除外する。別言すれば、探索部１１１は、ｆ（始，ｎ）＋ｇ（ｎ，終）＞探索範囲が満たされる場合に、次ノードｎ＋１の探索を行なわなくてよい。
【０１５６】
制御部１１２は、探索継続判定の条件の一例であるｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされる場合に、第１のメトリック値の判定を行なってよい。
【０１５７】
制御部１１２は、探索継続判定の条件の一例であるｍ１（始，ｎ）＋ｐ１（ｎ，終）＞第１の基準メトリック値が満たされる場合に、次ノードｎ＋１以降の探索を探索候補から除外してよい。別言すれば、探索部１１１は、ｍ１（始，ｎ）＋ｐ１（ｎ，終）＞第１の基準メトリック値が満たされる場合に、次ノードｎ＋１の探索を行なわなくてよい。ｍ１（始，ｎ）は、例示的に、始点ノードからノードｎまでにおいて探索済みの経路における第１のメトリック値の和（「第１の探索メトリック値」と称してもよい。）を示す。また、ｐ１（ｎ，終）は、例示的に、ノードｎから終点ノードまでの最短経路における第１のメトリック値の和を示す。
【０１５８】
探索部１１１は、探索継続判定の条件の一例であるｍ１（始，ｎ）＋ｐ１（ｎ，終）＜探索範囲が満たされる場合に、次ノードｎ＋１以降の探索を継続して行なってよい。
【０１５９】
制御部１１２は、探索継続判定の条件の一例であるｍ１（始，ｎ）＋ｐ１（ｎ，終）＝探索範囲が満たされる場合に、第２のメトリック値の判定を行なってよい。
【０１６０】
また、制御部１１２は、探索継続判定の条件の別例であるＭａｘ１（ｍ１（始，ｎ），ｐ１（ｎ，終））＞第１の基準メトリック値に基づいて、第１のメトリック値の判定を行なってもよい。Ｍａｘ１（ｍ１（始，ｎ），ｐ１（ｎ，終））は、例示的に、複数の第１のメトリック値のうち、最大の第１のメトリック値を示す。「複数の第１のメトリック値」の一例は、始点ノードからノードｎまでにおいて探索済みの経路における１又は複数の第１のメトリック値と、ノードｎから終点ノードまでの経路における１又は複数の第１のメトリック値とを含む。
【０１６１】
以下、第２〜第ｉ−１のメトリック値の判定は、第１のメトリック値の判定と同様に行なわれてよい。「ｉ」は、２以上の整数である。ただし、ｉ＝２のときは、第２〜第ｉ−１のメトリック値の判定は、行なわれなくてよい。
【０１６２】
制御部１１２は、探索継続判定の条件の一例であるｍｉ−１（始，ｎ）＋ｐｉ−１（ｎ，終）＝探索範囲が満たされる場合に、第ｉのメトリック値の判定を行なってよい。
【０１６３】
制御部１１２は、探索継続判定の条件の一例であるｍｉ（始，ｎ）＋ｐｉ（ｎ，終）＞第ｉの基準メトリック値が満たされる場合に、次ノードｎ＋１以降の探索を探索候補から除外してよい。別言すれば、探索部１１１は、ｍｉ（始，ｎ）＋ｐｉ（ｎ，終）＞第ｉの基準メトリック値が満たされる場合に、次ノードｎ＋１の探索を行なわなくてよい。ｍｉ（始，ｎ）は、例示的に、始点ノードからノードｎまでにおいて探索済みの経路における第ｉのメトリック値の和（「第ｉの探索メトリック値」と称してもよい。）を示す。また、ｐｉ（ｎ，終）は、例示的に、ノードｎから終点ノードまでの最短経路における第ｉのメトリック値の和を示す。
【０１６４】
探索部１１１は、探索継続判定の条件の一例であるｍｉ（始，ｎ）＋ｐｉ（ｎ，終）＜探索範囲が満たされる場合に、次ノードｎ＋１以降の探索を継続してよい。
【０１６５】
探索部１１１は、探索継続判定の結果に従い、ネットワーク３のトポロジに対応した探索木において、始点ノードから終点ノードまでの経路の候補を探索してよい（図１３の符号Ｄ２参照）。なお、図１３においては、深さが“４”及び“５”の位置に存在し、探索が行なわれたノードの図示を省略している。
【０１６６】
図１３において、「×」を示したノードは、次ノード以降の探索が行なわれないことを示す。
【０１６７】
例えば、始点ノードからノード＃１，＃３を経由する経路において、始点ノードからノード＃３までの探索ホップ長ｆ（始，３）＝２であり、ノード＃３から終点ノードまでの最短ホップ長ｇ（３，終）＝３である。よって、ｆ（始，３）＋ｇ（３，終）＝５となり、探索ホップ長と最短ホップ長との加算値は探索範囲である５ホップ以内となる。
【０１６８】
また、始点ノードからノード＃３までの第１の探索メトリック値ｍ１（始，３）＝１ｍｓであり、ノード＃３から終点ノードまでの最短経路における第１のメトリック値ｐ１（３，終）＝２ｍｓとなる。よって、ｍ１（始，３）＋ｐ１（３，終）＝３ｍｓとなり、第１の探索メトリック値とノード＃３から終点ノードまでの最短経路における第１のメトリック値との和は第１の基準メトリック値である１０ｍｓを超える。
【０１６９】
しかしながら、始点ノードからノード＃３までの探索済みの経路における第２のメトリック値の最大値はｍ２（始，３）＝５０％であり、ノード＃３から終点ノードまでの最短経路における第２のメトリック値の最大値はｐ２（３，終）＝２０％である。よって、ｍａｘ（ｍ１（始，３），ｐ１（３，終））＝５０％となり、始点ノードからノード＃３を経由する終点ノードまでの経路の第２のメトリック値の最大値は第２の基準メトリック値である４０％を超える。
【０１７０】
ホップ長及び第１のメトリック値の経路探索要求は満たされるが、第２のメトリック値が悪化するため、ノード＃３の葉ノードに相当する各ノードの探索は、探索候補から除外される。
【０１７１】
次に、第３実施形態の経路探索装置における経路探索例を、図１４及び図１５に示すフローチャート（ステップＳ５１〜Ｓ６６）に従って説明する。なお、図１４に、ステップＳ５１〜Ｓ５６及びＳ６３〜Ｓ６６の処理を示し、図１５に、ステップＳ５７〜Ｓ６２の処理を示す。
【０１７２】
探索部１１１は、ネットワーク３の全区間（別言すれば、各ノード間）の最短ホップ長を算出する（図１４のステップＳ５１）。算出された全区間の最短ホップ長は、例えば、記憶装置１３に格納されてよい。また、全区間の最短ホップ長の算出は、ネットワーク３の構成変更時等の、経路探索の開始前に、予め行なわれていてもよい。
【０１７３】
探索部１１１は、オペレータ端末２を介したオペレータからの経路探索要求を受け付け、経路探索要求に基づいた経路探索条件を設定する（図１４のステップＳ５２）。設定された経路探索条件に関する情報は、例えば、記憶装置１３に格納されてよい。経路探索条件に関する情報には、例示的に、探索範囲、始点ノードと終点ノードとに関する情報及び優先度が付加された複数のメトリック値が含まれてよい。
【０１７４】
探索部１１１は、始点ノードから終点ノードまでにおける最短経路の第１〜第ｉのメトリック値を算出し、算出した第１〜第ｉのメトリック値を第１〜第ｉの基準メトリック値にそれぞれ設定する（図１４のステップＳ５３）。設定された基準値は、例えば、記憶装置１３が記憶してよい。
【０１７５】
探索部１１１は、親ノードを選択ノードに設定する（図１４のステップＳ５４）。
【０１７６】
探索部１１１は、葉ノードに未探索ノードがあるかを判定する（図１４のステップＳ５５）。
【０１７７】
葉ノードに未探索ノードがある場合には（図１４のステップＳ５５のＹｅｓルート参照）、探索部１１１は、未探索ノードであり、且つ、ノードＩＤが最も小さいノードを次の選択ノードに設定する（図１４のステップＳ５６）。
【０１７８】
決定部１１３は、現在の選択ノードが終点ノードであるかを判定する（図１５のステップＳ５７）。
【０１７９】
現在の選択ノードが終点ノードでない場合には（図１５のステップＳ５７のＮｏルート参照）、制御部１１２は、ｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされるかを判定する（図１５のステップＳ５８）。
【０１８０】
ｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされない場合には（図１５のステップＳ５８のＮｏルート参照）、制御部１１２は、現在の選択ノードから終点ノードまでの経路を探索候補から除外する。探索部１１１は、現在の選択ノードを探索済みノードに設定し、選択ノードを親ノードに戻す（別言すれば、設定する）（図１５のステップＳ５９）。そして、処理は、図１４のステップＳ５４へ戻る。
【０１８１】
一方、ｆ（始，ｎ）＋ｇ（ｎ，終）≦探索範囲が満たされる場合には（図１５のステップＳ５８のＹｅｓルート参照）、制御部１１２は、ｍ１（始，ｎ）＋ｐ１（ｎ，終）≦第１の基準メトリック値が満たされるかを判定する（図１５のステップＳ６０）。
【０１８２】
ｍ１（始，ｎ）＋ｐ１（ｎ，終）≦第１の基準メトリック値が満たされない場合には（図１５のステップＳ６０のＮｏルート参照）、処理は図１５のステップＳ５９へ移行する。
【０１８３】
一方、ｍ１（始，ｎ）＋ｐ１（ｎ，終）≦第１の基準メトリック値が満たされる場合には（図１５のステップＳ６０のＹｅｓルート参照）、制御部１１２は、ｍ２（始，ｎ）＋ｐ２（ｎ，終）≦第２の基準メトリック値が満たされるかを判定する。
【０１８４】
なお、図１５のステップＳ６０において、制御部１１２は、ｍ１（始，ｎ）＋ｐ１（ｎ，終）＝第１の基準メトリック値が満たされる場合に、ｍ２（始，ｎ）＋ｐ２（ｎ，終）≦第２の基準メトリック値が満たされるかを判定してもよい。また、ｍ１（始，ｎ）＋ｐ１（ｎ，終）＜第１の基準メトリック値が満たされる場合には、処理は図１５のステップＳ６２へ移行してもよい。
【０１８５】
そして、制御部１１２は、第１の基準メトリック値についての探索継続判定と同様に、第２〜第ｉ−１の基準メトリック値についての探索継続判定を行なう。
【０１８６】
ｍｉ−１（始，ｎ）＋ｐｉ−１（ｎ，終）≦第ｉ−１の基準メトリック値が満たされる場合には、制御部１１２は、ｍｉ（始，ｎ）＋ｐｉ（ｎ，終）≦第ｉの基準メトリック値が満たされるかを判定する（図１５のステップＳ６１）。
【０１８７】
なお、制御部１１２は、ｍｉ−１（始，ｎ）＋ｐｉ−１（ｎ，終）＝第ｉ−１の基準メトリック値が満たされる場合に、ｍｉ（始，ｎ）＋ｐｉ（ｎ，終）≦第ｉの基準メトリック値が満たされるかを判定してもよい。また、ｍｉ−１（始，ｎ）＋ｐｉ−１（ｎ，終）＜第ｉ−１の基準メトリック値が満たされる場合には、処理は図１５のステップＳ６２へ移行してもよい。
【０１８８】
ｍｉ（始，ｎ）＋ｐｉ（ｎ，終）≦第ｉの基準メトリック値が満たされない場合には（図１５のステップＳ６１のＮｏルート参照）、処理は図１５のステップＳ５９へ移行する。
【０１８９】
一方、ｍｉ（始，ｎ）＋ｐｉ（ｎ，終）≦第ｉの基準メトリック値が満たされる場合には（図１５のステップＳ６１のＹｅｓルート参照）、探索部１１１は、現在の選択ノードを親ノードに設定する（図１５のステップＳ６２）。そして、処理は、図１４のステップＳ５４へ戻る。
【０１９０】
図１５のステップＳ５７において、現在の選択ノードが終点ノードである場合には（図１５のステップＳ５７のＹｅｓルート参照）、決定部１１３は、ネットワーク３の全ノードに対する探索が済んでいるかを判定する（図１４のステップＳ６３）。
【０１９１】
全ノードに対する探索が済んでいる場合には（図１４のステップＳ６３のＹｅｓルート参照）、決定部１１３は、探索解（別言すれば、最後に探索した経路）を、例えば記憶装置１３が記憶する情報に登録する（図１４のステップＳ６４）。そして、処理は、終了する。
【０１９２】
一方、全ノードに対する探索が済んでいない場合には（図１４のステップＳ６３のＮｏルート参照）、決定部１１３は、得られた経路に対して第１〜第ｉのメトリック値を算出する。また、決定部１１３は、算出した第１〜第ｉのメトリック値を第１〜第ｉの基準メトリック値にそれぞれ設定する（図１４のステップＳ６５）。
【０１９３】
探索部１１１は、選択ノードを親ノードに戻す（別言すれば、設定する）（図１４のステップＳ６６）。そして、処理は、図１４のステップＳ５４へ戻る。
【０１９４】
図１４のステップＳ５５において、葉ノードに未探索ノードがない場合には（図１４のステップＳ５５のＮｏルート参照）、処理は図１４のステップＳ６６へ移行する。
【０１９５】
このように、第３実施形態において、制御部１１２は、同値条件が満たされる場合に、第２の和が第２の基準メトリック値を超えるかを判定してよい。「同値条件」の一例は、始点ノードからノードｎまでの第１のメトリック値と、ノードｎから終点ノードまでの最短経路における第１のメトリック値との第１の和が、第１の基準メトリック値と等しいという条件である。「第２の和」の一例は、始点ノードからノードｎまでの第２のメトリック値と、ノードｎから終点ノードまでの最短経路における第２のメトリック値との和である。
【０１９６】
これにより、上述した第１及び第２実施形態と同様の効果を奏することができるとともに、例えば、以下の効果を奏することができる。
【０１９７】
ホップ長に加えて、複数のメトリック値を基準とした経路探索要求をオペレータが設定した場合においても、ある条件を満たすネットワーク３の経路の探索時間を短縮することができる。
【０１９８】
探索部１１１は、同値条件が満たされ、第２の和が第２の基準コスト値以下である場合に、始点ノードから第ｎ＋１ノードを経由する終点ノードまでの経路の候補を探索する。
【０１９９】
これにより、ホップ長に加えて、複数のメトリック値を基準とした経路探索要求をオペレータが設定した場合においても、経路の探索を適切に継続することができる。
【０２００】
〔Ｄ〕第４実施形態
〔Ｄ−１〕システム構成例
第４実施形態において、表示処理部１１４（図１を参照）は、探索部１１１による経路の候補の探索がノードｎからノードｎ＋１へ進むに応じて、始点ノードからノードｎまでの探索した経路をオペレータ端末２が備える表示装置２２に表示させてよい。また、表示処理部１１４は、経路の探索が探索候補から制御部１１２によって除外されたことを示す情報を表示装置２２に表示させてよい。
【０２０１】
〔Ｄ−２〕動作例
図１６〜図１９は、第４実施形態の経路探索装置における探索プロセスの画面表示例を説明する図である。
【０２０２】
図１６〜図１９に示す「探索プロセス」及び「現時点で導出された経路」は、オペレータ端末２が備える表示装置２２に表示されてよい。図１６〜図１９において、「探索プロセス」に表示される探索木において破線で示すノードのオブジェクトは、最後に表示されたノードのオブジェクトであることを示す。
【０２０３】
表示処理部１１４は、探索木の深さ“０”における始点ノードが探索されると、始点ノードを示すオブジェクトを表示装置２２に表示させてよい（図１６の符号Ｅ１参照）。
【０２０４】
表示処理部１１４は、探索木の深さ“１”におけるノード＃１が探索されると、ノード＃１を示すオブジェクトを、始点ノードの葉ノードに設定し、深さ“１”の位置に表示装置２２に表示させてよい（図１６の符号Ｅ２参照）。
【０２０５】
表示処理部１１４は、探索木の深さ“２”における始点ノード及びノード＃３、＃２が探索されると、始点ノード及びノード＃３、＃２を示すオブジェクトを、ノード＃１の葉ノードに設定し、表示装置２２に表示させてよい（図１６の符号Ｅ３参照）。
【０２０６】
また、表示処理部１１４は、深さ“３”における始点ノード及びノード＃３以降の経路が探索候補から除外されると、始点ノード及びノード＃３のオブジェクト上に探索候補から除外されたことを示す「×」を表示装置２２に表示させてよい（図１６の符号Ｅ３参照）。
【０２０７】
表示処理部１１４は、探索木の深さ“３”におけるノード＃１，＃４及び終点ノードが探索されると、ノード＃１、＃４及び終点ノードを示すオブジェクトを、ノード＃２の葉ノードに設定し、表示装置２２に表示させてよい（図１７の符号Ｅ４参照）。
【０２０８】
また、表示処理部１１４は、深さ“３”におけるノード＃１、＃４以降の経路が探索候補から除外されると、ノード＃１、＃４のオブジェクト上に探索候補から除外されたことを示す「×」を表示装置２２に表示させてよい（図１７の符号Ｅ４参照）。
【０２０９】
更に、表示処理部１１４は、始点ノードから終点ノードまでの経路が導出されると、導出された経路を「現時点で導出された経路」として表示装置２２に表示させてよい（図１７の符号Ｅ４参照）。表示処理部１１４は、導出された経路における１又複数のメトリック値を表示装置２２に表示させてもよい。
【０２１０】
図１７の符号Ｅ４においては、始点ノードからノード＃１、＃２を介して終点ノードに到達する経路が導出され、導出された経路の第１及び第２のメトリック値がそれぞれ５０ｍｓ及び１０％であることを示している。
【０２１１】
表示処理部１１４は、探索木の深さ“１”におけるノード＃３が探索されると、ノード＃３を示すオブジェクトを、始点ノードの葉ノードに設定し、表示装置２２に表示させてよい（図１７の符号Ｅ５参照）。
【０２１２】
表示処理部１１４は、探索木の深さ“２”におけるノード＃１が探索されると、ノード＃１を示すオブジェクトを、ノード＃３の葉ノードに設定し、表示装置２２に表示させてよい（図１８の符号Ｅ６参照）。
【０２１３】
表示処理部１１４は、探索木の深さ“３”におけるノード＃２が探索されると、ノード＃２を示すオブジェクトを、ノード＃１の葉ノードに設定し、表示装置２２に表示させてよい（図１８の符号Ｅ７参照）。
【０２１４】
表示処理部１１４は、探索木の深さ“４”における終点ノードが探索されると、終点ノードを示すオブジェクトを、ノード＃２の葉ノードに設定し、表示装置２２に表示させてよい（図１９の符号Ｅ８参照）。
【０２１５】
また、表示処理部１１４は、始点ノードから終点ノードまでの経路が導出されると、導出された経路を「現時点で導出された経路」として表示装置２２に表示させてよい（図１９の符号Ｅ８参照）。表示処理部１１４は、導出された経路における１又複数のメトリック値を表示装置２２に表示させてもよい。
【０２１６】
図１９の符号Ｅ８においては、始点ノードからノード＃３、＃１、＃２を介して終点ノードに到達する経路が導出され、導出された経路の第１及び第２のメトリック値がそれぞれ１５０ｍｓ及び５％であることを示している。
【０２１７】
以降、表示装置２２は、探索木における新たなノードが探索されるに応じて、表示装置２２に表示させる「探索プロセス」及び／又は「現時点で導出された経路」を更新する。別言すれば、表示処理部１１４は、探索木における新たなノードが探索されるに応じて、表示装置２２の表示状態を段階的に制御する。
【０２１８】
次に、第４実施形態の経路探索装置１における探索プロセスの画面表示例を、図２０に示すフローチャート（ステップＳ７１〜Ｓ７５）に従って説明する。
【０２１９】
経路探索装置１は、オペレータ端末２から経路探索要求を受信する（図２０のステップＳ７１）。
【０２２０】
探索部１１１は、受信した経路探索要求に基づき、設計条件を設定する（図２０のステップＳ７２）。設定した設計条件に関する情報は、記憶装置１３が記憶してもよい。
【０２２１】
表示処理部１１４は、探索木の探索過程で得られる経路解とホップ長とメトリック値とを表示装置２２に表示させることにより、例えばオペレータに対して可視化する（図２０のステップＳ７３）。
【０２２２】
決定部１１３は、探索部１１１による探索木の探索が終了したかを判定する（図２０のステップＳ７４）。
【０２２３】
探索木の探索が終了していない場合には（図２０のステップＳ７４のＮｏルート参照）、処理は図２０のステップＳ７３へ戻る。
【０２２４】
一方、探索木の探索が終了した場合には（図２０のステップＳ７４のＹｅｓルート参照）、決定部１１３は、選択経路をネットワーク３に設定する（図２０のステップＳ７５）。そして、処理は、終了してよい。
【０２２５】
このように、第４実施形態において、表示処理部１１４は、経路の候補の探索がノードｎからノードｎ＋１へ進むに応じて、始点ノードからノードｎまでの探索した経路を表示装置２２に表示させる。また、表示処理部１１４は、制御部１１２によって経路の探索が探索候補から除外されたことを示す情報を表示装置２２に表示させる。
【０２２６】
以上により、オペレータは、表示装置２２を介して、経路探索例の進捗状態を把握することができる。
【０２２７】
〔Ｅ〕その他
開示の技術は上述した各実施形態に限定されるものではなく、各実施形態の趣旨を逸脱しない範囲で種々変形して実施することができる。各実施形態の各構成及び各処理は、必要に応じて取捨選択することができ、あるいは適宜組み合わせてもよい。例えば、上述した第４実施形態は、第１実施形態、第２実施形態、又は第３実施形態と組み合わされてよい。
【０２２８】
上述した各実施形態において、経路探索装置１が備えるＣＰＵ１１は、表示処理部１１４としての機能を備えることとしたが、これに限定されるものではない。表示処理部１１４としての機能は、例示的に、経路探索システム１００において経路探索装置１とは別の表示制御装置（不図示）に備えられてよい。これにより、上述した各実施形態と同様の効果を奏することができる。
【０２２９】
〔Ｆ〕付記
（付記１）
ネットワークのトポロジに対応した探索木において、始点ノードから終点ノードまでの経路の候補を探索する探索部と、
前記始点ノードから第ｎノード（ｎは自然数）までのホップ長と、前記第ｎノードから前記終点ノードまでの最短ホップ長との加算値が、設定ホップ長を超える経路については、前記第ｎノードから前記終点ノードまでの経路を探索候補から除外する制御部と、を備える、経路探索装置。
【０２３０】
（付記２）
前記経路の候補の探索は、前記加算値が前記設定ホップ長以下である経路について、前記第ｎノードから前記終点ノードへ向かう方向に接続された第ｎ＋１ノードが存在する場合に、前記始点ノードから前記第ｎ＋１ノードを経由する前記終点ノードまでの経路に対して行なわれる、付記１に記載の経路探索装置。
【０２３１】
（付記３）
前記第ｎ＋１ノードが前記終点ノードである場合に、前記始点ノードから前記第ｎノードを経由する前記終点ノードまでの経路を、経路探索の結果として決定する決定部を備える、付記２に記載の経路探索装置。
【０２３２】
（付記４）
前記経路を探索候補から除外する制御は、前記ホップ長とは異なる第１のコスト値について、前記始点ノードから前記第ｎノードまでの第１のコスト値と、前記第ｎノードから前記終点ノードまでの最短経路における第１のコスト値との第１の和が、第１の設定コスト値を超える経路に対して行なわれる、付記２又は３に記載の経路探索装置。
【０２３３】
（付記５）
前記経路の候補の探索は、前記加算値が前記設定ホップ長以下であり、前記第１の和が前記第１の基準コスト値以下である場合に、前記始点ノードから前記第ｎ＋１ノードを経由する前記終点ノードまでの経路に対して行なわれる、付記４に記載の経路探索装置。
【０２３４】
（付記６）
前記経路を探索候補から除外する制御は、前記第１の和が前記第１の基準コスト値と等しい場合に、前記ホップ長及び前記第１のコスト値とは異なる第２のコスト値について、前記始点ノードから前記第ｎノードまでの第２のコスト値と、前記第ｎノードから前記終点ノードまでの最短経路における第２のコスト値との第２の和が、第２の基準コスト値を超える経路に対して行なわれる、付記４又は５に記載の経路探索装置。
【０２３５】
（付記７）
前記経路の候補の探索は、前記第１の和が前記第１の基準コスト値と等しく、前記第２の和が前記第２の基準コスト値以下である場合に、前記始点ノードから前記第ｎ＋１ノードを経由する前記終点ノードまでの経路に対して行なわれる、付記６に記載の経路探索装置。
【０２３６】
（付記８）
前記経路の候補の探索が前記第ｎノードから前記第ｎ＋１ノードへ進むに応じて、前記始点ノードから前記第ｎノードまでの探索した経路を表示装置に表示させる表示処理部を備える、付記２〜７のいずれか１項に記載の経路探索装置。
【０２３７】
（付記９）
前記表示処理部は、前記制御部によって前記経路の探索が前記探索候補から除外されたことを示す情報を前記表示装置に表示させる、付記８に記載の経路探索装置。
【０２３８】
（付記１０）
前記経路の候補の探索は、探索木における深さ方向に接続された前記第ｎ＋１ノードを優先して行なわれる、付記２〜９のいずれか１項に記載の経路探索装置。
【０２３９】
（付記１１）
経路探索装置による経路探索方法であって、
ネットワークのトポロジに対応した探索木において、始点ノードから終点ノードまでの経路の候補を探索し、
前記始点ノードから第ｎノード（ｎは自然数）までのホップ長と、前記第ｎノードから前記終点ノードまでの最短ホップ長との加算値が、設定ホップ長を超える経路については、前記第ｎノードから前記終点ノードまでの経路を探索候補から除外する、経路探索方法。
【０２４０】
（付記１２）
前記経路の候補の探索は、前記加算値が前記設定ホップ長以下である経路について、前記第ｎノードから前記終点ノードへ向かう方向に接続された第ｎ＋１ノードが存在する場合に、前記始点ノードから前記第ｎ＋１ノードを経由する前記終点ノードまでの経路に対して行なわれる、付記１１に記載の経路探索方法。
【０２４１】
（付記１３）
前記第ｎ＋１ノードが前記終点ノードである場合に、前記始点ノードから前記第ｎノードを経由する前記終点ノードまでの経路を、経路探索の結果として決定する、付記１２に記載の経路探索方法。
【０２４２】
（付記１４）
前記経路を探索候補から除外する制御は、前記ホップ長とは異なる第１のコスト値について、前記始点ノードから前記第ｎノードまでの第１のコスト値と、前記第ｎノードから前記終点ノードまでの最短経路における第１のコスト値との第１の和が、第１の基準コスト値を超える経路に対して行なわれる、付記１２又は１３に記載の経路探索方法。
【０２４３】
（付記１５）
前記経路の候補の探索は、前記加算値が前記設定ホップ長以下であり、前記第１の和が前記第１の基準コスト値以下である場合に、前記始点ノードから前記第ｎ＋１ノードを経由する前記終点ノードまでの経路に対して行なわれる、付記１４に記載の経路探索方法。
【０２４４】
（付記１６）
前記経路を探索候補から除外する制御は、前記第１の和が前記第１の基準コスト値と等しい場合に、前記ホップ長及び前記第１のコスト値とは異なる第２のコスト値について、前記始点ノードから前記第ｎノードまでの第２のコスト値と、前記第ｎノードから前記終点ノードまでの最短経路における第２のコスト値との第２の和が、第２の基準コスト値を超える経路に対して行なわれる、付記１４又は１５に記載の経路探索方法。
【０２４５】
（付記１７）
前記経路の候補の探索は、前記第１の和が前記第１の基準コスト値と等しく、前記第２の和が前記第２の基準コスト値以下である場合に、前記始点ノードから前記第ｎ＋１ノードを経由する前記終点ノードまでの経路に対して行なわれる、付記１６に記載の経路探索方法。
【０２４６】
（付記１８）
前記経路の候補の探索が前記第ｎノードから前記第ｎ＋１ノードへ進むに応じて、前記始点ノードから前記第ｎノードまでの探索した経路を表示装置に表示させる、付記１２〜１７のいずれか１項に記載の経路探索方法。
【０２４７】
（付記１９）
前記経路の探索が前記探索候補から除外されたことを示す情報を前記表示装置に表示させる、付記１８に記載の経路探索方法。
【０２４８】
（付記２０）
前記経路の候補の探索は、探索木における深さ方向に接続された前記第ｎ＋１ノードを優先して行なわれる、付記１２〜１９のいずれか１項に記載の経路探索方法。
【符号の説明】
【０２４９】
１００  経路探索システム
１      経路探索装置
１１    ＣＰＵ
１１１  探索部
１１２  制御部
１１３  決定部
１１４  表示制御部
１２    メモリ
１３    記憶部
２      オペレータ端末
２１    入力装置
２２    表示装置
３      ネットワーク
【図１】
0006547575.tif 000002
【図２】
0006547575.tif 000003
【図３】
0006547575.tif 000004
【図４】
0006547575.tif 000005
【図５】
0006547575.tif 000006
【図６】
0006547575.tif 000007
【図７】
0006547575.tif 000008
【図８】
0006547575.tif 000009
【図９】
0006547575.tif 000010
【図１０】
0006547575.tif 000011
【図１１】
0006547575.tif 000012
【図１２】
0006547575.tif 000013
【図１３】
0006547575.tif 000014
【図１４】
0006547575.tif 000015
【図１５】
0006547575.tif 000016
【図１６】
0006547575.tif 000017
【図１７】
0006547575.tif 000018
【図１８】
0006547575.tif 000019
【図１９】
0006547575.tif 000020
【図２０】
0006547575.tif 000021