"複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを前記区画ごとに探索する区画ルート探索手段を備え、前記区画ルート探索手段は、出発地点を含む区画である出発区画において、前記出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを前記出発区画におけるルートに設定する出発ルート探索手段と、出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、前記中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを前記中間区画におけるルートに設定する中間ルート探索手段と、目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを前記目的区画におけるルートに設定する目的ルート探索手段と、を備え、前記複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれ、前記中間ルート探索手段は、前記中間区画が前記代表設定区画であって、前記進入地点が前記代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを前記中間区画におけるルートに設定することを特徴とするナビゲーション装置。請求項1に記載のナビゲーション装置であって、前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、目的地点の位置に応じて選択した出口を退出地点に設定することを特徴とするナビゲーション装置。請求項2に記載のナビゲーション装置であって、前記代表ルートの出口は、前記区画の外縁を形成する複数の辺のいずれかに位置し、前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、前記中間区画における基準位置に対する目的地点の方角に対応する辺に位置する出口を、前記目的地点の位置に応じた出口として選択することを特徴とするナビゲーション装置。請求項2又は請求項3に記載のナビゲーション装置であって、前記中間ルート探索手段は、前記代表ルートの出口が複数存在する場合には、目的地点との距離が最も近い出口を、前記目的地点の位置に応じた出口として選択することを特徴とするナビゲーション装置。請求項1から請求項4までのいずれか1項に記載のナビゲーション装置であって、前記出発ルート探索手段は、前記出発区画が前記代表設定区画である場合には、代表ルートの出口を退出地点に設定することを特徴とするナビゲーション装置。請求項1から請求項5までのいずれか1項に記載のナビゲーション装置であって、出発地点から目的地点までのルートを前記区画ルート探索手段とは異なる方法で探索する代替ルート探索手段と、前記区画ルート探索手段により探索された第1のルートを、前記代替ルート探索手段により探索された第2のルートに差し替える差替手段と、を更に備えることを特徴とするナビゲーション装置。請求項6に記載のナビゲーション装置であって、前記差替手段は、前記第1のルートを前記第2のルートに差し替えるか否かをユーザに選択させることを特徴とするナビゲーション装置。請求項6又は請求項7に記載のナビゲーション装置であって、前記代表ルートと異なる前記第2のルートが走行されたことを条件として、前記第2のルートを前記代表ルートとして登録する登録手段を更に備えることを特徴とするナビゲーション装置。複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを前記区画ごとに探索するルート探索方法であって、出発地点を含む区画である出発区画において、前記出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを前記出発区画におけるルートに設定する出発ルート探索ステップと、出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、前記中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを前記中間区画におけるルートに設定する中間ルート探索ステップと、目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを前記目的区画におけるルートに設定する目的ルート探索ステップと、を備え、前記複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれ、前記中間ルート探索ステップでは、前記中間区画が前記代表設定区画であって、前記進入地点が前記代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを前記中間区画におけるルートに設定することを特徴とするルート探索方法。前述した特許文献1に記載のルート探索の手法は、階層構造に整備された地図データを必要とするものであり、地図データが階層構造に整備されていない場合には適用することができなかった。本発明は、こうした問題にかんがみてなされたものであり、階層構造に整備されていない地図データを用いてルート探索に要する時間を短縮するための技術を提供することを目的としている。請求項1に記載のナビゲーション装置は、複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを区画ごとに探索する区画ルート探索手段を備える。具体的には、この区画ルート探索手段は、出発ルート探索手段、中間ルート探索手段及び目的ルート探索手段を備える。出発ルート探索手段は、出発地点を含む区画である出発区画において、出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発区画におけるルートに設定する。中間ルート探索手段は、出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間区画におけるルートに設定する。目的ルート探索手段は、目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを目的区画におけるルートに設定する。また、複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれる。そして、中間ルート探索手段は、中間区画が代表設定区画であって、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを中間区画におけるルートに設定する。このような構成によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、ルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。ここで、代表ルートの出口が複数存在する場合には、請求項2に記載のように、目的地点の位置に応じて選択した出口を退出地点に設定するようにしてもよい。このようにすれば、目的地点に応じた適切なルートを設定することが可能となる。具体的には、請求項3に記載のように、代表ルートの出口は、区画の外縁を形成する複数の辺のいずれかに位置し、中間ルート探索手段は、代表ルートの出口が複数存在する場合には、中間区画における基準位置に対する目的地点の方角に対応する辺に位置する出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、目的地点の方角に応じた適切なルートを設定することが可能となる。また、請求項4に記載のように、中間ルート探索手段は、代表ルートの出口が複数存在する場合には、目的地点との距離が最も近い出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、目的地点へ向かった適切なルートを設定することができる。また、請求項5に記載のように、出発ルート探索手段は、出発区画が代表設定区画である場合には、代表ルートの出口を退出地点に設定するようにしてもよい。つまり、出発地点から代表ルートの出口までのルートを探索するのである。このようにすれば、出口があらかじめ設定されているため、総当たりの手法でルートを探索するとしても探索の手間や時間を大幅に短縮することができる。しかも、出発区画の退出地点を進入地点とする中間区画において、進入地点を代表ルートの入口に位置させることができるため、以降の区画における探索の処理負荷を抑えることができる。また、請求項6に記載のように、代替ルート探索手段及び差替手段を更に備え、代替ルート探索手段が、出発地点から目的地点までのルートを区画ルート探索手段とは異なる方法で探索し、差替手段が、区画ルート探索手段により探索された第1のルートを、代替ルート探索手段により探索された第2のルートに差し替えるようにしてもよい。このようにすれば、第2のルートと比較して短時間で探索可能な第1のルートを最初に提示し、その後に第1のルートと比較して信頼性の高い第2のルートに差し替えるといったことが可能となる。ただし、第1のルートが第2のルートに差し替えられることをユーザが望まない場合も考えられる。そこで、請求項7に記載のように、差替手段は、第1のルートを第2のルートに差し替えるか否かをユーザに選択させるようにしてもよい。このようにすれば、ユーザの意に反して第1のルートが第2のルートに差し替えられてしまうことを防ぐことができる。また、代表ルートに代えて第2のルートが走行される場合には、その第2のルートを代表ルートとした方がユーザにとって好ましい場合もある。そこで、請求項8に記載のように、登録手段を更に備え、この登録手段が、代表ルートと異なる第2のルートが走行されたことを条件として、第2のルートを代表ルートとして登録するようにしてもよい。このようにすれば、代表ルートをユーザに応じた適切なルートに更新することができる。次に、請求項9に記載のルート探索方法は、複数の区画に分割された地図を表す地図データを用いて、出発地点から目的地点までのルートを区画ごとに探索する方法であって、出発ルート探索ステップ、中間ルート探索ステップ及び目的ルート探索ステップを備える。出発ルート探索ステップでは、出発地点を含む区画である出発区画において、出発区画を退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発区画におけるルートに設定する。中間ルート探索ステップでは、出発地点及び目的地点を含まない区画であって他の区画で設定された退出地点を進入地点とする中間区画において、中間区画を退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間区画におけるルートに設定する。目的ルート探索ステップでは、目的地点を含む区画であって他の区画で設定された退出地点を進入地点とする目的区画において、進入地点から目的地点までのルートを探索して、探索したルートを目的区画におけるルートに設定する。また、複数の区画には、区画を通過するルートとして代表ルートが設定された代表設定区画が含まれる。そして、中間ルート探索ステップでは、中間区画が代表設定区画であって、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定し、その代表ルートを中間区画におけるルートに設定する。このような方法によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、ルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。以下、本発明が適用された実施形態について、図面を用いて説明する。図1は、実施形態のナビゲーション装置の概略構成を示すブロック図である。このナビゲーション装置は、車両に搭載されて用いられるものであり、位置検出部11、地図データ記憶部15、操作部16、表示部17、音声出力部18、制御部19などを備える。位置検出部11は、GPSGlobalPositioningSystem用の人工衛星からの送信信号を受信し、車両の位置座標や高度を検出するGPS受信機12と、車両に加えられる回転運動の角速度に応じた検出信号を出力するジャイロスコープ13と、車両の走行距離を出力する距離センサ14とを備える。そして、これらの各センサ12~14の出力信号に基づいて制御部19が、現在位置、方位、速度等を算出する。地図データ記憶部15は、地図データを記憶し、その各種データを制御部19に入力する。地図データ記憶部15に格納されるデータは、交差点等の特定地点に対応するノード及びノード間を接続するリンクによって道路の接続状況を示す道路データや、地図上の施設に関する施設データ、ルート案内を行うための案内データなどを含む各種データである。操作部16は、ユーザからの各種指示各種の設定や機能実行の指示を入力するためのものであり、表示部17の表示画面上に配置されたタッチパネルや、メカニカルなキースイッチ等が用いられる。表示部17は、液晶ディスプレイ等の表示画面を有するものであり、制御部19からの映像信号の入力に応じて各種画像を表示画面に表示する。この表示部17は、地図画像の表示や、出発地点から目的地点までの誘導ルート、車両の現在位置を示すマーク、その他の案内情報等の表示に用いられる。音声出力部18は、各種情報を音声にてユーザに報知する。これによって、表示部17による表示と音声出力部18による音声出力との両方でユーザに対して各種ルート案内を行うことができる。制御部19は、CPU、ROM、RAM、I/O及びこれらの構成を接続するバスライン等からなる周知のマイクロコンピュータを中心に構成されている。そして、CPUは、ROMに記憶されているプログラムに従い、位置検出部11、地図データ記憶部15、操作部16から入力された各種情報に基づき、各種処理を実行する。具体的には、制御部19は、地図データ記憶部15に記憶されている地図データを用いて、現在位置出発地点から目的地点までのルートを探索するルート探索処理を実行する。本実施形態で用いられる地図データは、図2に示すように、複数のセル一定サイズの正方形の区画に分割されており、制御部19は、出発地点から目的地点までのルートを、次の1~3の手順でセルごとに探索する。1出発地点を含むセル以下出発セルともいう。において、その出発セルを退出する退出地点を目的地点の位置に応じて設定する。そして、その出発地点から、設定した退出地点までのルートを探索し、探索したルートをその出発セルにおけるルートに設定する。2出発地点及び目的地点を含まないセルであって、他のセルで設定された退出地点を進入地点とするセル以下中間セルともいう。において、その中間セルを退出する退出地点を目的地点の位置に応じて設定する。そして、その進入地点から、設定した退出地点までのルートを探索し、探索したルートをその中間セルにおけるルートに設定する。3目的地点を含むセルであって他のセルで設定された退出地点を進入地点とするセル以下目的セルともいう。において、その進入地点から目的地点までのルートを探索し、探索したルートをその目的セルにおけるルートに設定する。このように制御部19は、1セル分の地図データを順に読み込み、セルごとにルートを探索することで、出発地点から目的地点までのルートを探索する。ただし、セル内において総当たりの手法でルートを探索すると、ルート探索に要する時間が長くなる。特に、すべてのセルにおいて総当たりの手法でルートを探索すると、セル数に比例して探索時間が増大してしまう。そこで、本実施形態では、図2に示すように、各セルにおいて、例えば幹線道路などのように、走行案内するルートに適した一部の道路が、代表ルートセルの拡大図において太線で示されたルートとしてあらかじめ設定されている。各セルにおける代表ルートの入口及び出口は、セルの外縁を形成する4つの辺北側、西側、南側及び東側の各方角に対応する辺のいずれかに位置し、あるセルにおける代表ルートの出口は、その出口が位置する辺で隣接する他のセルにおける代表ルートの入口となる。また、代表ルートの設定されたセル以下代表設定セルともいう。には、図3A,Bに示すように、セルにおける各方角の辺を基準とした代表ルートの入口と出口との対応関係が記憶されている。例えば、図3Aに示すセルの場合、代表ルートの入口又は出口となり得る箇所が、東側、南側及び北側の3箇所に存在する。そして、このセルでは、図3Bに示すように、東側を入口とした場合の出口が南側の1箇所、南側を入口とした場合の出口が東側及び北側の2箇所、北側を入口とした場合の出口が南側の1箇所に設定され、かつそれら出口に至るためのルートがそれぞれ一意に定義されている。なお、東側を入口とした場合の出口を北側及び南側の2箇所に設定してもよく、同様に、北側を入口とした場合の出口を東側及び南側の2箇所に設定してもよい。このように、代表設定セルでは、代表ルートの入口と出口との対応関係が設定されているため、代表ルートの入口に対応する出口を選択するだけで、入口から出口へ至るルートを考慮することなく最短ルートであるか否かは問わず、ルートを設定することが可能となる。そして、セルにおける代表ルートの出口を、隣接するセルにおける代表ルートの入口として、代表ルートを順につないでいくことにより、短時間でルートを設定することができる。ここで、このような処理を実現するために制御部19が実行する具体的処理内容について説明する。図4は、制御部19が実行するルート探索処理のフローチャートである。このルート探索処理は、ルート探索を開始する操作がユーザにより操作部16で行われることにより開始される。制御部19は、ルート探索処理を開始すると、まずS101で、目的地点をユーザに設定させる。続いてS102で、階層構造の地図データが使用可能であるか否かを判定する。すなわち、地図データ記憶部15に記憶される地図データが、階層構造に整備されたものであるか否かを判定する。例えば、ナビゲーション装置が複数の国で使用されるものであり、国によって地図データの構造が異なるような場合に、このような判定が有効となる。なお、階層構造に整備されていない地図データを用いることが決まっている場合には、S102の判定処理を行うことなくS104へ移行するようにしてもよい。そして、S102で、階層構造の地図データが使用可能であると判定した場合には、S103へ移行して、階層構造の地図データを使用してルートを設定した後、S111へ移行する。この場合のルート設定は、従来技術をそのまま適用すればよいため、具体的な説明は省略する。一方、S102で、階層構造の地図データが使用可能でないと判定した場合には、前述したS103の処理に代えて、S104~S110の処理を実行する。すなわち、まずS104で、出発地点通常は現在位置を含むセルを処理対象のセル以下対象セルという。に設定する。続いてS105では、対象セルのルート設定に代表ルートを使用可能である対象セルに代表ルートが設定されているか否かを判定する。このS105で、対象セルのルート設定に代表ルートを使用可能であると判定した場合には、S106へ移行して、代表ルートを使用してルートを設定するためのルート設定処理を実行した後、S108へ移行する。ここで、図4のS106で実行されるルート設定処理の詳細について図5のフローチャートを用いて説明する。制御部19は、ルート設定処理を開始すると、まずS201で、対象セルへの進入地点が、その対象セルに設定されている代表ルートの入口に位置しているか否かを判定する。なお、対象セルへの進入地点とは、前回の対象セルの退出地点後述のことである。ただし、対象セルに出発地点が含まれる場合には、その出発地点を進入地点として処理を行う。そして、図6Aに例示するように、S201で、対象セルへの進入地点が代表ルートの入口に位置していると判定した場合には、S202へ移行し、対象セルを基準とした目的地点の方角を判定する。本実施形態では、対象セルの中心位置を基準とした目的地点の方角が、北東~北西北東含む、北西~南西北西含む、南西~南東南西含む、南東~北東南東含むの4つの範囲のいずれに分類されるかを判定する。そして、S202で目的地点の方角が北東~北西北東含むに分類されると判定した場合には、S203へ移行し、進入地点を入口とする代表ルートの出口のうち、対象セルにおける北側の辺に設定された出口を退出地点に設定する。その後、S207へ移行する。また、S202で目的地点の方角が北西~南西北西含むに分類されると判定した場合には、S204へ移行し、代表ルートの出口のうち、対象セルにおける西側の辺に設定された出口を退出地点に設定する。その後、S207へ移行する。また、S202で目的地点の方角が南西~南東南西含むに分類されると判定した場合には、S205へ移行し、代表ルートの出口のうち、対象セルにおける南側の辺に設定された出口を退出地点に設定する。その後、S207へ移行する。また、S202で目的地点の方角が南東~北東南東含むに分類されると判定した場合には、S206へ移行し、代表ルートの出口のうち、対象セルにおける東側の辺に設定された出口を退出地点に設定する。その後、S207へ移行する。S207では、進入地点から退出地点までの代表ルートを、対象セルのルートに設定し、図5のルート設定処理を終了する。このように、進入地点が代表ルートの入口に位置する場合には、ルート計算を行うことなく、目的地点の方角に応じた出口を選択するだけでルートが設定される。なお、目的地点の方角に代表ルートの出口が存在しない場合には、他の方角の出口の中から、目的地点の方角に近い方角の出口を選択するようにしてもよい。また、対象セルへの進入地点の方角から遠い方角の出口を選択するようにしてもよい。例えば、対象セルへの進入地点が西側、目的地点が南の方角であって、対象セルにおける南側の辺に出口が設定されていない場合には、東側の辺に設定された出口目的地点の方角に近い方角であって、進入地点の方角から遠い方角を優先的に選択する。また、目的地点との距離が最も近い出口を、目的地点の位置に応じた出口として選択するようにしてもよい。このようにすれば、代表ルートの出口の数が同じ方角に2つ以上存在するような場合にも、目的地点の位置に応じた1つの出口として選択することができるため、目的地点へ向かった適切なルートを設定することができる。一方、図6Bに例示するように、S201で、対象セルへの進入地点が代表ルートの入口に位置していないと判定した場合には、S208へ移行し、総当たりの手法でルート探索を行い、対象セルのルートを設定した後、図5のルート設定処理を終了する。なお、この場合の退出地点も、目的地点の位置に応じて例えば目的地点との距離が最も近い出口などに設定される。特に、この退出地点を代表ルートの出口から選択するようにすれば、次回の対象セルの進入地点を代表ルートの入口に位置させることができる。つまり、進入地点から対象セルの代表ルートの出口までのルート探索を行うのである。こうすれば、出口があらかじめ設定されているため、総当たりの手法でルート探索するとしても探索の手間、時間を大幅に短縮することができる。とりわけ対象セルが出発セルである場合、すなわち進入地点が出発地点通常は現在位置である場合、この方法をとれば、それ以後の探索の手間、時間を容易に節約できる。図4に戻り、S105で対象セルのルート設定に代表ルートを使用可能でないと判定した場合には、S107へ移行し、前述したS208と同様、総当たりの探索処理を実施して対象セルのルートを設定した後、S108へ移行する。S108では、設定したルートの出口退出地点が位置する辺で現在の対象セルに隣接するセルを、次の対象セルに設定する。続いてS109では、設定した対象セルに目的地点が含まれているか否かを判定し、含まれていない中間セルであると判定した場合には、S105へ戻り、前述した処理S105~S108を行う。一方、S109で対象セルに目的地点が含まれている目的セルであると判定した場合には、S110へ移行し、総当たりの探索処理を実施して対象セルのルート進入地点から目的地点までのルートを設定する。これにより、出発地点から目的地点までのルートが設定される。続いて、S111では、こうして設定したルートを必要に応じて別のルートに差し替えるルート差替処理を実行し、図4のルート探索処理を終了する。ここで、図4のS111で実行されるルート差替処理の詳細について図7のフローチャートを用いて説明する。制御部19は、ルート差替処理を開始すると、まずS301で、代表ルートを使用したルート設定処理S106を行ったか否かを判定し、ルート設定処理を行っていないと判定した場合には、図7のルート差替処理を終了する。一方、S301で、代表ルートを使用したルート設定処理を行ったと判定した場合には、S302へ移行し、総当たりの手法での出発地点から目的地点までのルート探索を、バックグラウンドで実行する。続いて、S303では、設定済みのルート代表ルートを使用して設定したルートを、バックグラウンドで探索したルート総当たりの手法で探索したルートに差し替えるか否かをユーザに確認する。そして、ルートを差し替えるための操作がユーザにより行われた場合には、S304へ移行し、設定済みのルートをバックグラウンドで探索したルートに差し替えた後、S305へ移行する。一方、ルートを差し替えないための操作がユーザにより行われた場合には、そのままS305へ移行する。S305では、地図データにおいて設定されている代表ルートを必要に応じて更新するための代表ルート更新処理を実行し、ルート差替処理を終了する。ここで、図7のS305で実行される代表ルート更新処理の詳細について図8のフローチャートを用いて説明する。制御部19は、代表ルート更新処理を開始すると、まずS401で、出発地点を含むセルを対象セルに設定する。続いてS402では、対象セルの代表ルートとバックグラウンドで探索したルートとが同じであるか否かを判定し、同じでないと判定した場合には、S403へ移行して、バックグラウンドで探索したルートを車両が実際に走行したか否かを判定する。そして、S403でバックグラウンドで探索したルートを走行したと判定した場合には、S404へ移行し、対象セルの代表ルートをバックグラウンドで探索したルートに更新する。一方、S402で対象セルの代表ルートとバックグラウンドで探索したルートとが同じであると判定した場合や、S403でバックグラウンドで探索したルートを走行していないと判定した場合には、代表ルートを更新せずにS405へ移行する。S405では、次のセルを対象セルに設定する。続いてS406では、対象セルに目的地点が含まれているか否かを判定し、含まれていないと判定した場合には、S402へ戻り、前述した処理S402~S405を行う。一方、S406で対象セルに目的地点が含まれていると判定した場合には、図8の代表ルート更新処理を終了する。次に、ルート探索の具体例について、図2を用いて説明する。1セルAセルA出発セルにおいては、出発地点が代表ルートの入口に位置していないためS201:NO、総当たりの手法でルート探索が行われるS208。具体的には、代表ルートの出口この例では北側1箇所及び南側1箇所の合計2箇所のうち、目的地点との距離が最も近い出口北側の出口が、セルAを退出する退出地点として設定される。そして、出発地点から退出地点までのルートが探索され、探索されたルートがセルAにおけるルートとして設定される。2セルBセルAの退出地点を進入地点とするセルB中間セルにおいては、進入地点が代表ルートの入口に位置しているためS201:YES、この代表ルートがセルBにおけるルートとして設定されるS202~S207。具体的には、代表ルートの出口この例では北側1箇所及び西側1箇所の合計2箇所のうち、目的地点に近い方角に存在する出口北側の出口が、セルBを退出する退出地点として設定される。3セルCセルBの退出地点を進入地点とするセルC中間セルにおいても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルCにおけるルートとして設定される。具体的には、代表ルートの出口この例では北側1箇所、西側1箇所及び東側1箇所の合計3箇所のうち、目的地点の方角に存在する出口東側の出口が、セルCを退出する退出地点として設定される。4セルDセルCの退出地点を進入地点とするセルD中間セルにおいても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルDにおけるルートとして設定される。具体的には、代表ルートの出口この例では東側1箇所のうち、目的地点の方角に存在する出口東側の出口が、セルDを退出する退出地点として設定される。5セルEセルDの退出地点を進入地点とするセルE中間セルにおいても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルEにおけるルートとして設定される。具体的には、代表ルートの出口この例では北側1箇所、南側1箇所及び東側1箇所の合計3箇所のうち、目的地点の方角に存在する出口北側の出口が、セルEを退出する退出地点として設定される。6セルFセルEの退出地点を進入地点とするセルF中間セルにおいても、進入地点が代表ルートの入口に位置しているため、この代表ルートがセルFにおけるルートとして設定される。具体的には、代表ルートの出口この例では東側1箇所のうち、目的地点の方角に存在する出口東側の出口が、セルFを退出する退出地点として設定される。7セルGセルFの退出地点を進入地点とするセルG目的セルにおいては、進入地点から目的地点までのルート探索が、総当たりの手法で行われ、探索されたルートがセルGにおけるルートとして設定されるS110。このようにして、出発地点から目的地点までのルートが設定される。以上説明したように、本実施形態のナビゲーション装置は、複数のセルに分割された地図を表す地図データを用いて、出発地点から目的地点までのルートをセルごとに探索するS104~S110。具体的には、出発地点を含むセルである出発セルにおいて、出発セルを退出する退出地点を目的地点の位置に応じて設定し、出発地点から退出地点までのルートを探索して、探索したルートを出発セルにおけるルートに設定するS104~S109。そして、出発地点及び目的地点を含まないセルであって他のセルで設定された退出地点を進入地点とする中間セルにおいて、中間セルを退出する退出地点を目的地点の位置に応じて設定し、進入地点から退出地点までのルートを探索して、探索したルートを中間セルにおけるルートに設定するS104~S109。さらに、目的地点を含むセルであって他のセルで設定された退出地点を進入地点とする目的セルにおいて、進入地点から目的地点までのルートを探索して、探索したルートを目的セルにおけるルートに設定するS110。また、複数のセルには、セルを通過するルートとして1つ以上の代表ルートが設定された代表設定セルが含まれる。そして、中間セルが代表設定セルであってS105:YES、進入地点が代表ルートの入口である場合にはS201:YES、その代表ルートの出口を退出地点に設定し、その代表ルートを中間セルにおけるルートに設定するS202~S207。このようなルート探索方法によれば、進入地点が代表ルートの入口である場合には、その代表ルートの出口を退出地点に設定することで、総当たりでルートを探索する処理を省略することができる。このため、ルート探索に要する時間を短縮することができる。また、目的地点の位置に応じて選択した出口をセルの退出地点に設定するようにしているためS202~S206、代表ルートの出口が複数存在する場合にも、目的地点に応じた適切なルートを設定することが可能となる。具体的には、代表ルートの出口は、正方形のセルの4つの辺のいずれかに位置し、代表ルートの出口が複数存在する場合には、中間セルにおける基準位置本実施形態では中心位置に対する目的地点の方角に対応する辺に位置する出口を、目的地点の位置に応じた出口として選択するS202~S206。このため、目的地点の方角に応じた適切なルートを設定することが可能となる。また、代表ルートを使用して設定した第1のルートとは別に、出発地点から目的地点までの第2のルートを総当たりの探索処理で探索しS302、第1のルートを第2のルートに差し替えるS304。このため、第2のルートと比較して短時間で探索可能な第1のルートを最初に提示し、その後に第1のルートと比較して信頼性の高い第2のルートに差し替えるといったことが可能となる。特に、第1のルートを第2のルートに差し替えるか否かをユーザに選択させるようにしているためS303、ユーザの意に反して第1のルートが第2のルートに差し替えられてしまうことを防ぐことができる。加えて、代表ルートと異なる第2のルートが走行された場合にS402:NO,S403:YES、第2のルートを代表ルートとして登録するようにしているためS404、代表ルートをユーザに応じた適切なルートに更新することができる。なお、本実施形態では、S104~S110が、区画ルート探索手段としての処理の一例に相当し、特に、S104~S109が、出発ルート探索手段及び中間ルート探索手段としての処理出発ルート探索ステップ及び中間ルート探索ステップの一例に相当し、S110が、目的ルート探索手段としての処理目的ルート探索ステップの一例に相当する。また、S302が、代替ルート探索手段としての処理の一例に相当し、S304が、差替手段の一例に相当し、S305が、登録手段の一例に相当する。また、出発セル、中間セル、目的セル及び代表設定セルが、出発区画、中間区画、目的区画及び代表設定区画の一例にそれぞれ相当する。以上、本発明の実施形態について説明したが、本発明は、上記実施形態に限定されることなく、種々の形態を採り得ることは言うまでもない。1上記実施形態では、バックグラウンドで探索したルート代表ルートとは異なるルートが走行された場合に、代表ルートを更新するようにしているが、これに限定されるものではない。例えば、バックグラウンドで探索したルートのセルにおける入口及び出口の各方角が、代表ルートの入口及び出口の各方角と同じであることを条件に加えてもよい。このようにすれば、セルにおける代表ルートの入口及び出口の数各方角における数を一定に保ちつつ代表ルートを更新することができる。また、代表ルートを更新する既存の代表ルートを削除して新規の代表ルートを記憶することに代えて、代表ルートを追加する既存の代表ルートを削除せずに新規の代表ルートを記憶するようにしてもよい。2上記実施形態では、セルの中心位置を基準として目的地点の方角を判定するようにしているが、これに限定されるものではなく、例えば、セルへの進入地点を基準として目的地点の方角を判定するようにしてもよい。"