ナビゲーション装置及びプログラム
【課題】各グループ間の極値の比較により全体のソートを行うことでソート処理時間を短縮化させる。
【解決手段】施設を検索して案内する機能を備えたナビゲーション装置において、施設を検索する施設検索手段４ａと、検索した施設の列値を順次算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするグループ分け手段４ｂと、全グループ間の極値比較により施設全体をソートし、ソートした施設のリストを案内する制御手段４ｃとを備えている。
【解決手段】施設を検索して案内する機能を備えたナビゲーション装置において、施設を検索する施設検索手段４ａと、検索した施設の列値を順次算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするグループ分け手段４ｂと、全グループ間の極値比較により施設全体をソートし、ソートした施設のリストを案内する制御手段４ｃとを備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は施設を検索して案内するナビゲーション装置及びプログラムに関する。
【背景技術】
【０００２】
現在地周辺の施設の検索等において、検索した各施設までの直線距離を各々算出し、現在地から近い順にソートしてリスト表示するＰＯＩ（Point Of Interest)検索が知られているが、この方法では最短距離として検索された施設が車両で走行した場合には最短時間で到達できる施設ではない場合がある。そこで、ユーザが指定したジャンルの施設を検索して現在地周辺で絞り込む際、リスト表示を現在地からの距離順ではなく、個々の施設に対してルート探索を実施し、当該施設までの走行距離または到着予想時間を算出して短い順にリスト表示するものが知られている（特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００３−２３２６４１
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記特許文献の方法では、該当する施設がたくさんある場合、全ての施設に対してルート探索を行うため、探索に時間がかかってしまうとともに、ナビゲーション装置の処理装置（ＣＰＵ）の負荷が大きくなってしまう。また、一般的なＰＯＩ検索ではリスト表示において施設を距離順などに並べ替えるソート処理に時間がかかってしまっていた。
【課題を解決するための手段】
【０００５】
本発明は上記課題を解決しようとするもので、検索した施設をソートして表示する場合に、ソート処理にかかる時間を短縮化することを目的とする。
本発明は、施設を検索して案内する機能を備えたナビゲーション装置において、施設を検索する施設検索手段と、検索した施設の列値を順次算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするグループ分け手段と、全グループ間の極値比較により施設全体をソートし、ソートした施設のリストを案内する制御手段とを備えたことを特徴とする。
また、本発明は、施設を検索して案内するナビゲーション装置を制御するプログラムにおいて、施設を検索するステップ、検索した施設の列値を算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするステップ、全グループ間の極値比較により施設全体をソートし、ソートした施設のリストを案内するステップをコンピュータに実行させることを特徴とする。
【発明の効果】
【０００６】
本発明は、検索した施設をソートするための列値の大小関係により施設をグループ化してグループ内のソートを完了し、各グループ間の極値の比較により全体のソートを行うことでソート処理時間を短縮化することができる。
【図面の簡単な説明】
【０００７】
【図１】本実施形態のナビゲーション装置の例を示すブロック図である。
【図２】施設のグループ分けを説明する図である。
【図３】グループ間比較を説明する図である。
【図４】グループ分けしたときのデータ例を説明する図である。
【図５】グループ間の比較を行うときのデータ例を説明する図である。
【図６】グループ分けの処理フローを示す図である。
【図７】グループ分けの処理フローを示す図である。
【図８】グループ間比較処理フローを示す図である。
【発明を実施するための形態】
【０００８】
以下、本発明の実施の形態について説明する。
図１は本実施形態に係るナビゲーション装置の構成例を示すブロック図である。目的地、検索エリア、検索する施設名、ジャンル等の情報を入力するキーボード、マウス、タッチパネル、操作キー等からなる入力装置１、現在位置に関する情報を検出するＧＰＳ（Global Positioning System ）等からなる現在位置検出装置２、地図データ、道路データ、施設等の地点データ、経路の探索に必要なナビゲーション用データ、経路案内に必要な表示／音声の案内データ、さらに地図の表示、経路探索、音声案内等の案内を行うためのプログラム（アプリケーション及び／又はＯＳ）等を記憶する情報記憶装置３、施設名、ジャンル、エリア等を指定して施設を検索する施設検索手段４ａ、検索した施設に関し、現在位置からの距離や到達時間等のソートする値（列値）を順次算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするグループ分け手段４ｂ、グループ分けした各グループの中の列値の最小値（極値）の比較により検索した施設の全体をソートし、ソートした施設のリストを案内する制御手段４ｃを備え、ナビゲータ処理手段として地図の表示処理、経路探索処理、経路案内に必要な表示／音声案内処理、さらにシステム全体の制御を行う中央処理装置４、交通情報を送受信する通信装置５、経路案内に関する情報を出力し、制御手段４ｓから出力される施設のリストを表示するディスプレイ、スピーカその他の出力装置６から構成されている。
【０００９】
図２は施設のグループ分けを説明する図である。
ここでは「ランド」という施設名称で検索したときにヒットした施設とその座標が、ネバーランド(x1,y1) 、ネズミーランド(x2,y2) 、ランドセルハウス(x3,y3) 、健康ランド(x4,y4) 、スーバーランド(x5,y5) の５つの施設であったと仮定する。これらの施設をソートする場合、ソートするための基準として、例えば、施設までの距離、施設までの到達時間をソート値（列値）とし、その大小関係により施設をソートする。以下では、距離をソート値（列値）として説明するが、時間の場合も同様である。
【００１０】
図示のように、ネバーランド、ネズミーランド、ランドセルハウス、健康ランド、スーバーランドの各距離（列値）が、それぞれ389 、127 、3383、1184、1382と算出されたものとし、これら列値を算出しながら、直前の施設の列値と比較してグループ分けする。例えば、最初にグループＩＤ（識別情報）を「１」に設定し、ネバーランドの列値389 とネズミーランドの列値127 とを比較する。ネズミーランドの列値はネバーランドの列値（直前値）より大きくない（小さい）ので、ネバーランドとは別グループとしてグループＩＤを更新し、「２」を登録する。次いで、ランドセルハウスの列値3383をネズミーランドの127 （直前値）と比較し、ランドセルハウスの列値はネズミーランドの列値（直前値）より大きいので、ネズミーランドと同一グループとしてグループＩＤは更新せず「２」のままとする。次いで、健康ランドの列値1184をランドセルハウスの列値3383と比較すると、健康ランドの列値はランドセルハウスの列値（直前値）より大きくない（小さい）ので、ランドセルハウスとは別グループとしてグループＩＤを更新し、「３」を登録する。次いで、スーパーランドの列値1382と健康ランドの列値1184とを比較し、スーパーランドの列値は健康ランドの列値（直前値）より大きいので、健康ランドと同一グループとしてグループＩＤは更新せず「３」のままにする。
【００１１】
このように、施設の列値を直前の施設の列値と比較し、単調増加（小→大）していない場合には直前の施設とは別グループとして登録することでグループ分けを行う。このようなグルーフ分けにより、ここでは図示するように、ネバーランドのグループ、ネズミーランド、ランドセルハウスのグループ、健康ランド、ランドセルハウスのグループの３つのグループに分けられ、各グループは列値が小さい順に並び、各グループ内のソートは完了することになる。もちろん、列値が単調減少していない場合には直前の施設とは別グループとして登録することでグループ分けすることも可能であり、その場合は、各グループは列値が大きい順に並ぶことになる。
【００１２】
図３はグループ間の比較による全体のソートを説明する図である。
図２で説明したように、検索した施設の列値の大小関係に着目してグループ分けすると、列値を計算しながらグループ分けが行われて各グループ内のソートが完了する。本実施形態では各グループ内は列値が小さい順に並ぶことになり、次いで、全体をソートするためにグループ間の比較を行う。各グループ内でその先頭が最小の列値（極値）であるので、図３（ａ）に示すように、３グループの先頭の値を比較してネズミーランドの極値127 を全体の最小値として取得し、このデータを処理済みとして図３（ｂ）に示すように抹消する。ネズミーランドを抹消したグループ２では２番目のランドセルハウスの列値が最小値（極値）であるので、他のグループの極値と比較する（図３（ｂ））。この比較により、ネバーランドの極値389 が最小値であるので、これを全体の最小値として取得し、このデータを処理済みとして図３（ｃ）に示すように抹消する。次いで、グループ１は未処理のデータはないので、グループ２、グループ３との間で極値を比較し（図３（ｃ））、同様に極値同士の最小値を取得し、このデータを処理済みとして抹消していく。このような処理を全グループにおいて未処理データがなくなるまで繰り返することで、全データが列値の小さい順にソートされ、全体のソートが完了し、図３（ｄ）に示すように、列値の小さい表示順にしてリスト表示が行われる。
【００１３】
このように、本実施形態では列値を計算しながらその前後の値を比較してその大小関係で順次グループ分けすることにより、グループ分けの終了と同時に各グループ内のソートは完了し、グループ間の極値の比較のみで全体をソートすることができるので、個々のデータ全体を比較してソートするのに比して格段にソート処理にかかる時間を短縮化することができる。
【００１４】
図４は列値の比較によりグループ分けしたときのデータ例を説明する図である。
図４（ａ）の例は、上記したように、施設の列値を直前の施設の列値と比較し、単調増加していない場合には直前の施設とは別グループとし、単調増加している場合は同じグループとして順次グループＩＤを登録するデータ例を示している。
図４（ｂ）の例は、上記したようにグループ分けしたときのグループの情報（グループＩＤとそれに対応する施設の数）のみ別の所にテーブルとして持っておき、グループ情報テーブルにおける施設の先頭と、グループ分けした各施設データの先頭（列値が最小）のみ連結しておく例を示している。
【００１５】
図５はグループ間の比較を行うときのデータ例を説明する図である。
図５（ａ）は図４（ａ）のデータ例に対応し、グループ分けによりグループＩＤを登録し、これにグループ間の極値の比較により最小値を取得してデータが処理済みとなった否かの施設の数をカウントする処理済施設数の項目を付加したデータ例を示している。この処理済施設数のカウント値を参照することで、当該グループに未処理のデータが存在するか否か判別できる。これは、処理済施設数分先のデータが同一グループＩＤなのか否かで判別し、同一グループＩＤであれば未処理のデータが存在し、同一グループＩＤでなければ未処理のデータは存在しない。また、有効なデータ（これからソートする処理開始位置のデータ）へのアクセスを処理済施設数分先のデータとして参照することも可能である。
図５（ｂ）は図４（ｂ）のデータ例に対応し、グループ情報テーブルの各グループＩＤに処理済施設数の項目を付加したものである。このデータ例では、未処理のデータが存在するか否かは、施設の数と処理済施設数のカウント値を比較することで判別することができ、また、有効なデータへのアクセスは処理済施設数分先のデータとして参照することができる。
【００１６】
図６は施設の列値（距離）を直前の距離と比較し、単調増加していない場合には直前の施設とは別グループとして順次グループＩＤを登録するデータ例（図４（ａ））の場合の処理フローを示している。
先ず、グループＩＤを初期化して「１」にセットし（ステップＳ１）、比較する直前距離値を初期化（０）する（ステップＳ２）。次いで、グループ分けする対象施設データがあるか否か判断し（ステップＳ３）、ある場合はその施設までの距離を算出する（ステップＳ４）。次いで、直前のデータの距離と今回のデータの距離を比較し（ステップＳ５）、直前のデータの距離は今回のデータの距離以上か否か判断する（ステップＳ６）。一番最初のデータについては、初期値として設定された直前距離０より大きいので、グループＩＤを更新せず（グループＩＤは「１」）にステップＳ８に移行し、直前距離値を更新し（今回距離値を直前距離値とする）、グループＩＤを設定登録（ステップＳ９）して、ステップＳ３に戻り、同様の処理を繰り返す。ステップＳ６において、直前距離が今回距離以上の場合（単調増加していない）にはグループＩＤを更新（インクリメント）する（ステップＳ７）。このような処理を全データについて行い、ステップＳ３において対象施設データがなくなればグループ分け処理は終了する。上記したように、この処理でグループ分けした各グループ内は距離の小さい順に並ぶのでグループ内のソートも完了する。
【００１７】
図７は施設の列値（距離）を直前の距離と比較し、単調増加していない場合には直前の施設とは別グループとしてグループ分けしたときのグループ情報のみ別の所にテーブルとして持っておき、グループ情報とグループ分けした各施設データの先頭のみ連結しておくデータ例（図４（ｂ））の場合の処理フローを示している。
先ず、グループＩＤを初期化して「１」にセットし（ステップＳ１１）、比較する直前距離値を初期化（最大値）する（ステップＳ１２）。次いで、グループ分けする対象施設データがあるか否か判断し（ステップＳ１３）、ある場合はその施設までの距離を算出する（ステップＳ１４）。次いで、直前のデータの距離と今回のデータの距離を比較し（ステップＳ１５）、直前のデータの距離は今回のデータの距離以上か否か判断する（ステップＳ１６）。一番最初のデータについては、初期値が最大である直前距離よりは小さいので、グループＩＤを更新せず（グループＩＤは「１」）にステップＳ１８に移行し、施設の数を更新（インクリメント）し、グループＩＤ、更新した施設の数をグループ情報テーブルに登録する（ステップＳ１９）。次いで、直前距離値を更新し（今回距離値を直前距離値とする）（ステップＳ２０）、ステップＳ１３に戻り、同様の処理を繰り返す。ステップＳ１６において、直前距離が今回距離以上である（単調増加していない）場合にはグループＩＤを更新（インクリメント）（ステップＳ１７）するとともに、当該グループの施設の数を更新する。このような処理を全データについて行い、ステップＳ１３において対象施設データがなくなればグループ分け処理は終了する。以上の処理によりグループ分けした各グループ内は距離の小さい順に並ぶのでグループ内のソートは完了する。
【００１８】
図８はグループ間の比較によるソート処理フローを示す図である。この処理は図３のグループ間の比較処理に対応するもので、グループ分けは終わっていることが前提である。まず、全データが処理済みか否か判断し（ステップＳ２１）、未処理データがある場合、最小距離の初期化として最大値をセットする（ステップＳ２２）。次いで、全グループ間の距離比較処理が終了か否か判断し（ステップＳ２３）、未処理グループがある場合、当該未処理グループに未処理データがあるか否か判断し（ステップＳ２４）、未処理データかある場合、当該グループの未処理データの距離は最小か否か判断する（ステップＳ２５）。一番最初のデータの場合には、初期化でセットされた最大値との比較であるので、最小値と判断され（ステップＳ２５、Ｙ）、当該グループの未処理データの距離を最小距離とし（ステップＳ２６）、ステップＳ２３に戻って同様の処理を繰り返す。ステップＳ２４において未処理データがない場合、ステップＳ２５において未処理データの距離が最小でない場合もステップＳ２３に戻って同様の処理を繰り返す。こうして、全グループ間の距離比較が終了すると、グループ全体で最小距離となったデータを処理済みとし（ステップＳ２７）、次ぎの段階のグループ間比較のために最初に戻り、ステップＳ２１で全データが処理済みでない場合、ステップＳ２２で同様に最小距離の初期化（最大値をセット）して同様の処理を繰り返してグループ間の比較を行う。こうして、順次、最小距離となったデータを処理済みとして、全データか処理済みとなっとき処理は終了し、全体のソートが完了する。
【符号の説明】
【００１９】
１…入力装置、２…現在位置検出装置、３…情報記憶装置、４ａ…施設検索手段、４ｂ…グループ分け手段、４ｃ…制御手段、４…中央処理装置、５…通信装置、６…出力装置。
【技術分野】
【０００１】
本発明は施設を検索して案内するナビゲーション装置及びプログラムに関する。
【背景技術】
【０００２】
現在地周辺の施設の検索等において、検索した各施設までの直線距離を各々算出し、現在地から近い順にソートしてリスト表示するＰＯＩ（Point Of Interest)検索が知られているが、この方法では最短距離として検索された施設が車両で走行した場合には最短時間で到達できる施設ではない場合がある。そこで、ユーザが指定したジャンルの施設を検索して現在地周辺で絞り込む際、リスト表示を現在地からの距離順ではなく、個々の施設に対してルート探索を実施し、当該施設までの走行距離または到着予想時間を算出して短い順にリスト表示するものが知られている（特許文献１）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００３−２３２６４１
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記特許文献の方法では、該当する施設がたくさんある場合、全ての施設に対してルート探索を行うため、探索に時間がかかってしまうとともに、ナビゲーション装置の処理装置（ＣＰＵ）の負荷が大きくなってしまう。また、一般的なＰＯＩ検索ではリスト表示において施設を距離順などに並べ替えるソート処理に時間がかかってしまっていた。
【課題を解決するための手段】
【０００５】
本発明は上記課題を解決しようとするもので、検索した施設をソートして表示する場合に、ソート処理にかかる時間を短縮化することを目的とする。
本発明は、施設を検索して案内する機能を備えたナビゲーション装置において、施設を検索する施設検索手段と、検索した施設の列値を順次算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするグループ分け手段と、全グループ間の極値比較により施設全体をソートし、ソートした施設のリストを案内する制御手段とを備えたことを特徴とする。
また、本発明は、施設を検索して案内するナビゲーション装置を制御するプログラムにおいて、施設を検索するステップ、検索した施設の列値を算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするステップ、全グループ間の極値比較により施設全体をソートし、ソートした施設のリストを案内するステップをコンピュータに実行させることを特徴とする。
【発明の効果】
【０００６】
本発明は、検索した施設をソートするための列値の大小関係により施設をグループ化してグループ内のソートを完了し、各グループ間の極値の比較により全体のソートを行うことでソート処理時間を短縮化することができる。
【図面の簡単な説明】
【０００７】
【図１】本実施形態のナビゲーション装置の例を示すブロック図である。
【図２】施設のグループ分けを説明する図である。
【図３】グループ間比較を説明する図である。
【図４】グループ分けしたときのデータ例を説明する図である。
【図５】グループ間の比較を行うときのデータ例を説明する図である。
【図６】グループ分けの処理フローを示す図である。
【図７】グループ分けの処理フローを示す図である。
【図８】グループ間比較処理フローを示す図である。
【発明を実施するための形態】
【０００８】
以下、本発明の実施の形態について説明する。
図１は本実施形態に係るナビゲーション装置の構成例を示すブロック図である。目的地、検索エリア、検索する施設名、ジャンル等の情報を入力するキーボード、マウス、タッチパネル、操作キー等からなる入力装置１、現在位置に関する情報を検出するＧＰＳ（Global Positioning System ）等からなる現在位置検出装置２、地図データ、道路データ、施設等の地点データ、経路の探索に必要なナビゲーション用データ、経路案内に必要な表示／音声の案内データ、さらに地図の表示、経路探索、音声案内等の案内を行うためのプログラム（アプリケーション及び／又はＯＳ）等を記憶する情報記憶装置３、施設名、ジャンル、エリア等を指定して施設を検索する施設検索手段４ａ、検索した施設に関し、現在位置からの距離や到達時間等のソートする値（列値）を順次算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするグループ分け手段４ｂ、グループ分けした各グループの中の列値の最小値（極値）の比較により検索した施設の全体をソートし、ソートした施設のリストを案内する制御手段４ｃを備え、ナビゲータ処理手段として地図の表示処理、経路探索処理、経路案内に必要な表示／音声案内処理、さらにシステム全体の制御を行う中央処理装置４、交通情報を送受信する通信装置５、経路案内に関する情報を出力し、制御手段４ｓから出力される施設のリストを表示するディスプレイ、スピーカその他の出力装置６から構成されている。
【０００９】
図２は施設のグループ分けを説明する図である。
ここでは「ランド」という施設名称で検索したときにヒットした施設とその座標が、ネバーランド(x1,y1) 、ネズミーランド(x2,y2) 、ランドセルハウス(x3,y3) 、健康ランド(x4,y4) 、スーバーランド(x5,y5) の５つの施設であったと仮定する。これらの施設をソートする場合、ソートするための基準として、例えば、施設までの距離、施設までの到達時間をソート値（列値）とし、その大小関係により施設をソートする。以下では、距離をソート値（列値）として説明するが、時間の場合も同様である。
【００１０】
図示のように、ネバーランド、ネズミーランド、ランドセルハウス、健康ランド、スーバーランドの各距離（列値）が、それぞれ389 、127 、3383、1184、1382と算出されたものとし、これら列値を算出しながら、直前の施設の列値と比較してグループ分けする。例えば、最初にグループＩＤ（識別情報）を「１」に設定し、ネバーランドの列値389 とネズミーランドの列値127 とを比較する。ネズミーランドの列値はネバーランドの列値（直前値）より大きくない（小さい）ので、ネバーランドとは別グループとしてグループＩＤを更新し、「２」を登録する。次いで、ランドセルハウスの列値3383をネズミーランドの127 （直前値）と比較し、ランドセルハウスの列値はネズミーランドの列値（直前値）より大きいので、ネズミーランドと同一グループとしてグループＩＤは更新せず「２」のままとする。次いで、健康ランドの列値1184をランドセルハウスの列値3383と比較すると、健康ランドの列値はランドセルハウスの列値（直前値）より大きくない（小さい）ので、ランドセルハウスとは別グループとしてグループＩＤを更新し、「３」を登録する。次いで、スーパーランドの列値1382と健康ランドの列値1184とを比較し、スーパーランドの列値は健康ランドの列値（直前値）より大きいので、健康ランドと同一グループとしてグループＩＤは更新せず「３」のままにする。
【００１１】
このように、施設の列値を直前の施設の列値と比較し、単調増加（小→大）していない場合には直前の施設とは別グループとして登録することでグループ分けを行う。このようなグルーフ分けにより、ここでは図示するように、ネバーランドのグループ、ネズミーランド、ランドセルハウスのグループ、健康ランド、ランドセルハウスのグループの３つのグループに分けられ、各グループは列値が小さい順に並び、各グループ内のソートは完了することになる。もちろん、列値が単調減少していない場合には直前の施設とは別グループとして登録することでグループ分けすることも可能であり、その場合は、各グループは列値が大きい順に並ぶことになる。
【００１２】
図３はグループ間の比較による全体のソートを説明する図である。
図２で説明したように、検索した施設の列値の大小関係に着目してグループ分けすると、列値を計算しながらグループ分けが行われて各グループ内のソートが完了する。本実施形態では各グループ内は列値が小さい順に並ぶことになり、次いで、全体をソートするためにグループ間の比較を行う。各グループ内でその先頭が最小の列値（極値）であるので、図３（ａ）に示すように、３グループの先頭の値を比較してネズミーランドの極値127 を全体の最小値として取得し、このデータを処理済みとして図３（ｂ）に示すように抹消する。ネズミーランドを抹消したグループ２では２番目のランドセルハウスの列値が最小値（極値）であるので、他のグループの極値と比較する（図３（ｂ））。この比較により、ネバーランドの極値389 が最小値であるので、これを全体の最小値として取得し、このデータを処理済みとして図３（ｃ）に示すように抹消する。次いで、グループ１は未処理のデータはないので、グループ２、グループ３との間で極値を比較し（図３（ｃ））、同様に極値同士の最小値を取得し、このデータを処理済みとして抹消していく。このような処理を全グループにおいて未処理データがなくなるまで繰り返することで、全データが列値の小さい順にソートされ、全体のソートが完了し、図３（ｄ）に示すように、列値の小さい表示順にしてリスト表示が行われる。
【００１３】
このように、本実施形態では列値を計算しながらその前後の値を比較してその大小関係で順次グループ分けすることにより、グループ分けの終了と同時に各グループ内のソートは完了し、グループ間の極値の比較のみで全体をソートすることができるので、個々のデータ全体を比較してソートするのに比して格段にソート処理にかかる時間を短縮化することができる。
【００１４】
図４は列値の比較によりグループ分けしたときのデータ例を説明する図である。
図４（ａ）の例は、上記したように、施設の列値を直前の施設の列値と比較し、単調増加していない場合には直前の施設とは別グループとし、単調増加している場合は同じグループとして順次グループＩＤを登録するデータ例を示している。
図４（ｂ）の例は、上記したようにグループ分けしたときのグループの情報（グループＩＤとそれに対応する施設の数）のみ別の所にテーブルとして持っておき、グループ情報テーブルにおける施設の先頭と、グループ分けした各施設データの先頭（列値が最小）のみ連結しておく例を示している。
【００１５】
図５はグループ間の比較を行うときのデータ例を説明する図である。
図５（ａ）は図４（ａ）のデータ例に対応し、グループ分けによりグループＩＤを登録し、これにグループ間の極値の比較により最小値を取得してデータが処理済みとなった否かの施設の数をカウントする処理済施設数の項目を付加したデータ例を示している。この処理済施設数のカウント値を参照することで、当該グループに未処理のデータが存在するか否か判別できる。これは、処理済施設数分先のデータが同一グループＩＤなのか否かで判別し、同一グループＩＤであれば未処理のデータが存在し、同一グループＩＤでなければ未処理のデータは存在しない。また、有効なデータ（これからソートする処理開始位置のデータ）へのアクセスを処理済施設数分先のデータとして参照することも可能である。
図５（ｂ）は図４（ｂ）のデータ例に対応し、グループ情報テーブルの各グループＩＤに処理済施設数の項目を付加したものである。このデータ例では、未処理のデータが存在するか否かは、施設の数と処理済施設数のカウント値を比較することで判別することができ、また、有効なデータへのアクセスは処理済施設数分先のデータとして参照することができる。
【００１６】
図６は施設の列値（距離）を直前の距離と比較し、単調増加していない場合には直前の施設とは別グループとして順次グループＩＤを登録するデータ例（図４（ａ））の場合の処理フローを示している。
先ず、グループＩＤを初期化して「１」にセットし（ステップＳ１）、比較する直前距離値を初期化（０）する（ステップＳ２）。次いで、グループ分けする対象施設データがあるか否か判断し（ステップＳ３）、ある場合はその施設までの距離を算出する（ステップＳ４）。次いで、直前のデータの距離と今回のデータの距離を比較し（ステップＳ５）、直前のデータの距離は今回のデータの距離以上か否か判断する（ステップＳ６）。一番最初のデータについては、初期値として設定された直前距離０より大きいので、グループＩＤを更新せず（グループＩＤは「１」）にステップＳ８に移行し、直前距離値を更新し（今回距離値を直前距離値とする）、グループＩＤを設定登録（ステップＳ９）して、ステップＳ３に戻り、同様の処理を繰り返す。ステップＳ６において、直前距離が今回距離以上の場合（単調増加していない）にはグループＩＤを更新（インクリメント）する（ステップＳ７）。このような処理を全データについて行い、ステップＳ３において対象施設データがなくなればグループ分け処理は終了する。上記したように、この処理でグループ分けした各グループ内は距離の小さい順に並ぶのでグループ内のソートも完了する。
【００１７】
図７は施設の列値（距離）を直前の距離と比較し、単調増加していない場合には直前の施設とは別グループとしてグループ分けしたときのグループ情報のみ別の所にテーブルとして持っておき、グループ情報とグループ分けした各施設データの先頭のみ連結しておくデータ例（図４（ｂ））の場合の処理フローを示している。
先ず、グループＩＤを初期化して「１」にセットし（ステップＳ１１）、比較する直前距離値を初期化（最大値）する（ステップＳ１２）。次いで、グループ分けする対象施設データがあるか否か判断し（ステップＳ１３）、ある場合はその施設までの距離を算出する（ステップＳ１４）。次いで、直前のデータの距離と今回のデータの距離を比較し（ステップＳ１５）、直前のデータの距離は今回のデータの距離以上か否か判断する（ステップＳ１６）。一番最初のデータについては、初期値が最大である直前距離よりは小さいので、グループＩＤを更新せず（グループＩＤは「１」）にステップＳ１８に移行し、施設の数を更新（インクリメント）し、グループＩＤ、更新した施設の数をグループ情報テーブルに登録する（ステップＳ１９）。次いで、直前距離値を更新し（今回距離値を直前距離値とする）（ステップＳ２０）、ステップＳ１３に戻り、同様の処理を繰り返す。ステップＳ１６において、直前距離が今回距離以上である（単調増加していない）場合にはグループＩＤを更新（インクリメント）（ステップＳ１７）するとともに、当該グループの施設の数を更新する。このような処理を全データについて行い、ステップＳ１３において対象施設データがなくなればグループ分け処理は終了する。以上の処理によりグループ分けした各グループ内は距離の小さい順に並ぶのでグループ内のソートは完了する。
【００１８】
図８はグループ間の比較によるソート処理フローを示す図である。この処理は図３のグループ間の比較処理に対応するもので、グループ分けは終わっていることが前提である。まず、全データが処理済みか否か判断し（ステップＳ２１）、未処理データがある場合、最小距離の初期化として最大値をセットする（ステップＳ２２）。次いで、全グループ間の距離比較処理が終了か否か判断し（ステップＳ２３）、未処理グループがある場合、当該未処理グループに未処理データがあるか否か判断し（ステップＳ２４）、未処理データかある場合、当該グループの未処理データの距離は最小か否か判断する（ステップＳ２５）。一番最初のデータの場合には、初期化でセットされた最大値との比較であるので、最小値と判断され（ステップＳ２５、Ｙ）、当該グループの未処理データの距離を最小距離とし（ステップＳ２６）、ステップＳ２３に戻って同様の処理を繰り返す。ステップＳ２４において未処理データがない場合、ステップＳ２５において未処理データの距離が最小でない場合もステップＳ２３に戻って同様の処理を繰り返す。こうして、全グループ間の距離比較が終了すると、グループ全体で最小距離となったデータを処理済みとし（ステップＳ２７）、次ぎの段階のグループ間比較のために最初に戻り、ステップＳ２１で全データが処理済みでない場合、ステップＳ２２で同様に最小距離の初期化（最大値をセット）して同様の処理を繰り返してグループ間の比較を行う。こうして、順次、最小距離となったデータを処理済みとして、全データか処理済みとなっとき処理は終了し、全体のソートが完了する。
【符号の説明】
【００１９】
１…入力装置、２…現在位置検出装置、３…情報記憶装置、４ａ…施設検索手段、４ｂ…グループ分け手段、４ｃ…制御手段、４…中央処理装置、５…通信装置、６…出力装置。
【特許請求の範囲】
【請求項１】
施設を検索して案内する機能を備えたナビゲーション装置において、
施設を検索する施設検索手段と、
検索した施設の列値を順次算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするグループ分け手段と、
全グループ間の極値比較により施設全体をソートし、ソートした施設のリストを案内する制御手段と、
を備えたナビゲーション装置。
【請求項２】
前記グループ分け手段は、算出した列値を直前の列値と比較し、単調変化していない場合に、これらの施設を別グループとする請求項１記載のナビゲーション装置。
【請求項３】
前記制御手段は、全グループ間で最小の極値の施設を処理済みとして抹消後、グループ間の再度の極値比較を順次行う請求項１記載のナビゲーション装置。
【請求項４】
前記制御手段は、各グループに処理済施設数のデータを付加し、処理済施設数のデータを参照して有効なデータへのアクセスを行う請求項２記載のナビゲーション装置。
【請求項５】
前記列値は、距離または時間である請求項１乃至４いずれか１項記載のナビゲーション装置。
【請求項６】
施設を検索して案内するナビゲーション装置を制御するプログラムにおいて、
施設を検索するステップ、
検索した施設の列値を算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするステップ、
全グループ間の極値比較により施設全体をソートし、ソートした施設のリストを案内するステップ、
をコンピュータに実行させることを特徴とするプログラム。
【請求項１】
施設を検索して案内する機能を備えたナビゲーション装置において、
施設を検索する施設検索手段と、
検索した施設の列値を順次算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするグループ分け手段と、
全グループ間の極値比較により施設全体をソートし、ソートした施設のリストを案内する制御手段と、
を備えたナビゲーション装置。
【請求項２】
前記グループ分け手段は、算出した列値を直前の列値と比較し、単調変化していない場合に、これらの施設を別グループとする請求項１記載のナビゲーション装置。
【請求項３】
前記制御手段は、全グループ間で最小の極値の施設を処理済みとして抹消後、グループ間の再度の極値比較を順次行う請求項１記載のナビゲーション装置。
【請求項４】
前記制御手段は、各グループに処理済施設数のデータを付加し、処理済施設数のデータを参照して有効なデータへのアクセスを行う請求項２記載のナビゲーション装置。
【請求項５】
前記列値は、距離または時間である請求項１乃至４いずれか１項記載のナビゲーション装置。
【請求項６】
施設を検索して案内するナビゲーション装置を制御するプログラムにおいて、
施設を検索するステップ、
検索した施設の列値を算出し、算出した列値を直前の列値と比較してその大小関係により施設を順次グループ分けするステップ、
全グループ間の極値比較により施設全体をソートし、ソートした施設のリストを案内するステップ、
をコンピュータに実行させることを特徴とするプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１０−２３０５２２（Ｐ２０１０−２３０５２２Ａ）
【公開日】平成２２年１０月１４日（２０１０．１０．１４）
【国際特許分類】
【出願番号】特願２００９−７８８７３（Ｐ２００９−７８８７３）
【出願日】平成２１年３月２７日（２００９．３．２７）
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
【公開日】平成２２年１０月１４日（２０１０．１０．１４）
【国際特許分類】
【出願日】平成２１年３月２７日（２００９．３．２７）
【出願人】（０００１００７６８）アイシン・エィ・ダブリュ株式会社 (3,717)
【Ｆターム（参考）】
[ Back to top ]