【事件の表示】
　特許第２６９６０９６号「最短経路探索装置」の請求項４に係る特許に対する特許異議の申立てについて、次のとおり決定する。
【結論】
　　訂正を認める。
　　特許第２６９６０９６号の請求項４に係る特許を維持する。
【理由】
１．手続きの経緯
　特許第２６９６０９６号の請求項４に係る発明は、昭和６３年１２月２６日に出願され、平成９年９月１９日に設定登録され、その後、その特許について異議申立人　有限会社石井興産より特許異議の申立がなされ、取消理由通知がなされ、その指定期間内である平成１１年３月３０日に訂正請求がなされたものである。
２．訂正の適否についての判断
ア．訂正の概要及び、その適否の判断
　特許権者が求めている訂正の内容は以下のとおりである。
ａ．請求項４の「双方向探索手段による双方向探索過程において探索される探索ノード又は探索技を、前記経路データに含まれる枝の等級データにより制限する縮退探索手段と、」の記載を「双方向探索手段による双方向探索過程において探索される探索枝を、その探索技が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択する縮退探索手段と、」に訂正する。
ｂ．明細書１２頁３−５行の「又、縮退探索手段は、順次探索される探索ノード又は探索技を、その等級データにより制限する手段である。」の記載を「又、縮退探索手段は、双方向探索手段による双方向探索過程において探索される探索技を、その探索技が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択する手段である。」と訂正する。
ｃ．明細書１５頁３−５行の「双方向探索過程において、更に、枝の等級データにより、探索される探索フード又は探索枝が制限される。」の記載を「双方向探索手段による双方向探索過程において探索される探索枝が、その探索枝が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択される。」と訂正する。
ｄ．明細書５２頁１０−１５行の「又、第３発明は、双方向探索過程において探索される探索ノード又は探索枝を、枝の優先度を示す等級データに基づいて制限しているので、経路探索が等級の高い経路に沿って実行される可能性が高く、等級の高い枝に接続された等級の低い枝への経路探索が防止されるため、」の記載を「又、第３発明は、双方向探索過程において探索される探索枝を、その探索枝が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択するようにしているので、経路探索が等級の高い経路に沿って実行される可能性が高く、等級の高い枝に接続され、その枝よりも所定等級数だけ等級の低い枝への経路探索が防止されるため、」と訂正する。
　上記ａに関する記載として「又、永久ノードｍが楕円内に存在すると判定された場合には、ステップ３１２へ移行して、その永久ノードｍの後方探索枝の等級１Ｓ（ｍ）がさらに１つ後方の後方探索枝の等級１Ｓ（Ｐ（ｍ））−ｎ以上か否かが判定される。そして、判定結果がＮＯの場合にはその永久ノードｍは捨て去られ、ステップ３０６へ戻り、次の探索処理が実行される。即ち、１つ後方の後方探索技の等級よりｎ等級を越える下位等級の探索枝は選択されないことを意味しており、探索枝の選択が制限されたことになる。このステップにより縮退探索が行われる。」（明細書３６頁最下行−３７頁１０行）の記載がある。
　よって、上記ａの訂正は、願書に添付した明細書に記載された範囲内で、「枝の等級データにより制限する縮退探索手段」の具体的な探索方法を実施例に記載された内容となるよう、限定したものといえるから、特許請求の範囲の減縮に該当するものであって、新規事項の追加に該当せず、また、実質上特許請求の範囲を拡張し、または変更するものではない。
　上記ｂ乃至ｄの訂正は、上記ａの訂正に合わせて、詳細な説明の特許請求の範囲に対応する記載を訂正し、該請求の範囲の訂正により奏する効果を明瞭にするものであるから、不明瞭な記載の釈明である。
イ．独立特許要件の判断
　以上のとおりであるから、訂正明細書の請求項４に係る発明（以下本件発明という）は、その特許請求の範囲の請求項４に記載された下記のとおりのものである。
　　　　記
　【請求項４】ノード及び枝の情報及び枝の優先度を示す等級データとで構成される経路データを記憶した経路データ記憶手段と、
探索開始位置及び探索終了位置を入力する位置入力手段と、
探索開始位置及び探索終了位置の双方向から順次ノード又は枝を探索して最短経路を探索する双方向探索手段と、
双方向探索手段による双方向探索過程において探索される探索技を、その探索技が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択する縮退探索手段と、
双方向探索手段による双方向探索過程において双方向からの探索ノード又は探索技が接続された経路の中から、探索開始位置から探索終了位置に至る最短経路を決定する最短経路決定手段と、
その最短経路を表示する表示手段と
を有する最短経路探索装置。
　本件発明に対して当審が平成１０年１２月１４日付けで通知した取消理由通知で引用した刊行物１及び２には下記のとおりの記載がある。
刊行物１：特開昭６２−８６５００号公報
　「第１の記憶手段ａには、各交差点毎に、重要道路同士が交差する重要交差点か否かの交差点種別及びその位置座標が記憶されている。
　第２の記憶手段ｂには、各重要交差点毎に、それに隣接する重要交差点及びそれまでの区間道程が記憶されている。
　第３の記憶手段ｃには、各交差点毎に、それに隣接する交差点及びそれまでの区間道程が記憶されている。
　第４の記憶手段ｄには、隣接重要交差点間を結ぶ重要道路上の非重要交差点列が記憶されている。」（公報２頁右上欄１３行−左下欄４行）
　「道路地図，交差点等の各種情報の記憶は、外部メモリ１２によって行なわれている。
　第４Ｂ図に示されるように、外部メモリ１２内には、基準となる道路地図（第４Ａ図参照）を縦横に区画して得られた各ブロック（０，０）〜（２，２）に対応して、複数のブロックエリアが設けられている。
　各ブロックエリアは、更に当該ブロックに含まれる各交差点に対応した複数の交差点Ｎｏ．エリア（１〜８），（９〜１１），（１２〜１８）等に分割されている。
　各交差点Ｎｏ．エリアには、当該交差点のＸ，Ｙ座標情報エリア，隣接交差点Ｎｏ．エリア，隣接交差点までの道程情報エリア，隣接交差点への方位情報エリア，交差点名称情報エリア，フラグエリアおよびインター番号エリアが設けられている。
　フラグエリアには、高速道上フラグ，立体交差フラグ，高速インター上フラグ，高速道路への接続道路上フラグ，交差点名称在りフラグ，高速インター出口フラグ，高速インター入口フラグのほか、特にこの発明に関連して国道等の重要度の高い道路同士が交差する重要交差点であることを示すフラグ（重要交差点フラグ）が設けられている。
　更に、外部メモリ１２内には、第４Ｂ図に示される全交差点に関する情報のほかに、第４Ｃ図に示されるように、重要度の高い道路同士が交差する重要交差点のみに関する幾つかの情報が記憶されている。
　すなわち、このエリアは各中心重要交差点毎のエリアに区画されており、各々のエリアには、隣接重要交差点Ｎｏ．情報，隣接重要交差点間に挟まれた非重要交差点列情報，隣接重要交差点までの道程情報がそれぞれ記憶されている。」（公報３頁右上欄５行−左下欄１７行）
　「第１９Ｂ図に出発重要交差点，目的重要交差点の選択処理の詳細を示す。
　この処理が開始されると、まず第１６図の出発交差点，目的交差点の選択処理で選択された出発交差点座標（Ｘｓｓ，Ｙｓｓ）及び目的交差点座標（Ｘｄｄ，Ｙｄｄ）の読み込みを行なう（ステップ１９１０１）。
　次いで読込まれた出発交差点が重要交差点であるか否かを第４Ｂ図に示される重要交差点フラグに基づいて判定する。
　ここで、出発交差点が重要交差点と判定されると（ステップ１９１０２肯定）、出発交差点（Ｘｓｓ，Ｙｓｓ）はそのまま出発重要交差点（Ｘｋｓ，Ｙｋｓ）として記憶される（ステップ１９１０３）。
　これに対して、出発交差点が重要交差点でないと判定されると（ステップ１９１０２否定）、次式を満足するＸＹ領域が求められる（ステップ１９１０４）。
（Ｘ−Ｘｓｓ）（Ｘｄｄ−Ｘｓｓ）＋（Ｙ−Ｙｓｓ）（Ｙｄｄ−Ｙｓｓ）＞０
　この式で決定される領域とは、第１９Ｃ図に斜線で示される領域であって、すなわち出発交差点（Ｘｓｓ，Ｙｓｓ）と目的交差点（Ｘｄｄ，Ｙｄｄ）とを結ぶ直線と直交し、かつ出発交差点（Ｘｓｓ，Ｙｓｓ）を通る直線を境界として、目的交差点側のエリアに相当する。
　次いで、求められたＸＹ領域に存在する重要交差点の各座標を参照し、その中から出発交差点に最も近い交差点を選び出す（ステップ１９１０５）。
　次いで、選択された重要交差点を出発重要交差点（Ｘｋｓ，Ｙｋｓ）として記憶する（ステップ１９１０６）。
　同様にして、目的交差点についてもこれが重要交差点であるか否かを判定する（ステップ１９１０７）。
　ここで、目的交差点が重要交差点と判定されると（ステップ１９１０７肯定）、目的交差点（Ｘｄｄ，Ｙｄｄ）はそのまま目的重要交差点（Ｘｋｄ，Ｙｋｄ）として記憶される（ステップ１９１０８）。
　これに対して、目的交差点が重要交差点でないと判定されると（ステップ１９１０７否定）、次式を満足するＸＹ領域が求められる（ステップ１９１０９）。
（Ｘ−Ｘｄｄ）（Ｘｓｓ−Ｘｄｄ）＋（Ｙ−Ｙｄ）（Ｙｓｓ−Ｙｄｄ）＞０
　上式で決定される領域とは、第１９Ｄ図に斜線で示される領域であって、すなわち目的交差点（Ｘｄｄ，Ｙｄｄ）と出発交差点（Ｘｓｓ，Ｙｓｓ）とを結ぶ直線と直交し、かつ目的交差点（Ｘｄｄ，Ｙｄｄ）を通る直線を境界として、出発交差点（Ｘｓｓ，Ｙｓｓ）側の領域に相当する。
　次いで、求められたＸＹ領域に存在する重要交差点の中から、出発交差点に最も近いものを選び出す（ステップ１９１１０）。
　次いで、選択された重要交差点を目的重要交差点（Ｘｋｄ，Ｙｋｄ）として記憶する。
　この結果、第１９Ｃ図に示されるように、出発交差点から見て目的交差点側にある重要交差点が出発重要交差点（Ｘｋｓ，Ｙｋｓ）として選択され、また第１９Ｄ図に示されるように、目的交差点から見て出発交差点側にある最寄りの重要交差点が目的重要交差点（Ｘｋｄ，Ｙｋｄ）として選択される。
　次に、経路主要部検索処理の詳細を第１９Ｅ図に示す。
　同図において、この処理が開始されると、まず出発重要交差点の１つ隣にある全重要交差点（１次重要交差点）が第４Ｃ図に示される記憶情報を参照して検索される（ステップ１９２０１）。
　次いで、第１９Ｆ図に示されるように、各重要交差点に対応する道程記憶領域に、出発重要交差点からの道程が記憶される（ステップ１９２０２）。
　その後交差点カウンタＮの値を初期値１から（ステップ１９２０３）＋１ずつ更新させながら（ステップ１９２１０）、各Ｎ次重要交差点の１つ隣にある全重要交差点，すなわち（Ｎ＋１）次重要交差点を検索し（ステップ１９２０４）、出発重要交差点から各（Ｎ＋１）次重要交差点までの道程が求められる（ステップ１９２０５）。
　そして、Ｎ＋１次重要交差点の道程記憶領域に．未だ道程が記憶されていなければ（ステップ１９２０６否定）、各交差点に対応する道程記憶領域に出発重要交差点からの道程が記憶され（ステップ１９２０８）、他方既に道程が記憶されていれば（ステップ１９２０６肯定）、既に記憶された道程よりも短い場合に限り、道程の書替が行なわれる（ステップ１９２０７）。
　以上を繰り返す間に、（Ｎ＋１）次重要交差点の中に、目的重要交差点が発見されると（ステップ１９２０９肯定）、各重要交差点までの道程情報を頼りに、目的重要交差点から出発重要交差点へ戻る最短経路の途中通過重要交差点が順に記憶される（第１９Ｇ図参照）。
　次いで、重要交差点間補間処理が実行される（ステップ１９２１２）。
　重要交差点間補間処理の詳細を第１９Ｈ図に示す。
　この処理では、まず通過順番カウンタＩの値を零リセットした後（ステップ１９２１３）、Ｉの値を＋１更新しては（ステップ１９２１４）、Ｉ番目の重要交差点と（Ｉ＋１）番目の重要交差点との間に存在する非重要交差点列を第４Ｃ図に示される記憶情報を参照して読出し（ステップ１９２１５）、読み出された非重要交差点列を、Ｉ番目の重要交差点と（Ｉ＋１）番口の重要交差点との間に挿入する（ステップ１９２１６）。
　そして、以上の処理を、通過順番カウンタＩの値が最大値Ｉｍａｘに達するまで繰り返すのである（ステップ１９２１７）。
　今仮に第１９０図に示されるように、出発重要交差点Ｐ２と目的重要交差点Ｐ９との間に、６個の交差点（Ｐ３，Ｐ４，Ｐ５，Ｐ６，Ｐ７，Ｐ８）が存在し、この中でＰ５とＰ７のみが重要交差点である場合を想定する。
　この場合、第１９Ｅ図におけるステップ１９２１１の処理が終了した時点では、第１９Ｉ図に示されるように、重要交差点列Ｐ２→Ｐ５→Ｐ７→Ｐ９が登録された状態にある。
　これに対して、第１９Ｈ図に示される重要交差点間補間処理が終了すると、第１９Ｊ図に示されるように、重要交差点Ｐ２とＰ５との間には、非重要交差点Ｐ３，Ｐ４が補間され、同様に重要交差点Ｐ５とＰ７との間には、非重要交差点Ｐ６が補間され、重要交差点Ｐ７とＰ９との間には、非重要交差点Ｐ８が補間されるのである。
　この結果、第１９Ｈ図の処理が完了した時点では、第１９Ｊ図に示されるように、重要道路上に存在する一連の交差点列Ｐ２→Ｐ３→Ｐ４→Ｐ５→Ｐ６→Ｐ７→Ｐ８→Ｐ９が得られることとなる。
　ここで、特に大切なことは、仮に全交差点を重要交差点と非重要交差点とに分けずに混在記憶させ、単に重要交差点フラグのみに基づいて、出発重要交差点Ｐ２から目的重要交差点Ｐ９までの最短経路を重要道路を通過することを条件として検索させた場合、その検索時間は極めて大きな値となるのに対し、この実施例では重要交差点のみを対象としてまず最短経路検索を行ない、その後隣接重要交差点間に予め設定した非重要交差点列を補間するという手法を採用しているため、検索時間が大幅に短縮されることである。
　次に、経路始端部検索処理の詳細を第１９Ｋ図に示す。
この処理では、まず出発交差点の１つ隣にある全交差点（１次交差点）を検索する（ステップ１９３０１）。
　次いで、各交差点に対応する道程記憶領域に第１９Ｆ図の場合と同様にして、出発交差点からの道程を記憶する（ステップ１９３０２）。
　次いで、交差点カウンタＮの値を初期値１から（ステップ１９３０３）、＋１ずつ更新させながら（ステップ１９３１０）、各Ｎ次交差点の１つ隣にある全交差点，（Ｎ＋１）次交差点を検索し（ステップ１９３０４）、次いで出発交差点から（Ｎ＋１）次交差点までの道程を求める（ステップ１９３０５）。
　そして、得られた（Ｎ＋１）次交差点の道程記憶領域に、未だ道程が記憶されていなければ（ステップ１９３０６否定）、各交差点に対応する道程記憶領域に、出発交差点からの道程を記憶させ（ステップ１９３０８）、他方既に道程が記憶されていれば（ステップ１９３０６肯定）、既に記憶された道程よりも短い場合に限り、道程の書替を行なう　（ステップ１９３０７）。
　以上の処理を繰り返す間に、（Ｎ＋１）次交差点の中に、出発重要交差点が発見されれば（ステップ１９３０９）、各交差点間での道程情報を頼りに、出発重要交差点から出発交差点へ戻る最短経路の途中通過交差点を順に記憶する（ステップ１９３１１）。
　これを、前述した第１９０図の例で説明すると、この場合出発交差点Ｐ１と出発重要交差点Ｐ２との間には、交差点は存在しないが、仮に複数の交差点が存在したとすれば、それらをつなぐ最短経路が求められるわけである。
　次に、経路終端部検索処理の詳細を第１９Ｌ図に示す。
　同図において、この処理が開始されると、まず目的重要交差点の１つ隣にある全交差点（１次交差点）が検索され（ステップ１９４０１）、続いて各交差点に対応する道程記憶領域に目的重要交差点からの道程が記憶される（ステップ１９４０２）。
　次いで、交差点カウンタＮの値を初期値１から（ステップ１９４０３）＋１更新しては（ステップ１９４１０）、各Ｎ次交差点の１つ隣にある全交差点，（Ｎ＋１）次交差点を検索し（ステップ１９４０４）、目的重要交差点から各（Ｎ＋１）次交差点までの道程が求められる（ステップ１９４０５）。
　次いで、求められた（Ｎ＋１）次交差点の道程記憶領域に、未だ道程が記憶されていなければ（ステップ１９４０６否定）、各交差点に対応する道程記憶領域に目的重要交差点からの道程が記憶され（ステップ１９４０８）、他方既に道程が記憶されていれば（ステップ１９４０６肯定）、既に記憶された道程よりも短い場合に限り、道程の書替が行なわれる（ステップ１９４０７）。
　以上を繰り返す間に、Ｎ＋１次交差点の中に、目的交差点が発見されれば（ステップ１９４０９肯定）、各交差点までの道程情報を頼りに、目的交差点から目的重要交差点へ戻る最短経路の途中通過交差点を順に記憶する（ステップ１９４１１）。
　これを前述した第１９０図の例で説明すると、目的重要交差点Ｐ９と、目的交差点Ｐ１１との間には、非重要交差点であるＰ１０が存在するため、Ｐ９→Ｐ１０→Ｐ１１なる交差点列が最終的に形成されることとなる。
　部分経路結合処理の詳細を第１９Ｍ図に示す。
　この処理が開始されると、第１９Ｍ図に示されるように、出発交差点から出発重要交差点へ至る交差点列を通過順番メモリにセットする（ステップ１９５０１）。
　次いで、出発重要交差点から目的重要交差点へ至る交差点列を、出発重要交差点に続けて通過順番メモリにセットする（ステップ１９５０２）。
　そして最後に、目的重要交差点から目的交差点へ至る交差点列を、目的重要交差点に続けて通過順番メモリにセットする（ステップ１９５０３）。
　以上の処理が完了すると、第１９０図に示される経路に対応して、出発交差点Ｐ１から目的交差点Ｐ１１へと向かい、かつ重要交差点Ｐ２，Ｐ５，Ｐ７，Ｐ９を通過することを条件として案内経路が最終的に完成するわけである（第１９Ｎ図参照）。
　このように、以上の最短経路検索処理によれば、出発交差点と目的交差点とを結ぶ最短経路が、交通重要度の高い路線を優先して自動設定されるため、これに基づき経路案内を行なえば、一般に道に迷い易い交通重要度の低い県道や市道等を避けて、交通重要度の高い国道等に沿って車両を走らせることができ、この種装置の使い勝手を向上させることができる。
　しかも、経路検索に際して、重要度の高い交差点のみを対象としてまず最短経路上の重要交差点列を求め、その後予め設定された非重要交差点列で、隣接重要交差点間を補間するようにしたため、検索時間についても大幅に短縮することが可能となる。」（公報５頁左上欄１７行−８頁左上欄１９行）
刊行物２：特開昭６２−８２４７５号公報
　「第７図（ｂ）に示す様に、始点▲Ｓ▼、終点▲Ｔ▼から同時に経路の探索を行い、両方の点から経路になりうる点として判断された点が１つでも現れると（図中▲Ａ▼▲Ｂ▼▲Ｃ▼）、始点▲Ｓ▼及び終点▲Ｔ▼からの経路探索を中止し、重り点▲Ａ▼▲Ｂ▼▲Ｃ▼のうちの１つを選び（例えば▲Ａ▼点）この点から始点▲Ｓ▼、終点▲Ｔ▼にそれぞれ逆追跡処理を行う。」（公報３頁左上欄１１−１６行）
　「本発明の並列経路探索方式及び装置により第７図（ｂ）に示すように従来の方法（第７図（ａ））に比べ探索範囲が一般的に半分になる、また並列に処理することにより、これがさらに半分の処理時間で実行できる。」（公報４頁右上欄１７行−左下欄２行）
（対比・判断）
　本件発明と上記刊行物１乃び２に記載の発明とを対比すると、上記いずれの刊行物に記載の発明にも、本件発明を特定する事項である「探索過程において探索される探索枝を、その探索枝が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択する縮退探索手段」が記載されておらず、当該事項により本件発明は、経路の探索時に「運転者が一般に道路を走行している場合に、広い一級国道からは、急に極端に狭い側道に曲がるのは少なく、一般に狭い側道から広い一級国道へ曲がることはあり得るという経験が生かされる」という格別の作用を有するものであり、本件発明が上記刊行物１乃び２に記載のものから容易に発明をすることができたものとはいえない。
ウ．むすび
　以上のとおりであるから、上記訂正は、特許法第１２０条の４第２項および同条第３項で準用する第１２６条第２−４項の規定に適合するので、当該訂正を認める。
３．特許異議の申し立てについて
ア．申立の概要
　特許異議申立人は特許異議申立時に、証拠として甲第１乃び２号証（当審が上記取消理由通知書で引用した刊行物１及び２とその内容は同じである）を提出し、本件発明は、甲第１乃び２号証に基づき当業者が容易に発明できたものであるから特許法第２９条第２項の規定に該当し、本件発明の特許は、特許法第１１３条第１項第２号の規定により取り消されるべきである旨主張している。
イ．判断
　特許異議申立人が提出した甲第１乃び２号証には、本件発明を特定する事項である「探索過程において探索される探索枝を、その探索技が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択する縮退探索手段」が記載されておらず、当該事項により本件発明は、経路の探索時に「運転者が一般に道路を走行している場合に、広い一級国道からは急に極端に狭い側道に曲がるのは少なく、一般に狭い側道から広い一級国道へ曲がることはあり得るという経験が生かされる」という格別の作用を有するものであり、本件発明が上記刊行物１乃び２に記載のものから容易に発明をすることができたものとはいえない。
ウ．むすび
　以上のとおりであるから、特許異議申立の理由および、証拠によっては、本件発明の特許を取り消すことはできない。
　また、他に本件発明の特許を取り消すべき理由を発見しない。
　よって結論のとおり決定する。
【異議決定日】
平成１１年７月２７日（１９９９．７．２７）
【訂正の要旨】
　　　　　訂正の要旨
ａ．請求項４の「双方向探索手段による双方向探索過程において探索される探索ノード又は探索枝を、前記経路データに含まれる枝の等級データにより制限する縮退探索手段と、」の記載を、特許請求の範囲の減縮を目的として「双方向探索手段による双方向探索過程において探索される探索枝を、その探索枝が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択する縮退探索手段と、」に訂正する。
ｂ．明細書１２頁３−５行の「又、縮退探索手段は、順次探索される探索ノード又は探索技を、その等級データにより制限する手段である。」の記載を、特許請求の範囲の訂正に合わせて「又、縮退探索手段は、双方向探索手段による双方向探索過程において探索される探索技を、その探索技が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択する手段である。」と訂正する。
ｃ．明細書１５頁３−５行の「双方向探索過程において、更に、枝の等級データにより、探索される探索ノード又は探索枝が制限される。」の記載を、特許請求の範囲の訂正に合わせて「双方向探索手段による双方向探索過程において探索される探索技が、その探索技が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択される。」と訂正する。
ｄ．明細書５２頁１０−１５行の「又、第３発明は、双方向探索過程において探索される探索ノード又は探索技を、枝の優先度を示す等級データに基づいて制限しているので、経路探索が等級の高い経路に沿って実行される可能性が高く、等級の高い枝に接続された等級の低い枝への経路探索が防止されるため、」の記載を、特許請求の範囲の訂正に合わせて「又、第３発明は、双方向探索過程において探索される探索技を、その探索技が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択するようにしているので、経路探索が等級の高い経路に沿って実行される可能性が高く、等級の高い枝に接続され、その枝よりも所定等級数だけ等級の低い枝への経路探索が防止されるため、」と訂正する。
（５４）【発明の名称】
最短経路探索装置
（５７）【特許請求の範囲】
　（１）ノード及び枝で構成される経路データを記憶した経路データ記憶手段と、
　探索開始位置及び探索終了位置を入力する位置入力手段と、
　探索開始位置及び探索終了位置の双方向から順次ノード又は枝を探索して最短経路を探索する双方向探索手段と、
　双方向探索手段により探索方向を切換えて双方向探索を実行する過程において、各方向から順次探索される探索ノード又は探索枝の数が略均衡するように前記探索方向の順序を切換制御する探索順序制御手段と、
　双方向探索手段による双方向探索過程において双方向からの探索ノード又は探索枝が接続された経路の中から、探索開始位置から探索終了位置に至る最短経路を決定する最短経路決定手段と、
　その最短経路を表示する表示手段と
　を有する最短経路探索装置。
　（２）ノード及び枝で構成される経路データを記憶した経路データ記憶手段と、
　探索開始位置及び探索終了位置を入力する位置入力手段と、
　探索開始位置及び探索終了位置の双方向から順次ノード又は枝を探索して最短経路を探索する双方向探索手段と、
　双方向探索手段による双方向探索過程において探索される探索ノード又は探索枝を、探索開始位置及び探索終了位置、又は探索開始位置及び探索終了位置のそれぞれの近傍点を２つの焦点とする楕円の内部領域に存在するものに限定し、その楕円を楕円の長径に対する短径の比Ｆを焦点間距離が短い程大きくするように変化させる探索領域制限手段と、
　双方向探索手段による双方向探索過程において双方向からの探索フード又は探索枝が接続された経路の中から、探索開始位置から探索終了位置に至る最短経路を決定する最短経路決定手段と、
　その最短経路を表示する表示手段と
　を有する最短経路探索装置。
　（３）前記探索領域制限手段は、探索開始位置及び探索終了位置に対してそれぞれ所定距離Ｃ０だけ外側に設定された２点を焦点とし、焦点間距離Ｃ、長径に対する短径の比Ｆで定義される楕円の内部領域に存在するものに限定し、その楕円を前記焦点間距離Ｃが短い程、前記比Ｆを大きくし、前記比Ｆが大きい程、前記所定距離Ｃ０を大きくするように変化させることを特徴とする特許請求の範囲第２項に記載の最短経路探索装置。
　（４）ノード及び枝の情報及び枝の優先度を示す等級データとで構成される経路データを記憶した経路データ記憶手段と、
　探索開始位置及び探索終了位置を入力する位置入力手段と、
　探索開始位置及び探索終了位置の双方向から順次ノード又は枝を探索して最短経路を探索する双方向探索手段と、
　双方向探索手段による双方向探索過程において探索され
る探索枝を、その探索枝が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択する
　双方向探索手段による双方向探索過程において双方向からの探索ノード又は探索枝が接続された経路の中から、探索開始位置から探索終了位置に至る最短経路を決定する最短経路決定手段と、
　その最短経路を表示する表示手段と
　を有する最短経路探索装置。
　（５）前回の探索に対して探索終了位置が同一の場合には、探索開始位置が既に決定されている最短経路上又は探索終了位置からの探索領域内に存在するか否かを判定する探索開始位置判定手段と、
　その探索開始位置がその最短経路上又はその探索領域内に存在する場合には、既に求められている探索終了位置からの探索結果データによって探索開始位置から探索終了位置までの最短経路を決定する第２最短経路決定手段と、
　探索開始位置がその最短経路上又はその探索領域内に存在しない場合には、探索開始位置からのみ順次ノード又は枝を探索して最短経路を探索する片方向探索手段と、
　その片方向探索からの探索ノード又は探索枝が前記探索結果データに含まれる探索ノード又は探索枝に接続された経路の中から、探索開始位置から探索終了位置へ至る最短経路を決定する第３最短経路決定手段と
　を更に有することを特徴とする特許請求の範囲第１項乃至第４項記載の最短経路探索装置。
【発明の詳細な説明】
　【産業上の利用分野】
　本発明は、ネットワークにおいて、探索開始位置から探索終了位置へ至る最短経路を自動探索する装置に関する。例えば、移動体の現在位置からこれから行こうとする目的位置までの最短経路を道路地図上において探索するナビゲーション装置等に応用される。
　【従来技術】
　移動体の現在位置から目的位置へ至る最短経路を探索し、その経路を表示する車載ナビゲーション装置は多数開発され公開されている。
　これらの装置に要請されることは、探索開始位置と探索終了位置のノード対が特定されたとき、そのノード対間の最短経路を高速に探索して表示することである。
　従来から、最短経路の探索手法はネットワーク管理や電気回路の分野においても必要であり研究されている。
　例えば、ラベル確定法、行列法、ダイナミックプログラム法等がある。なかでも、ラベル確定法は探索効率が良くディジタル演算に適していることから多くの研究がなされている。その中では、ポテンシャル法、ダイキストラ法、ニコルソン法等が代表的な解決として知られており、特に最近では、探索中の状態ファイルを更新する効率のよい方法として、ヒープ法やバケット法等の改良アルゴリズムが発表されている。
　【発明が解決しようとする課題】
　しかし、上記のラベル確定法は、探索開始位置から経路距離が最短な探索枝を順次延ばして行く手法のため、最先端のノードは概念的には探索開始位置から等距離の位置にある。したがって、探索は探索開始位置を中心として同心円状に拡大して行くことになり、探索終了位置がその円上にくる時に探索終了となる。このため、探索開始位置に対して探索終了位置と反対側の半円内部に最短経路が存在する確率は低く、その半円領域の探索は無駄な探索となる。
　それに対し、ニコルソン法は１つの探索開始位置と探索終了位置間における最短経路を求める問題を対象にしている。ニコルソン法は探索開始位置と探索終了位置の双方向からラベル確定法と同様な探索を行うものである。したがって、探索は探索開始位置と探索終了位置とをそれぞれ中心として同心円状に等半径で拡大して行くことになり、双方向からの円が交差する時に探索終了となる。このため、一方向から探索するラベル確定法に比べて探索領域は約１／２となる。
　しかし、ニコルソン法においても、探索開始位置と探索終了位置とを中心とする各円の相互に遠い側の半円領域も探索していることになり、最短経路の存在確率の低い範囲を無駄に探索している。このため、探索時間がかかり車載ナビゲーション装置に要求される応答時間を確保するには不十分である。
　又、探索開始位置と探索終了位置とをそれぞれ中心とする２つの円が等半径となるように、双方向からの探索順序を交互に切り換えている。しかし、探索時間は探索するノード数で決定されるため、ノード密度が異なれば双方向から等距離で探索する場合が最も探索ノード数が少ないとは限らない。このように、ニコルソン法でも最も効率的な探索が実行されているとは言い難い。
　更に、車両が最短経路に従って移動している時、何らかの原因で最短経路から外れる場合など、同一目的位置に向けて再び最短経路を求め表示したい場合がある。しかし、改めて新たな現在位置と目的位置とに対して両位置の最短経路を求めていたのでは、経路探索の効率が良くなく、やはり動作速度上問題がある。
　【課題を解決するための手段】
　第１発明は、第１図（ａ）に示すように、経路データ記憶手段、位置入力手段、双方向探索手段、探索順序制御手段、最短経路決定手段、表示手段とで構成されている。
　経路データ記憶手段は、ノード及び枝で構成される、例えば、道路地図、回路等の最短経路探索の対象となる経路データを記憶する手段である。
　位置入力手段は、探索開始位置及び探索終了位置を入力する手段である。例えば、移動体の地図上の現在位及び目的位置を入力する手段である。　　　　
　双方向探索手段は、位置入力手段により入力された探索開始位置及び探索終了位置の双方向から経路データを用いて順次ノード又は枝を探索して最短経路を探索する手段である。最短経路は経路長、所要時間、費用等やこれらの量を総合評価した評価値が最小となる経路として定義される。そして、各方向からの探索は、例えば、この評価値が小さいものから順にノード又は枝を選択して、探索ネットワークを拡張する手順で実行される。
　探索順序制御手段は、双方向探索手段により探索方向を切換えて双方向探索を実行する過程において、各方向から順次探索される探索ノード又は探索枝の数が略均衡するように探索方向の順序を切換制御する手段である。
　最短経路決定手段は、双方向からの探索ノード又は探索技が接続された経路の中から、探索開始位置から探索終了位置に至る最短経路を決定する手段である。例えば、探索過程において探索開始位置への最短経路の確定されたフードと探索終了位置への最短経路の確定されたノードが最先に一致した時には、そのノードが存在する経路が最短経路とされる。
　表示手段は、その最短経路を表示する手段である。例えば、道路地図を表示すると共に、その道路地図上に探索開始位置である現在位置と探索終了位置である目的位置と、その両位置を結ぶ最短経路とを表示する手段である。
　第２発明は、第１図（ｂ）に示すように、経路データ記憶手段、位置入力手段、双方向探索手段、探索領域制限手段、最短経路決定手段、表示手段とで構成されている。経路データ記憶手段、位置入力手段、双方向探索手段、最短経路決定手段、表示手段は第１発明と同一の構成である。
　探索領域制限手段は、双方向探索手段による探索領域を所定の楕円の内部領域に制限するものである。そして、その楕円を、探索開始位置及び探索終了位置、又は探索開始位置及び探索終了位置のそれぞれの近傍点を２つの焦点とし、長径に対する短径の比Ｆを焦点間距離が短い程大きくするように形状を変化させることを特徴としている。
　更に、探索領域制限手段の他の構成として、探索開始位置及び探索終了位置に対してそれぞれ所定距離Ｃ０だけ外側に設定された２点を焦点とし、焦点間距離Ｃ、長径に対する短径の比Ｆに関して、焦点間距離Ｃが短い程、比Ｆを大きくし、比Ｆが大きい程、所定距離Ｃ０を大きくするように形状を変化させた楕円に探索領域を制限するものでも良い。
　第３発明は、第１図（ｃ）に示すように、経路データ記憶手段、位置入力手段、双方向探索手段、縮退探索手段、最短経路決定手段、表示手段とで構成されている。位置入力手段、双方向探索手段、最短経路決定手段、表示手段は第１発明と同一の構成である。
　経路データ記憶手段はノード及び枝の情報及び枝の優先度を示す等級データを記憶するものである。
　又、縮退探索手段は、
双方向探索手段による双方向探索過程において探索される探索枝を、その探索枝が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択する
　この等級は、例えば、道幅や車線数及び高速道路、国道、県市町村道などの道路等級等で区別されるような枝の優先度を示すものである。したがって、選択技の等級を所定の条件で制限するということは、例えば、広い国道に沿って１つの経路が探索されている場合に、その国道に接続されている狭い脇道等は探索の対象から除外され、その脇道に接続される枝はそれ以上探索されないことを意味しており、探索速度が向上する。
　又、第４発明は、第１図（ｄ）に示すように、上記第１発明乃至第３発明において、更に、探索開始位置判定手段、第２最短経路決定手段、片方向探索手段、第３最短経路決定手段を付加したものである。
　この第４発明は、探索終了位置が不変で探索開始位置が変化した２回目以後の探索に有効である。
　探索開始位置判定手段は、探索開始位置が既に決定されている最短経路上又は探索終了位置からの探索領域内に存在するか否かを判定する手段である。
　第２最短経路決定手段は、探索開始位置判定手段の判定結果が肯定的である時に、探索終了位置からの探索結果データによって探索開始位置から探索終了位置までの最短経路を決定する手段である。
　片方向探索手段は、探索開始位置判定手段の判定結果が否定的である時に、探索開始位置からのみ順次ノード又は枝を探索して最短経路を探索する手段である。即ち、探索終了位置からの探索結果は前回までの探索で既に得られているので、それを利用するようにしている。
　第３最短経路決定手段は、その片方向探索からの探索ノード又は探索技が探索結果データに含まれる探索ノード又は探索技に接続された経路の中から最短経路を決定する手段である。即ち、片方向探索が進行すると探索終了位置から探索されたノード又は探索枝に接続されるようになる。しかし、この場合には、最先に接続される経路が最短経路になるとは限らないので、接続された幾つかの経路の中から、経路の評価値が最小のものが最短経路として決定される。
　【作用】
　第１発明では、位置入力手段により探索開始位置と探索終了位置が指定されると、双方向探索手段により探索開始位置と探索終了位置の双方向から順次探索される。探索順序制御手段により、双方向探索手段により探索方向を切換えて双方向探索を実行する過程において、各方向から順次探索される探索ノード又は探索技の数が略均衡するように探索方向の順序が切換制御される。そして、最短経路決定手段により、探索が進行して双方向か探索枝又は探索ノードが一致した経路の中から最短経路が決定され、表示手段によりその最短経路が表示される。
　又、第２発明では、探索領域が、探索開始位置及び探索終了位置、又は探索開始位置及び探索終了位置のそれぞれの近傍点を２つの焦点とし、長径に対する短径の比Ｆを焦点間距離が短い程大きくするように形状の変化する楕円の内部領域に制限される。
　さらに、第２発明の他の構成では、探索領域制限手段により、探索開始位置及び探索終了位置に対してそれぞれ所定距離Ｃ０だけ外側に設定された２点を焦点とし、焦点間距離Ｃ、長径に対する短径の比Ｆに関して、焦点間距離Ｃが短い程、比Ｆを大きくし、比Ｆが大きい程、所定距離Ｃ０を大きくするように形状を変化させた楕円の内部領域に探索領域が制限される。
　このように探索開始位置と探索終了位置との距離に応じて探索領域の楕円の形状を変化させることにより、探索されるノード又は枝が上記の所定の最短経路の存在する確率の高い領域内に制限することが可能となり、探索効率が向上する。即ち、探索開始位置と探索終了位置とが大きく離れている程、それらの位置を結ぶ直線に近い経路が最短経路と考えられる可能性が大きくなるため、探索領域をより偏平な楕円とすることで指向性を持たせ、探索領域を効果的に制限することができる。逆に、探索開始位置と探索終了位置との距離が短い程、２つの位置を結ぶ直線から離れた経路も最短経路になり得る可能性が大きくなることから、楕円を円形に近づけ指向性を無くすることで、より正確な最短経路の探索が可能となる。さらに、探索開始位置と探索終了位置との距離が短い程、２つの焦点を探索開始位置及び探索終了位置の外側に配置して、その距離Ｃ０を大きくすることで、探索開始位置から探索終了位置に対して遠ざかる方向の領域と、探索終了位置から探索開始位置に対して遠ざかる向の領域をより広く含めることができるため、さらに、より正確な最短経路の探索が可能となる。
　又、第３発明では、第１発明の探索順序制御手段に換わる縮退探索手段により、
双方向探索手段による双方向探索過程において探索される探索枝が、その探索技が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択され
　又、第４発明では、２回目以後の探索において、探索開始位置判定手段により、探索開始位置が既に決定されている最短経路上又は探索終了位置からの探索領域内に存在すると判定されると、第２最短経路決定手段により、探索終了位置からの探索結果データによって探索開始位置から探索終了位置までの最短経路が直ちに決定される。又、探索開始位置判定手段により探索開始位置が既に決定されている最短経路上又は探索終了位置からの探索領域内に存在しないと判定されると、片方向探索手段により、探索開始位置からのみ順次最短経路が探索される。そして、第３最短経路決定手段により、探索が進行しその片方向探索からの探索ノード又は探索枝が探索結果データの探索ノード又は探索技に接続されたと判定されると、その接続された経路の中から最短経路が決定される。
　【実施例】
　以下、本発明を具体的な実施例に基づいて説明する。
　第２図は本発明の実施例に係る車載ナビゲーション装置１０の構成を示すものである。
　尚、本実施例では探索開始位置は現在位置に、探索終了位置は目的位置として具体化されている。
　図において、コンピュータ２０はデータ記憶媒体２１をアクセスして、最短経路探索演算等を実行する装置である。コンピュータ２０は専用のマイクロプロセッサか、或いは汎用性のパーソナルコンピュータで構成され、記憶媒体２１は、フロッピィディスク，ハードディスク若しくはＲＡＭディスク等で構成される。その記憶媒体２１には地図データベースと探索プログラムが記憶され、探索過程データや探索結果データを記憶する探索データファイルが形成されている。
　又、車載ナビゲーション装置１０は、車両の現在位置を受信する受信手段５０を備えている。その受信手段５０は車載アンテナ５１と受信機５２で構成され、車外に設置された送信千段６０から現在位置を表す地点コードデータを受信し、そのデータをコンピュータ２０に回線８４を介して出力する手段である。送信手段６０は送信アンテナ６１と送信機６２で構成され、一般に路側に設置されており、その設置位置の地点コードデータを発信する手段である。
　尚、現在位置を与える方法は、上記方法の他、公知の車載センサにより方位と移動距離を計測して推測する方法か、通信衛星から測位データを受信して現在位置を知る位置標定法であっても良い。
　車載ナビゲーション装置１０は、ＣＲＴディスプレイ４１若しくはＸＹＺモニタで構成されるディスプレイ手段４０を有している。ディスプレイ手段４０は、幾つかの街路、車両の記号、現在位置と目的位置とを結ぶ最短経路等の地図を表示する。又、ディスプレイ手段４０は更にパネルスイッチ４３及び画面上に設けたタッチスイッチ４４を備えており、制御コンソール３０に替えてオペレータ制御コマンドを入力できる。例えば、目的位置は、画面上の地図において目的位置に対応する地点を上記スイッチの操作により直接指定することにより入力できる。この他、オペレータはパネルスイッチ４３とタッチスイッチ４４の操作手順を交互に組み合わせて種々のコマンドを発生できる。ディスプレイ千段４０は切替スイッチ４５を介して制御コンソール３０とコンピュータ２０に接続されている。
　制御コンソール３０はディスプレイ手段４０の画面を制御すると共に回線８１を介してコンピュータ２０と接続され、コマンドデータをコンピュータ２０へ出力する。コンピュータ２０は回線８３を介してディスプレイ手段４０へ映像信号、例えばＲＧＢ信号を送り、地図等を画面に表示する。
　スイッチ回路７１はエンジンキースイッチ７２と連動してオン、オフ信号を発生し、回線８２を介してコンピュータ２０へその信号を出力する。コンピュータ２０はこのオン信号を入力した時は、経路探索が１回も実行されていないことを記憶するため、再探索フラグを０にリセットする。
　本装置の電源が入れられると、後述の方法で入力される現在位置を中心とする地図がディスプレイ手段４０に表示される。その後オペレータは、上述したように制御コンソール３０又はディスプレイ手段４０のスイッチ類４３、４４を操作して、目的位置を指定する。この指定により得られた目的位置データはコンピュータ２０に入力され記憶媒体２１に記憶される。又、車両が所与の領域の街路を走行中、路側に設置されている送信手段６０の横を通ると、送信機６２で発信された現在位置を示すデータは受信機５２で受信され、コンピュータ２０はこのデータを受信機５２から入力し、現在位置データとし記憶媒体２１に記憶する。
　地図はノードを中心に構成しても枝（リンク）を中心に構成しても良い。ノードを中心として構成される地図データベースは次の情報で構成されている。
　（１）街路を規定するノードのコード番号
　（２）直進、右左折などの通行規制を規定する通行フラグ
　（３）車種規制、時間帯規制などリンクの通行規制を規定するリンク通行フラグ
　（４）リンク距離、旅行時間又は速度等のリンク属性値
　（５）道路種別、道路等級等のリンク属性値
　（６）ノードのＸ、Ｙ座標
　更に、行政区界、港湾、川、施設、鉄道及びそれらの名前、座標等の情報が含まれる。この記憶された地図データベースは地理的に所与の領域を移動するときに使用される。
　車両が、ある地点からある地点へ移動する時、コンピュータ２０が適切な地図を呼び出し、ＣＲＴディスプレイ４１に表示することができる。推測航法を備えた車載ナビゲーション装置では車両の移動軌跡を推測でき、これを表示中の地図に重ね書きすることができる。又、後に述べる経路探索アルゴリズムによって得られる最短経路を表示中の地図に重ね書きすることができる。
　経路探索アルゴリズムによって得られる最短経路は、経路を構成するノード番号の並びとして記憶媒体２１の探索データファイルに記憶される。経路探索が終了した時点の探索結果データはトランジエントな探索データファイルとして記憶媒体２１に記憶される。そして、探索データファイルは探索枝を展開するカレントファイルと、探索ノードを展開するノードファイルとで構成される。カレントファイルには次のデータが展開される。
　（１）経路探索の開始と共に順次開かれる探索枝の並び
　（２）探索枝を開き終わったか、まだ開き終わっていないかを示すフラグ
　（３）探索枝までの経路コスト。例えば経路距離、又は旅行時間
　（４）探索枝へ最短経路で連続する一つ手前のノード番号
　（１）の探索技の並びは、（３）の経路コストを属性値とし、その経路コストが最小となる探索技の抽出に用いられる。（２）のフラグは最短経路の確定された探索枝（永久枝）の集合と、未だ、最短経路が確定していないが探索技により次のノードを探索している過程の枝（活性枝）の集合を区別するために用いられる。
　上記のデータで構成されるカレントファイルはヒープ法かバケット法によるデータ構造を持たせると、次に開く枝の集合を限定でき、且つ、評価値が最小な枝の抽出が効率的となる。このカレントファイルは探索枝の一つを１レコード単位とするもので、探索の進行と共にファイルの大きさが増大する。このカレントファイルは、現在位置及び目的位置からの探索過程でそれぞれ展開される２つのサブファイルで構成されている。
　又、ノードファイルは探索中のノード（活性ノード）と最短経路の確定されたノード（永久ノード）と探索技が未だ延びていないノード（休眠ノード）とを区別して記憶するものである。そして、このノードファイルも現在位置からの探索と目的位置からの探索とで展開される２つのサブファイルに分かれている。又、目的位置からの探索に使用されるノードファイルには、探索終了時、２回目以後の探索過程で使用される探索結果データが記憶されていることになる。
　次に、最短経路探索手順をコンピュータ２０の処理手順を示したフローチャートに従って説明する。
　プログラムは第３図に示すように、大きく３つに分類される。
　第１は画面表示や目的位置、現在位置の入力を制御し全体を監視するメインプログラムであり、第２はＣＲＴディスプレイ４１をリフレッシュし、制御コンソール３０からの操作データ等の入力を行うプログラムであり、第３は最短経路探索を実行するためのプログラムである。このうち、第２のプログラムはリフレッシュ時又はデータ入力が発生する毎にメインプログラム及び第３の最短経路探索プログラムをインタラプトし、第３の最短経路探索プログラムは現在位置が入力され最短経路探索の実行要求が発生する毎に、メインプログラムをインタラプトするように構成されている。
　メインプログラムはコンピュータによって処理される全ての情報に応答して、必要なデータを計算しフォーマット化する。例えば、ＣＲＴディスプレイ４１に表示され選択される地図のデータ、現在位置及び目的位置のコマンドデータ、最短経路探索プログラムに与える現在位置と目的位置を示す地点コードと探索モード等を計算し処理する。又、目的位置が更新される毎に、再探索フラグは０にリセットされる。
　次に、最短経路探索手順について説明する。
　第４図において、ステップ１００では、再探索フラグを照合することにより初回探索であるか否かが判定される。再探索フラグが０のリセット状態であれば、初回探索であることを意味しており、ステップ１０２で探索実行プログラムが実行され、探索実行後、既に初回探索が完了したことを示すために再探索フラグが１にセットされ、ステップ１０４で最短経路が更新される。又、初回探索でない場合には、ステップ１０６へ移行して現在位置が既に求められている最短経路上に存在するか否かが判定され、最短経路上に存在する場合には、最短経路を更新することなく、本プログラムは終了される。即ち、地図上の現在位置を更新するだけで良い。又、現在位置が最短経路上に存在しない場合には、ステップ１０２へ移行して最短経路の再探索が実行される。
　そして、本プログラムによる探索結果に基づいて、メインプログラムが実行され、求められた最短経路はＣＲＴディスプレイ４１に表示される。
　次に、ステップ１０２で実行される探索実行手順について説明する。　　　　
　第５図において、ステップ２００では、再探索フラグを照合することにより初回探索であるか否かが判定される。初回探索であると判定された場合には、ステップ２０２へ移行して初回探索実行プログラムが実行され、初回探索でないと判定された場合には、ステップ２０４へ移行して再探索実行プログラムが実行される。そして、探索実行後、ステップ２０６にて探索成功か否かが判定され、探索成功であれば、そのまま終了し、探索成功でない場合には、ステップ２０８で等ノードによる探索が実行される。即ち、ステップ２０２、２０４の探索では探索領域を楕円領域に制限しているので、現在位置と目的位置とを結ぶ経路がその楕円領域に存在しない場合が考えられるので、その場合には探索領域を制限しない双方向の等ノード探索が実行される。
　次に、ステップ２０２で実行される初回探索手順について説明する。
　処理手順を詳細に説明する前に、探索概念について次に説明する。
　初回探索手順は、現在位置と目的位置の双方向から探索する方法（双方向探索）、探索領域を楕円内部に制限する探索方法（楕円探索）、双方向探索の探索過程において探索されるノード又は枝の数が均衡するような探索方法（等ノード探索）、最短経路を評価する経路長、所要時間、費用等又はこれらを総合評価した評価値（以下、この評価値を「コスト」という）の小さいものから順に探索する方法（等コスト探索）、探索技をその等級に応じて制限する探索方法（縮退探索）の全てのＡＮＤ条件により実行される。
　双方向探索、等ノード探索、等コスト探索を実行すると、探索領域は概念的には、第８図に示すように、現在位置０及び目的位置Ｄを中心とする探索の進行に伴って拡大していく等半径の円となる。そして、その２つの円が交差し両方向から延びた永久ノードが最初に接続されたとき、そのノードの存在する経路が現在位置と目的位置とを結ぶ最短経路となる。
　又、楕円探索は、探索領域を現在位置と目的位置とを原則的に焦点とし、その焦点を結ぶ軸を長軸とする楕円の内部に限定する探索手法である。そして、楕円探索を上記の双方向探索、等ノード探索、等コスト探索と組み合わせると、第９図に示すような、探索モデルとなる。
　このような楕円内部に探索領域を限定することで、現在位置Ｏからの探索においては目的位置Ｄから遠ざかる方向Ｘ、目的位置Ｄからの探索においては現在位置Ｏから遠ざかる方向Ｙへの探索技の展開が制限されることになり、最短経路が存在する可能性の少ない領域Ａ，Ｂでの探索は制限される。したがって、高速探索が可能となる。
　又、楕円は長径と短径の比Ｆ（０＜Ｆ＜１）を変　えることにより、その形状をパラメトリックに制御できる。Ｆを大きくすると円に近づき、Ｆを小さくすると細長い楕円となる。現在位置と目的位置とを焦点とした場合には、現在位置と目的位置との距離、つまり焦点間の距離（２Ｃ）が短いとネットワークの粗さが相対的に大きくなり、楕円内に最短経路が入らない場合が発生する。この弊害を避けるため、現在位置０と目的位置Ｄとの距離（ＯＤ間距離）が短い時は円に近づけ、長い時は探索効率を上げるため細長い楕円とする。一方、円に近づけると離率が小さくなり後退方向の最短経路をカットしてしまう場合が発生するので、焦点を現在位置と目的位置の外側に位置するように、焦点間距離をオフセットしてＯＤ間距離よりも大きくした楕円とする。つまりＣ０をオフセットとし、Ｃ＝Ｃ＋Ｃ０を新しい焦点と楕円中心との距離Ｃとする。
　ＦはＯＤ距離の長短に応じ、パラメトリックに変化させる。つまりＣが小さい時はＦを大きくし、Ｃが大きくなるに従いＦを小さくし楕円ｅを細長くする。実施例ではＣ１＜Ｃ２＜Ｃ３なる閾値を設定し、Ｃ＜Ｃ１ならＦ＝Ｆ１、Ｃ１≦Ｃ＜Ｃ２ならＦ＝Ｆ２、Ｃ２≦Ｃ＜Ｃ３ならＦ＝Ｆ３、Ｃ３＜ＣならＦ＝Ｆ４であるステップ関数とする。ただしＦ１〜Ｆ４は
１＞Ｆ１＞Ｆ２＞Ｆ３＞Ｆ４＞０なる定数である。
　縮退探索は、探索の際、探索枝を順次道路等級の等しいか、又は高い方へ上げながら、優先順位の低い道路枝をカットし、縮退した道路網により探索を行うものである。これにより、例えば、道幅の広い国道等に沿って探索が実行されている時、その国道に接続される道幅の狭い脇道等へ探索枝が延びることが防止され、効率の良い探索が行われる。道路等級は任意に設定でき、例えば市町村道、県道、国道、高速道路の順に等級を設定することでも良い。この他の、道路中の大小、設計交通容量、設計速度、有料道路と無料道路の違いによって等級を設定することもできる。道路等級により縮退を行うと、等級が上がるに従いネットワークが粗となり、経路の跡切れを生じる場合があるので、跡切れを避けるため、前の探索枝のｎランク下位の等級まで接続を認めるようにする。
　結局、上記の探索を全て実行すると極めて効率の良い探索が実行されることになり、その探索の概念は、第１０図に示される。
　次に、初回探索手順を第６図に従って詳細に説明するが、各記号及び用語を次のように定義する。
　Ｓ：現在位置のノード番号
　　　その座標（ＸＳ０，ＹＳ０）
　Ｔ：目的位置のノード番号
　　　その座標（ＸＴ０，ＹＴ０）
　ｉ：任意の活性ノードの番号
　ｋ：新たに発生された活性ノードの番号
　活性ノードは前に定義したように、最短経路は未だ確定していないが、永久ノードから探索枝（活性枝）が延び、現在開かれているノードをいう。
　ｍ：任意の永久ノードの番号
　永久ノードは前に定義したように、Ｓノード又はＴノードまでの最短経路が確定しているノードをいう。
　又、現在位置からの探索をＳ探索、目的位置からの探索をＴ探索、Ｓ探索による永久ノードをＳ永久ノード、Ｔ探索による永久ノードをＴ永久ノードという。
　ｊ：任意の接続ノードの番号
　接続ノードは、Ｓ探索又はＴ探索における活性ノード又は永久ノードが相手のＴ探索又はＳ探索における活性ノード又は永久ノードと一致したノードをいう。
　ｖ　：全てのノードを含む一般的なノードの番号
　Ｓ（ｖ）：Ｓノードからｖノードへ至る探索現在時点での最小コストを意味し、これをノードコストという。
　ＳＰ（ｍ）：永久ノードｍのノードコトスで永久ノードコストという。
　又、コストとは前に定義したように、距離、所要時間等を含めた最短経路の評価値であり、そのコストが最小となる経路が最短経路となる。したがって、コストは探索枝を展開するためのパラメータであり、そのノードまでのコトスや、探索枝のコスト、経路のコストという概念が存在する。
　Ｔ（ｖ）：ｖノードからＴノードへ至る探索現在時点の最小コストを意味し、これをノードコストという。
　ＳＴ（ｍ）：永久ノードｍのノードコトスで永久ノードコストという。
　Ｒ（ｊ）：探索現在時点での接続ノードｊの存在する経路（現在位置から目的位置に至る経路）のコストを意味し、これを経路コストという。
　ｕ：探索現在時点での経路コストＲ（ｊ）の最小な接続ノードの番号
　Ｓ探索、Ｔ探索にかかわらず、ＳノードからＴノードへ向かう経路上において、Ｔノード側を前方といい、その経路上の２つのノードにおいて、Ｔノードに近いノードを他のノードに対して前方ノードという。又、逆に、Ｓノード側を後方といい、Ｓノードに近いフードを他のノードに対して後方ノードという。
　Ｐ（ｉ）：探索現在時点において、活性ノードｉに接続される最短経路上の最近接の後方永久ノードの番号
　Ｑ（ｉ）：探索現在時点において、活性ノードｉに接続される最短経路上の最近接の前方永久ノードの番号
　α：探索現在時点におけるＳ探索の活性ノードのノードコストの中の最小値をいい、この値を探索コストという。この探索コストはＳ探索において活性ノードのなかから永久ノードを選択するパラメータとなる。
　β：探索現在時点におけるＴ探索の活性ノードのノードコストの中の最小値をいい、この値を探索コストという。この探索コストはＴ探索において活性ノードのなかから永久ノードを選択するパラメータとなる。
　ｄｍ，ｉ：永久ノードｍと活性フードｉ間の探索枝のコストを意味し、これを探索枝コストという。　ａ，ｂ：楕円の長径、短径、ａ＝Ｃ／１−Ｆ２，ｂ−ａＰ
　Ｃ：楕円の中心と焦点間の距離
　Ｃ１，Ｃ２，Ｃ３：閾値、０＜Ｃ１＜Ｃ２＜Ｃ３
　Ｆ１，Ｆ２，Ｆ３，Ｆ４　：定数、１＞Ｆ１＞Ｆ２＞Ｆ３＞Ｆ４＞０
　Ｆ　：楕円の長径と短径の比　Ｆ＝ｂ／ａ
　　　Ｃ　≦Ｃ１なら　Ｆ＝Ｆ１
　　　Ｃ１＜Ｃ　≦Ｃ２なら　Ｆ＝Ｆ２
　　　Ｃ２＜Ｃ　≦Ｃ３　ならＦ＝Ｆ３
　　　Ｃ３＜Ｃ　なら　Ｆ＝Ｆ４
ｘ０，ｙ０：楕円の中心座標
　θ：楕円の傾き　θ＝Ｓｉｎ−１｛（ＹＴ０−ＹＳ０）／２Ｃ｝　ｘｉ，ｙｉ：活性ノードｉの座標
　ｆ（ｘ，ｙ）：楕円の内外判定関数
　ｆ（ｘ，ｙ）≧０なら（ｘ，ｙ）は楕円の内側にある。
　ｆ（ｘ，ｙ）＜０なら（ｘ，ｙ）は楕円の外側にある。
　１Ｓ（ｖ）：後方ノ一ドＰ（ｖ）とノードｖ間の探索枝の道路等級をいい、大きい程等級が上である。
　１Ｔ（ｖ）：ノードｖと前方ノードＱ（ｖ）間の探索枝の道路等級をいい、大きい程等級が上である。
　次に、第６図のフローチャートに従って、探索手順を説明する。
　ステップ３００では探索データファイルの初期化が実行される。即ち、ＳノードとＴノードが最初の活性ノードとして探索データファイルの中のノードファイルに展開され、それらのノードのノードコストは、Ｓ（ｉ）＝０，Ｔ（ｉ）＝０に、後方ノード及び前方ノードは、Ｐ（ｉ）＝Ｓ，Ｑ（ｉ）＝Ｔに設定される。
　次に、ステップ３０２にて、ＳノードとＴノードとの座標から、上記した定義に従って楕円の各パラメータが演算され、楕円関数が決定される。
　次に、ステップ３０４で探索コストα，βが０に初期設定される。即ち、現時点では活性ノードのノードコストの最小値は０である。
　次に、ステップ３０６へ移行して、Ｓ永久ノード数はＴ永久ノード数以下か否かが判定される。そして、Ｓ永久ノード数がＴ永久ノード数以下の場合にはステップ３０８〜３２２のＳ探索が実行され、そうでない場合にはステップ３３２〜３４６のＴノード探索が実行される。このステップ３０６の処理により等ノード探索が実行される。即ち、探索現在時点において、Ｓ探索とＴ探索とにおいて永久ノードの数が均衡するように、交互に永久ノードが展開される。
　Ｓ探索の場合には、ステップ３０８にてＳ探索の全活性ノードの中からノードコストＳ（ｉ）が探索コトスα以上で最小値をとるノードが選択され、そのノードが永久ノードｍとして選択される。
　次に、ステップ３１０へ移行して、その永久ノードｍは楕円内に存在するか否かが判定され、存在しない場合には、その永久ノードｍは捨て去られ、ステップ３０６へ戻り、次の探索処理が実行される。
　又、永久ノードｍが楕円内に存在すると判定された場合には、ステップ３１２へ移行して、その永久ノードｍの後方探索枝の等級１Ｓ（ｍ）がさらに１つ後方の後方探索技の等級１Ｓ（Ｐ（ｍ））−ｎ以上か否かが判定される。そして、判定結果がＮＯの場合にはその永久ノードｍは捨て去られ、ステップ３０６へ戻り、次の探索処理が実行される。即ち、１つ後方の後方探索枝の等級よりｎ等級を越える下位等級の探索枝は選択されないことを意味しており、探索枝の選択が制限されたことになる。このステップにより縮退探索が行われる。
　ステップ３１４は、ステップ３１０の楕円探索条件とステップ３１２の縮退探索条件とを満たす場合に実行され、その選択されたノードは有効な永久ノードｍとし、そのノードコストＳ（ｍ）は永久ノードコストＳＰ（ｍ）としてノードファイルに登録される。
　次に、ステップ３１６でその永久ノードｍに接続される探索枝を地図データベースから検索し、次に接続される全ての活性ノードｋが決定される。そして、次のステップ３１８で活性ノードｋがカレントファイルに初めて展開される場合には、その永久ノードコストに展開された探索枝コストを加えた値、即ち、ＳＰ（ｍ）＋ｄｍ，ｋが活性ノードｋのノードコストＳ（ｋ）として登録される。又、展開された活性ノードｋが既にカレントファイルに展開されている活性ノードである場合には、登録されているノードコストＳ（ｋ）とＳＰ（ｍ）＋ｄｍ，ｋ　との大きさが比較され、ＳＰ（ｍ）＋ｄｍ，ｋの方が小さい場合には活性ノードｋへ至るよりコストの低い経路が発見されたことを意味しており、その場合には、その活性ノードｋのフードコストＳ（ｋ）はその値ＳＰ（ｍ）＋ｄｍ，ｋに再登録される。又、その活性ノードｋの後方ノードＰ（ｋ）をｍに再登録する。以上の処理が新しく展開された全ての活性ノードｋについて実行される。
　次に、ステップ３２２では、新しく展開された全活性ノードｋのうちＴ探索の活性ノード又は永久ノードに該当するものが有るか否かが判定される。なければ、接続ノードは発生しなかったことを意味しており、ステップ３０６に戻り、次の探索処理が実行される。
　又、ステップ３０６でＳ永久ノード数はＴ永久ノード数以下でないと判断された場合には、ステップ３３２〜ステップ３４６のＴ探索がＳ探索と全く同様に実行される。
　ところで、上記の処理内容を図示すると、第１１図に示すようになる。
　第１回目の実行サイクルでは、ステップ３０６の判断がＹＥＳとなり、ステップ３０８でＳノ一ドが永久ノードとして選択され、ステップ３１０、３１２の判定がＹＥＳとなり、ステップ３１４で永久ノードコストＳＰ（Ｓ）＝０が確定される。
　尚、１ｓ（Ｓ）＝１ｓ（Ｐ（Ｓ））＝ｎに初期設定されているので、最初の実行サイクルでは、ステップ３１０の判定は当然ＹＥＳとなる。第１１図（ａ）で示すように、ステップ３１６でノードＳに接続される探索枝が選択され、次に展開される活性ノードｋ１〜ｋ４が決定される。そして、ステップ３１８では既に展開されている活性ノードは存在しないので、新しい４つの活性ノードについてノードコストＳ（ｋ）が求められる。永久ノードコストＳＰ（Ｓ）は０であるのでノードコストＳ（ｋ）は探索枝コストｄｓ，ｋに等しくなる。又、各活性ノードｋの後方ノードＰ（ｋ）はＳノ一ドに登録される。又、ステップ３２０で探索コストαはその時の全ノードコストＳ（ｉ）の中の最小値に更新される。
　又、ステップ３２２で、第１０図（ｂ）に示すように、活性ノードｋのうちで、Ｔ探索の活性ノード、即ち、ノードＴ（現時点ではＴノ一ドしか展開されていない）に一致するものがあれば、そのノード、例えばノードｋ３は接続ノードとされ、一応、経路が構成されたのであるから、ステップ３２４以下でその経路が本当に最短経路になるか否かの判定が行われる。その処理については後述する。
　１回目の実行サイクルで接続ノードが発生しない場合について説明を続ける。
　第２回目の実行サイクルではＴ探索となり、同様な処理により、ステップ３４６の実行終了時には探索状態は、第１１図（ｃ）に示すようになる。
　第３回目の実行サイクルはＳ探索となり、ステップ３０８で現時点での活性ノードｉ（即ち、ｋ１〜ｋ４）のうちで、ノードコストＳ（ｉ）が探索コストα以上で最小値をとるノード、例えば、ノードｋ１が選択される。そのノードが楕円内に存在すれば、１Ｓ（Ｓ）がｎに初期設定されていることから、探索技Ｌ１は等級に関係なく選択されるので、ステップ３１４にてノードｋ１が永久ノードｍ１として登録され、そのノードコストＳ（ｍ１）も永久ノードコストＳＰ（ｍ１）としてノードファイルに登録される。次に、ステップ３１６にて、第１図（ｄ）に示すように、永久ノードｍ１に接続される活性ノードｋ２，ｋ９が展開される。このうち、活性ノードｋ９は新規な活性ノードであるので、ステップ３１８にて探索枝Ｌ９の探索枝コストｄｍ１，ｋ９＋永久ノードｍ１の永久ノードコストＳＰ（ｍ１）が活性ノードｋ９のノードコストＳ（ｋ９）としてカレントファイルに登録される。
　一方、活性ノードｋ２は既に展開された既活性ノードであるので、その時の既登録のノードコストＳ（ｋ２）より、新しく求められた探索枝Ｌ１０の探索枝コストｄｍ１，ｋ１０＋永久ノードｍ１の永久ノードコストＳＰ（ｍ１）の方が小さい場合には、ノードコストＳ（ｋ２）はその値に書替えられる。又、その活性ノードｋ２の後方ノードＰ（ｋ２）はノードＳからノードｍ１に書替えられる。即ち、ノードＳから活性ノードｋ２へ行くには、探索枝Ｌ２を通るより、永久ノードｍ１と探索枝Ｌ１０を通る経路の方がコストが低いことになり、その径路が最短経路となる。その時の探索ネットワークは第１１図（ｅ）に示すようになり、ステップ３２０でその状態での全活性ノード（ｋ２，ｋ３，ｋ４，ｋ９）のうちで、ノードコストＳ（ｋ）の最小値、例えば、Ｓ（ｋ３）が探索コストαの新しい値となる。　　　　　　　　　　　　　　　　　　　　
　このようにして、多数回の探索が実行されていくと、第１１図（ｆ）に示すようになり、楕円内で且つ探索枝の等級が１つ後方又は前方の探索枝の等級よりｎ等級を越える下位等級の選択枝は捨て去られた状態で永久ノードが次々と生成される。
　そして、ステップ３２２又はステップ３４６の判定がＹＥＳとなると、接続ノードが発生されたことになる。
　次に、接続ノードが発生した後の最短経路探索手順について説明する。
　初めて接続ノードが発生した状態では、第１１図（ｇ）に示すように、その接続フードはＳ探索及びＴ探索においても、活性ノードである。従って、ステップ３２４でその接続ノードｊ１におけるノードＳに対するノードコストＳ（ｊ１）とノードＴに対するノードコストＴ（ｊ１）との和で経路コストＲ（ｊ１）が演算される。そして、最初の実行サイクルでのステップ３２６での最小値ＭＲは、その経路コストＲ（ｊ１）となり、ステップ３２８にて、その最小値ＭＲが探索コストα＋探索コストβ以下か否かが判定される。最初に現れた接続ノードｊ１で条件が設立する場合は等号に限られ、ノードコストＳ（ｊ１）は探索コストαにフードコストＴ（ｊ１）は探索コストβに等しくなる。このことは、次回と次次回の探索で必ず接続ノードｊ１はＳ探索及びＴ探索で永久ノードとされる。即ち、この経路はＳ探索とＴ探索が永久ノードで接続された最初の経路となり、最小コスト経路となる。したがって、ステップ３３０でその接続ノードｊ１が存在する経路が最小コスト経路と決定される。
　一方、ステップ３２８の判定がＮＯの場合には、その後の探索において、接続ノードｊ１が永久ノードとされる前に他の経路で接続ノードが発生されたり、その接続ノードｊ１の後方ノードＰ（ｊ１）や前方ノードＱ（ｊ１）が書き換えられる、即ち、最小コスト経路が変更される可能性がある。従って、ステップ３０６へ移行して次の探索を継続する必要がある。
　又、探索が進行するに連れ、接続ノードが発生する毎に、ステップ３２４以下が実行される。ステップ３２４では、発生した接続ノードｊに対して経路コストＲ（ｊ）が演算される。そして、ステップ３２６で今までに発生している全接続ノードｊのうちで、経路コストＲ（ｊ）が最小となるものをノードｕとし、最小値ＭＲが選択される。尚、ある経路に注目したとき、その経路上の最初の接続ノードｊは必ずＳ探索及びＴ探索の活性ノードであり、その後、探索が進行するに連れ、その接続ノードはＳ探索の永久ノード又はＴ探索の永久ノードとなり、最後に両探索での永久ノードとなる。この永久ノードになった時、必ず、コストＲ（ｊ）＜α＋βが満たされる。しかし、コストＲ（ｊ）＜α十βの条件を満たしても、そのノードは両探索での永久ノードとは言えないが、その後の探索で初めての接続ノードが現れる経路の経路コストは必ず現在のα＋βを越えるため、それらの経路からは最小コスト経路は発見されない。したがって、既に接続されたＲ（ｊ）＜α＋βを満たす経路の中に最小コスト経路が存在する。したがって、全接続ノードｊに対して経路コストＲ（ｊ）の最小値ＭＲが最初にＭＲ≦α＋βを満たす経路が最小コスト経路、即ち、最短経路となる。
　上記の最短経路上の任意のノードｖはＳ探索において後方ノードＰ（ｖ）が、又、Ｔ探索において前方ノードＱ（ｖ）が明らかにされているので、接続ノードｕから順にＳ探索に対して１つづつ後方ノードをＳノードまで探り、Ｔ探索に対して１つづつ前方ノードをＴノードまで探ることによって最短経路上の全ノードを知ることができる。
　次に、目的位置が変わらず現在位置が変化した時の再探索の処理手順を第７図を参照して説明する。
　ステップ４００で新しい現在位置に対応するＳノードが探索結果データのＴ永久ノードに一致するか否かが判定される。一致すればそのＳノードは前回のＴ探索領域に存在することになり、ステップ４３４へ移行して、探索結果データに基づいて前方ノードＱ（ｖ）を順次たどることによりＴノードに至る最短経路を求めることができる。
　又、そのＳノードがＴ探索領域に存在しない場合には、ステップ４０１以下の処理が実行される。　ステップ４０１でステップ３００と同様な初期設定が行われる。但し、目的位置からの探索結果データは消去されない。又、ステップ４０２で新しい現在位置と不変な目的位置とを焦点とする楕円関数が演算され、ステップ４０４で探索コストαが０に初期設定される。又、探索コストβは前回のＴ探索の最終値に保存される。そして、ステップ４０６〜４２０のＳ探索が実行される。このＳ探索は第６図のステップ３０８〜３２２のＳ探索と同様である。但し、ステップ４２０ではＳ探索による活性ノードｋがフードファイルに探索結果データとして記憶されているＴ永久ノードか否かが判定される。
　判定結果がＮＯの場合には、ステップ４０６へ戻りＳ探索が継続される。
　又、判定結果がＹＥＳの場合には、ステップ４２２へ移行して、ステップ４２２〜４２６が実行される。この処理はステップ３２４〜３２８と同様である。そして、ステップ４２６の判定がＹＥＳとなると、ステップ４２６で、ステップ４２６の条件を満たす経路の発生回数が計数される。そして、次のステップ４３０でその発生回数Ｚが所定回数Ｗ以上か否かが判定され、所定回数以上となるまで、ステップ４０６へ戻りＳ探索が実行される。即ち、接続ノードｊはＴ永久ノードであるので、ノードコストＴ（ｊ）は探索コストβより小さい。このため、最初にステップ４２６の条件を満たす接続ノードｊであっても、ノードコストＳ（ｊ）は最小値即ち探索コストαに等しいとは限らない。したがって、その後のＳ探索において接続ノードｊが発生し経路コトスＲ（ｊ）が最小値をる経路が発生する可能性がある。そこで、所定の回数Ｗまで、ステップ４２６の条件を満たす経路を検出し、その経路の中で経路コストＲ（ｊ）が最小値をとる経路を最短経路とする必要がある。即ち、所定回数Ｗ以内に最短経路の接続が完了すると見做され、所定回数Ｗを越えてＳ探索を継続しても、最短経路が発見される可能性は少ないといえる。
　上記実施例ではステップ４２０のＳ探索の活性ノードがＴ探索の永久ノードと一致するか否かを判定したが、探索結果データをＴ探索の活性ノードを含めた探索最終状態のデータとし、Ｓ探索の活性ノードがＴ探索の永久ノード又は活性ノードと一致する接続フードが検出された後は、ステップ４２６の条件が満たされるまで、Ｔ探索とＳ探索とを同時に実行するようにすれば、ステップ４２８とステップ４３０は不要となり、ステップ４２６が初めて満たされた時に、最短経路が検出されることになる。但し、Ｔ探索は探索コストβから継続する探索となる。
　又、第５図のステップ２０８における双方向等ノード探索は、楕円探索又は、縮退探索を組み合わせた探索を行った場合、ネットワークの限定又は縮退により現在位置と目的位置とを結ぶ経路を消失し、最短経路を求められない時に、補間的に用いられる。等ノード探索だけなら、範囲を限定しないので最短経路を失うことはなく、必ず最短経路を求めることができる。　　　　　　　　　　　　　　
　双方向等ノード探索は道路網に粗密がある時、双方向等コスト探索と比べて探索時間が短縮される。これは双方向等ノード探索を行った時の探索ノード数は、双方向等コスト探索のそれに比べて少なくなることによる。その証明は、Ｓ探索側のノード密度とＴ探索側のそれを、それぞれの探索範囲内で一定であるとする時、ノード数は探索面積×ノ一ド密度であるとして求め、双方向等ノード探索を行った時の探索ノード数と双方向等コスト探索のそれと差を取り、シュワルツの不等式を用いて、その差がいつも負となることから示される。
　上記実施例装置による探索結果を次に示す。所与の領域の街路ノード数が約２８００、リンク数が約４２００の地図データベース上で複数のＳノードとＴノード対を選定し、探索を実行した。従来法の一方向探索のラベル確定法による探索結果に比べて双方向等ノード探索は最大約５倍、更に楕円探索を加えると最大約５０倍の時間短縮が得られた。更に、縮退探索を行うと楕円探索の更に数倍の時間短縮となった。
　２回目以降の探索においては、初回の探索結果データを利用しない探索に比べて２倍以上の時間短縮が得られた。
　尚、探索範囲の限定は、楕円を用いる以外に現在位置と目的位置とを中に含む矩形、或いは現在位置と目的位置を焦点とする二つの放物線で囲まれる領域でも良い。そして、現在位置と目的位置との距離の長短に応じ、これらの形状をパラメトリックに制御しても良い。
　又、ネットワークの縮退は、道路等級を設定する以外に、リンク属性値である距離、旅行時間にペナルティコストを付けることでも良い。例えば、右，左折に対しペナルティを付け、距離、旅行時間に加えることにより、右，左折方向への経路は通り難くなり、直進する方向へ探索が進み、縮退を行うと同様な効果が得られる。
　又、本発明は上記のような道路地図での最短経路探索の他、任意のネットワークにおいて、任意の評価値が最小となる経路を求める全ての装置にも応用できる。
　【発明の効果】
　第１発明は、双方向探索手段により探索方向を切換えて双方向探索を実行する過程において、各方向から順次探索される探索ノード又は探索枝の数が略均衡するように探索方向の順序を切換制御しているので、ノード又は枝の密度が異なる経路データにおいて、最短経路が発見されるまでに展開されるノード又は枝の数を最小とすることができる。したがって、最短経路探索時間を短くすることができる。
　又、第２発明は、双方向探索過程において探索される探索ノード又は探索枝を、探索開始位置及び探索終了位置、又は探索開始位置及び探索終了位置のそれぞれの近傍点を２つの焦点とし、長径に対する短径の比Ｆを焦点間距離が短い程大きくするように形状を変化させた楕円領域に制限している。
　従って、探索開始位置と探索終了位置とが大きく離れている程、それらの位置を結ぶ直線に近い経路が最短経路と考えられる可能性が大きくなる場合には、上記の手法により、探索領域をより偏平な楕円として指向性を持たせることで、探索領域を効果的に制限することができる。逆に、探索開始位置と探索終了位置との距離が短い程、２つの位置を結ぶ直線から離れた経路も最短経路になり得る可能性が大きくなる場合には、上記の手法により、探索領域の楕円を円形に近づけ指向性を排除することで、等方的な探索によりより正確な最短経路を検出することが可能となる。
　さらに、探索開始位置と探索終了位置との距離が短い程、２つの焦点を探索開始位置及び探索終了位置の外側に配置して、探索開始位置又は探索終了位置と焦点との間の距離Ｃ０を大きくすることで、探索開始位置から探索終了位置に対して遠ざかる方向の領域と、探索終了位置から探索開始位置に対して遠ざかる方向の領域をより広く含めることができる。このために、探索開始位置と探索終了位置との距離が短い場合には、より等方的な探索が可能となり、より正確な最短経路の探索を実行することができる。
　これらの結果、探索開始位置と探索終了位置との関係において、上記のように楕円の探索領域の形状を変化させているので、最短経路の存在する確率の高い領域が探索領域となり、最短経路の存在する確率が低い領域は探索領域から除外されているため、極めて効率の高い探索が可能となり最短経路探索時間が短縮される。
　又、第３発明は、双方向探索過程において探索され
る探索枝を、その探索枝が接続される既に探索されている枝の等級に対して所定の等級数より低い等級以上の枝の中から選択するようにしているので、
、その枝よりも所定等級数だけ等級の低い
　又、第４発明は、前回の探索に対して探索終了位置が同一の場合において、その探索開始位置がその最短経路上又はその探索領域内に存在するときには、既に求められている探索終了位置からの探索結果データによって探索開始位置から探索終了位置までの最短経路を決定し、探索開始位置がその最短経路上又はその探索領域内に存在しないときには、探索開始位置からのみ順次ノード又は枝を探索して最短経路を探索し、その片方向探索からの探索ノード又は探索枝が探索結果データに含まれる探索フード又は探索枝に接続された経路の中から、最短経路を決定するようにしているので、目的位置が不変な場合の２回目以後の経路探索を効率良く、したがって、最短経路探索時間を短縮することができる。
【図面の簡単な説明】
　第１図は本発明の構成を示したブロックダイヤグラム、第２図は本発明の具体的な一実施例に係る車載ナビゲーション装置を示した構成図、第３図乃至第７図は同実施例に係る装置の処理手順を示したフローチャート、第８図乃至第１１図は探索手順を示した説明図である。
１０…車載ナビゲーション装置
２０…コンピュータ
ｉ…活性ノード　ｍ…永久ノード　ｕ…接続ノード