特許
J-GLOBAL ID：200903062972662870
経路計算方法及び装置
発明者：
,
,
,
出願人/特許権者：
代理人 (1件)：
亀井 弘勝 (外1名)
公報種別：公開公報
出願番号（国際出願番号）：特願平5-248242
公開番号（公開出願番号）：特開平7-103772
出願日： 1993年10月04日
公開日（公表日）： 1995年04月18日
要約：
【要約】【目的】ポテンシャル法による経路計算を実行する場合に、処理の優先付けを行うことにより、計算ループ回数を低減させ、もって計算時間を短くできる経路計算方法を提供する。【構成】探索されるリンクが既に一度探索済のリンクであって、しかも前の探索時にトータルコストが小さくテーブルでの書換えが行われたリンクであれば、そのリンクは、初めて探索される他のリンクに比べると、最適経路を形成する可能性が相対的に高い。そこで、そのリンクの接続リンクを優先して探索する。【効果】優先的でない経路は、もしそのコストが高いと、探索は後に打ち切られることになり、ループ回数の低減を測ることができる。
請求項（抜粋）：
経路ネットワークを構成する各リンクのコスト及びリンク相互の接続関係を記憶した経路ネットワークメモリと、リンクごとに、このリンクの次に接続される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) において、接続リンクを探索しようとするリンクが既に手順(d)で既に探索され、そのときの手順(e) における比較の結果、加えられた値が小さく第1のテーブルでの書換えが行われたリンクであれば、そのリンクを、初めて探索されるリンクに優先して、(d) 以下の処理を行うことを特徴とする経路計算方法。
IPC (2件)：
前のページに戻る
