Pat

J-GLOBAL ID：200903022087678961

経路計算方法及び装置

Inventor： 橋本 武夫 ,  西村 茂樹 ,  中野 啓之 ,  平野 和夫
Applicant, Patent owner： 住友電気工業株式会社
Agent (1)： 亀井 弘勝 (外1名)
Gazette classification：公開公報
Application number (International application number)：1993248243
Publication number (International publication number)：1995103773
Application date： Oct. 04, 1993
Publication date： Apr. 18, 1995
Summary：

【要約】【目的】ポテンシャル法による経路計算を実行する場合に、ツリーの探索範囲を広げないようにし、もって、計算時間を短くできる経路計算方法を提供する。【構成】探索しようとするリンクが計算終了リンクであれば、そのトータルコストを上限コストの設定値と比較し、上限コストの設定値よりも小さければ上限コストを前記トータルコストの値に設定し直し、以後ツリー探索を繰り返すときにその都度、テーブルに記入されたリンクのトータルコストを参照し、それが上限コストよりも高ければ、接続リンクを探索することなくそのリンクについての処理を打切る。

Claim (excerpt)：

経路ネットワークを構成する各リンクのコスト及びリンク相互の接続関係を記憶した経路ネットワークメモリと、リンクごとに、このリンクの次に接続される1つ又は複数の接続リンクと、このリンクの前に接続される計算済の経路上のリンクと、このリンクを含む計算済の経路のトータルコストとを記入する欄を有する第1のテーブルと、接続リンクを探索すべきリンクを記入する欄を有する第2のテーブルとを用いて、(a) 出発地及び目的地の設定に応じて、経路ネットワークメモリから一定範囲の経路ネットワークデータを読み出し、(b) 読み出された経路ネットワークを構成する各リンクのトータルコストの初期値を十分大きな値に設定して、前記第1のテーブルの該当欄に書込み、(c) 計算開始リンクを第2のテーブルに書込み、この第2のテーブルに書き込まれたリンクに対応する第1のテーブルのトータルコスト欄を0に設定し、(d) 第2のテーブルに記入されたリンクについて、第1のテーブルを参照して接続リンクを探索し、探索された接続リンクのリンクコストを前記第2のテーブルに記入されたリンクのコストに加え、この加えた値を、第1のテーブルに記入された当該接続リンクのトータルコストと比較し、(e) 比較の結果、加えられた値が大きければ、その接続リンクについての処理を打切り、小さければその値を第1のテーブルの当該接続リンクのトータルコストに書換えるとともに、前記第2のテーブルに記入されたリンクをこの接続リンクに到る計算済の経路上のリンクとして書込み、(f) 当該接続リンクを第2のテーブルに新たに記入して、前記(d) ,(e) の処理を繰り返し、(g) 第2のテーブルに記入された全てのリンクについて接続リンクの探索が終了したときに、計算終了リンクを第1のテーブルから探し出し、そのリンクに到る計算済の経路上のリンクを順に辿っていくことにより、最適経路を決定する経路計算方法において、前記手順(d) において、第2のテーブルに記入されたリンクが計算終了リンクであれば、そのトータルコストを上限コストの設定値と比較して、上限コストの設定値よりも小さければ上限コストを前記トータルコストの値に更新し、以後手順(d) を繰り返すときに、第2のテーブルに記入されたリンクのトータルコストを参照し、設定された上限コストよりも高ければ、接続リンクを探索することなくそのリンクについての処理を打切ることを特徴とする経路計算方法。

IPC (2)：

G01C 21/00 ,  G06F 17/30