【手続補正書】
【提出日】平成24年12月12日(2012.12.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
電子地図に近道を追加するための、コンピュータによって実施される方法において、上記電子地図が複数のリンク及び複数のノードを含み、上記電子地図内のリンクの少なくとも一部が、該リンクを通過する際のコスト及び該リンクに関係付けられたリンク優先順位レベルを有しており、上記リンク優先順位レベルが、所定の数のリンク優先順位レベルの内の一つを表しており、より高いリンク優先順位レベルが、より重要なリンクを表している、上記方法が、
上記電子地図の複数のノード及び複数のリンクを記憶する記憶段階であって、各リンクには、上記リンク優先順位レベル及び該リンクを通過する際の上記コストが関係付けられている、上記記憶段階と、
プロセッサを用いて上記複数のリンクに沿って上記複数のノードを探査する探査段階であって、上記リンクに関係付けられた上記コストを使用して、どのノードが使用可能でないかを決定することを含み、第１の経路に沿って探査されたノードについて、もし該ノードからの後戻りではない全ての前進リンクが、より低いコストを有する第２の経路を経て既に探査されている別のノードに至る場合には、上記第１の経路に沿って探査されたノードは、使用可能でないと決定する、上記探査段階と、
上記探査中に通過され且つ使用可能でないと決定されたノードで終了しない上記リンクに対して新たなリンク優先順位レベルを形成する形成段階であって、上記新たなリンク優先順位レベルが以前のリンク優先順位レベルよりも高い、上記形成段階と、
複数の複合リンクを構築する構築段階であって、上記複合リンクが、上記新たなリンク優先順位レベルをもつ１つ以上のリンクを含み、各複合リンクが、複数のリンクに沿っての経路を表すリンクである、上記構築段階と、
上記複合リンクを上記電子地図に記憶する複合リンクを記憶する段階とからなり、上記複数の複合リンクが上記近道を表わすことを特徴とするコンピュータによって実施される方法。
【請求項２】
上記ノードに対するノード優先順位レベルを上記電子地図に記憶する記憶段階と、
新たなリンク優先順位レベルを有する１つ以上の上記リンクにより接続された上記ノードの集合体に対して新たなノード優先順位レベルを形成する形成段階と、
上記新たなノード優先順位レベルを上記電子地図に記憶する記憶段階と、
を更に含む請求項１に記載の方法。
【請求項３】
上記探査中に通過したＵターンを含む経路に対して１つ以上のＵターン指示を記憶し、新たなリンク優先順位レベルを形成する上記形成段階は、上記記憶されたＵターン指示に関連した経路上のリンクを考慮しない請求項２に記載の方法。
【請求項４】
元の地図ファイルを受け取る段階を更に含み、この元の地図ファイルは、上記電子地図における上記ノードを含み、上記新たなノード優先順位レベルを上記電子地図に記憶する上記段階及び上記複合リンクを記憶する上記段階は、新たなファイルを発生することを含み、そしてこの新たなファイルは、上記新たなノード優先順位レベル、上記複合リンク、及び上記元の地図ファイルからの上記電子地図の上記ノードを含む請求項２に記載の方法。
【請求項５】
複合リンクを構築する上記構築段階は、少なくとも探査レベルのリンクの選択まで次々のリンクに沿って通過しそしてその通過した次々のリンクに沿った移動を表す新たなリンクを構築することを含む請求項２に記載の方法。
【請求項６】
上記探査段階は、
探査の前にノードの集合体に対する使用可能度を無限大に設定し、
探査中に特定ノードへ通過するときにその特定ノードの使用可能度をチェックし、
上記特定ノードが使用可能でない場合には上記特定ノードの使用可能度を変更し、
上記特定ノードが使用可能でない場合には上記特定ノードの背後にある１つ以上のノードに対して使用可能度をチェックし、そして
上記特定ノードの背後にある上記１つ以上のノードの適当なノードが使用可能でない場合には、上記特定ノードの背後にある上記１つ以上のノードの適当なノードに対して上記使用可能度を変更する、
という段階を含む請求項２に記載の方法。
【請求項７】
新たなリンク優先順位を形成する上記形成段階は、
上記探査段階中に訪問されそして現在の探査レベル以上の優先順位レベルにある第１ノードグループを識別し、
経路に沿って上記第１ノードグループへと後方追跡し、そして
上記経路に沿って、優先順位が上記現在の探査レベルより１レベル低いものに等しい上記第１ノードグループへ至るリンクに対し、優先順位を現在の探査レベルに変更する、
という段階を含む請求項２に記載の方法。
【請求項８】
新たなノード優先順位を形成する上記形成段階は、
考慮中のノードに対して前方リンクを検査し、
上記検査段階に基づいて、選択される最大優先順位レベルを決定し、そして
上記決定された最大優先順位が現在の探査レベルより低い場合には、上記新たなノード優先順位を上記決定された最大優先順位に設定する、
という段階を含む請求項２に記載の方法。
【請求項９】
前方リンクを検査し、最大優先順位レベルを決定しそして上記新たなノード優先順位を設定する上記段階は、現在の探査レベルにある各ノードに対して実行される請求項８に記載の方法。
【請求項１０】
上記探査段階、新たなリンク優先順位レベルを形成する形成段階、新たなノード優先順位レベルを形成する形成段階、そして複合リンクを構築する上記構築段階は、複数の探査レベルの各々において実行される請求項２に記載の方法。
【請求項１１】
現在の探査レベルにおいて上記探査段階が実行される前に現在の探査レベルにおいて各ノードを識別する段階を更に含み、上記探査段階は、この識別段階で識別された各ノードにおいて実行される請求項１０に記載の方法。
【請求項１２】
プロセッサ読み取り可能なコードが記録されたプロセッサ読み取り可能な記憶媒体において、上記プロセッサ読み取り可能なコードは、
電子地図の複数のノード及び複数のリンクを記憶する記憶段階であって、各リンクには、リンク優先順位レベル及び該リンクを通過する際のコストが関係付けられている、上記記憶段階と、
プロセッサを用いて上記複数のリンクに沿って上記複数のノードを探査する探査段階であって、上記リンクに関係付けられた上記コストを使用して、どのノードが使用可能でないかを決定することを含み、第１の経路に沿って探査されたノードについて、もし該ノードからの第１の経路に沿っての後戻りではない全ての前進リンクが、より低いコストを有する第２の経路を経て既に探査されている別のノードに至る場合には、上記第１の経路に沿って探査されたノードは、使用可能でないと決定する、上記探査段階と、
上記探査中に通過され且つ使用可能でないと決定されたノードで終了しない上記リンクに対して新たなリンク優先順位レベルを形成する形成段階であって、上記新たなリンク優先順位レベルが以前のリンク優先順位レベルよりも高い、上記形成段階と、
複数の複合リンクを構築する構築段階であって、上記複合リンクが、上記新たなリンク優先順位レベルをもつ１つ以上のリンクを含み、各複合リンクが、複数のリンクに沿っての経路を表すリンクである、上記構築段階と、
上記複合リンクを上記電子地図に記憶し、上記複合リンクが近道を表わす、という段階とを含む方法を実行するようにプロセッサをプログラミングするためのものであることを特徴とするプロセッサ読み取り可能な記憶媒体。
【請求項１３】
入力デバイスと、
プロセッサ読み取り可能な記憶媒体と、
上記入力デバイス及び上記プロセッサ読み取り可能な記憶媒体と通信するプロセッサとを備え装置において、上記プロセッサ読み取り可能な記憶媒体は、
電子地図の複数のノード及び複数のリンクを記憶する記憶段階であって、各リンクには、上記リンク優先順位レベル及び該リンクを通過する際のコストが関係付けられている、上記記憶段階と、
プロセッサを用いて上記複数のリンクに沿って上記複数のノードを探査する探査段階であって、上記リンクに関係付けられた上記コストを使用して、どのノードが使用可能でないかを決定することを含み、第１の経路に沿って探査されたノードについて、もし該ノードからの後戻りではない全ての前進リンクが、より低いコストを有する第２の経路を経て既に探査されている別のノードに至る場合には、上記第１の経路に沿って探査されたノードは、使用可能でないと決定する、上記探査段階と、
上記探査中に通過され且つ使用可能でないと決定されたノードで終了しない上記リンクに対して新たなリンク優先順位レベルを形成する形成段階であって、上記新たなリンク優先順位レベルが以前のリンク優先順位レベルよりも高い、上記形成段階と、
複数の複合リンクを構築する構築段階であって、上記複合リンクが、上記新たなリンク優先順位レベルをもつ１つ以上のリンクを含み、各複合リンクが、複数のリンクに沿っての経路を表すリンクである、上記構築段階と、
上記複合リンクを上記電子地図に記憶し、上記複合リンクが近道を表わす、という段階とを含む方法を実行するように支援プロセッサをプログラミングするコードを記憶することを特徴とする装置。