図面 (/)

この項目の情報は公開日時点(1998年9月25日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (10)

課題

ノードリンクで構成されたネットワークにおける最短最小コスト経路コンピュータを用いて少ないメモリ容量で高速に探索する手法を求める

解決手段

ネットワーク内のノードに対して該ノードの出リンク最小コスト経路か否かを指標として記録したフラグテーブルを備え、フラグテーブルを参照して探索を行う。

概要

背景

ネットワークに関する代表的な最適化問題としては最短路問題最大流問題最小費用流問題などがある。そのうち最短路問題として広く使われている数理計画上の手法にダイクストラ法がある。以下、簡単にこの手法を説明する。

いま図1のようなネットワークがあったとする。図の丸印が節点、節点と節点を結ぶ線が枝である。ここでは、節点をノード、枝をリンクとよぶことにする。ノードとリンクの集合グラフといい、リンクに向きが有るものを有向グラフといい、無いものを無向グラフという。有向グラフは向きと長さをもっている。図1の例は有向グラフの例である。出発点のノードsから目的点のノードtへの経路で、もっとも短くなるものを見い出す問題が最短路問題である。

いま、ノードsからノードtへの最短路Pを
P={s,i,j,……、k,t}
とする。このとき、PをあるノードでP1とP2に分割した場合、部分集合P1とP2も、それぞれの集合内で最短路になっている。これを最適性の原理といい、この原理を利用して数理的に最短路を求めるアルゴリズムがダイクストラ法である。すなわち、ダイクストラ法は空集合から始めて、最短路となるノードを一つずつ求めて最短路部分集合を膨らませていき、最終的に全部のノードに対して最短路を求める方法である。以下は、プログラミングするときのアルゴリズムである。

ノードsからノードtに至るあらゆるノードの集合をV、sからjに至る最短路の長さd(j)、その最短路のノードの集合S1、その補集合S2(=V−S1)とすると、以下の方法で最短路が求まる。
(1)初期値化として、
S1←0(空集合)、S2←V
d(s)←0、d(i)←∞
とする。ここで、iはS2に含まれるノード、X←YはXをYで置き換えることを表す。

(2)S1=Vなら計算終了。
(3)S1≠Vなら、
最短路のd(i)を選び出し、
v←i
とする。d(v)はsからvに至る最短路となっているから、vをS1に含め、vをS2から外す。

(4)ノードvから出るリンク(出リンク)が次に到達する、S2に含まれるすべてのノードiに対して
d´(i)←d(v)+avi
を計算し、d(i)>d´(i) ならd(i)←d´(i) かつ p(i)←vとする。ここで、aviはノードvからノードiに至る長さ(リンクの長さ)であり、d(i)、d´(i)は出発点sからiに至る経路の長さである。この時点のd(i)は、S1内のノードからの最短路長になっている。S2にはもっと短い経路が存在する可能性はあるが、それは繰り返し計算のなかで求められることになる。
(5)ステップ(2)のステップに戻る。

以上の方法で求めたp(i)に対して、最終ノードtからp(t)をもとに逆にたどっていけば、出発ノードsまでの最短路が求まる。たとえば、図1の例を上記のアルゴリズムで求めると、
d(1)=0 d(2)=50 d(3)=70 d(4)=65 d(5)=85
p(2)= 1 p(3)= 2 p(4)= 2 p(5)= 3
となる。

s=1、t=5であるから、ノード5の前はノード3(p(5)=3)、ノード3の前はノード2(p(3)=2)、ノード2の前はノード1(p(2)=1)、すなわち出発点sにたどりつく。すなわち、最短路は1→2→3→5、その長さは85(=d(5))である。また、ノード1からノード4に至る経路(1→2→4)の長さd(4)は、やはり最短路長になっている。

実際に上記のアルゴリズムで用いた図1の経路をシミュレーションしてみるとわかるが、ノード3からノード4に至る長さd´(4)は計算しなくてもすむ。すなわち、ダイクストラ法を用いれば、総組み合わせによる最短路計算に比べて、計算量が少なくてすむ。このため、最短路問題ではダイクストラ法は広く利用されている。

概要

ノードとリンクで構成されたネットワークにおける最短最小コスト)経路をコンピュータを用いて少ないメモリ容量で高速に探索する手法を求める

ネットワーク内のノードに対して該ノードの出リンクが最小コスト経路か否かを指標として記録したフラグテーブルを備え、フラグテーブルを参照して探索を行う。

目的

効果

実績

技術文献被引用数
1件
牽制数
2件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

ノードリンクで構成されたネットワークに対して出発点から目的点に到達する組み合わせのなかで最小コストとなる経路を探索するコンピュータシステムにおいて、少なくとも前記ネットワーク内のノードに対して該ノードの出リンク最小コスト経路か否かを指標として記録したフラグテーブルを備えたことを特徴とする最小コスト経路探索システム

請求項2

ノードとリンクで構成されたネットワークに対して出発点から目的点に到達する組み合わせのなかで最小コストとなる経路を探索するコンピュータシステムにおいて、前記ネットワーク内のノードに対して該ノードの出リンクが最小コスト経路か否かを指標として記録したフラグテーブル、注目するノードの出リンクの対応を示す出リンクポインタテーブル、リンクの始点と終点のノードを示すリンク構成ノードテーブルを備えたことを特徴とする最小コスト経路探索システム。

請求項3

ノードとリンクで構成されたネットワークに対して出発点から目的点に到達する組み合わせのなかで最小コストとなる経路を探索する方法において、前記ネットワーク内のノードに対して該ノードの出リンクが最小コスト経路か否かを指標として記録したフラグテーブル、注目するノードの出リンクの対応を示す出リンクポインタテーブル、リンクの始点と終点のノードを示すリンク構成ノードテーブルを用いて、出発点から目的点までの最小コスト経路を探索することを特徴とする最小コスト経路探索方法

請求項4

ノードとリンクで構成されたネットワークに対して出発点から目的点に到達する組み合わせのなかで最小コストとなる経路を探索する方法において用いられるフラグテーブルの作成において、最小コスト経路探索アルゴリズムを用いて、目的ノードに入ってくるリンクのうちいちばん最初に到達した入リンクに印を付けるラベリング処理を行い、該ラベリングされたリンクを逆にたどって出発ノードのどの出リンクが目的ノードの最小コスト経路に寄与したかを探索する逆経路探索処理によって求まる出発ノードの出リンクに、目的ノードの最小コスト経路寄与出リンクとしてフラグを立てたデータを集成してテーブルを作成することを特徴とする最小コスト経路探索用フラグテーブル作成方法

技術分野

0001

本発明は、最短路探索や最大流探索問題などで用いられる、ノードリンクで構成されたネットワークにおける出発点から目的点までの最小コスト経路を探索する最小コスト経路検索方法およびシステムに関する。

背景技術

0002

ネットワークに関する代表的な最適化問題としては最短路問題最大流問題最小費用流問題などがある。そのうち最短路問題として広く使われている数理計画上の手法にダイクストラ法がある。以下、簡単にこの手法を説明する。

0003

いま図1のようなネットワークがあったとする。図の丸印が節点、節点と節点を結ぶ線が枝である。ここでは、節点をノード、枝をリンクとよぶことにする。ノードとリンクの集合グラフといい、リンクに向きが有るものを有向グラフといい、無いものを無向グラフという。有向グラフは向きと長さをもっている。図1の例は有向グラフの例である。出発点のノードsから目的点のノードtへの経路で、もっとも短くなるものを見い出す問題が最短路問題である。

0004

いま、ノードsからノードtへの最短路Pを
P={s,i,j,……、k,t}
とする。このとき、PをあるノードでP1とP2に分割した場合、部分集合P1とP2も、それぞれの集合内で最短路になっている。これを最適性の原理といい、この原理を利用して数理的に最短路を求めるアルゴリズムがダイクストラ法である。すなわち、ダイクストラ法は空集合から始めて、最短路となるノードを一つずつ求めて最短路部分集合を膨らませていき、最終的に全部のノードに対して最短路を求める方法である。以下は、プログラミングするときのアルゴリズムである。

0005

ノードsからノードtに至るあらゆるノードの集合をV、sからjに至る最短路の長さd(j)、その最短路のノードの集合S1、その補集合S2(=V−S1)とすると、以下の方法で最短路が求まる。
(1)初期値化として、
S1←0(空集合)、S2←V
d(s)←0、d(i)←∞
とする。ここで、iはS2に含まれるノード、X←YはXをYで置き換えることを表す。

0006

(2)S1=Vなら計算終了。
(3)S1≠Vなら、
最短路のd(i)を選び出し、
v←i
とする。d(v)はsからvに至る最短路となっているから、vをS1に含め、vをS2から外す。

0007

(4)ノードvから出るリンク(出リンク)が次に到達する、S2に含まれるすべてのノードiに対して
d´(i)←d(v)+avi
を計算し、d(i)>d´(i) ならd(i)←d´(i) かつ p(i)←vとする。ここで、aviはノードvからノードiに至る長さ(リンクの長さ)であり、d(i)、d´(i)は出発点sからiに至る経路の長さである。この時点のd(i)は、S1内のノードからの最短路長になっている。S2にはもっと短い経路が存在する可能性はあるが、それは繰り返し計算のなかで求められることになる。
(5)ステップ(2)のステップに戻る。

0008

以上の方法で求めたp(i)に対して、最終ノードtからp(t)をもとに逆にたどっていけば、出発ノードsまでの最短路が求まる。たとえば、図1の例を上記のアルゴリズムで求めると、
d(1)=0 d(2)=50 d(3)=70 d(4)=65 d(5)=85
p(2)= 1 p(3)= 2 p(4)= 2 p(5)= 3
となる。

0009

s=1、t=5であるから、ノード5の前はノード3(p(5)=3)、ノード3の前はノード2(p(3)=2)、ノード2の前はノード1(p(2)=1)、すなわち出発点sにたどりつく。すなわち、最短路は1→2→3→5、その長さは85(=d(5))である。また、ノード1からノード4に至る経路(1→2→4)の長さd(4)は、やはり最短路長になっている。

0010

実際に上記のアルゴリズムで用いた図1の経路をシミュレーションしてみるとわかるが、ノード3からノード4に至る長さd´(4)は計算しなくてもすむ。すなわち、ダイクストラ法を用いれば、総組み合わせによる最短路計算に比べて、計算量が少なくてすむ。このため、最短路問題ではダイクストラ法は広く利用されている。

発明が解決しようとする課題

0011

最短経路(最短路)を求める方法の一例として、ダイクストラ法を従来技術で説明した。これまで、最短経路の探索をコンピュータで行う場合、必要に応じてそのつど最短経路を計算する方法が採られていた。その理由は、対象が単純なネットワークであったこと、リアルタイム応答を必要としなかったこと、あらゆる出発点と到達点の経路をすべて記録することは記憶装置の記憶容量に限界があること、などが挙げられる。ダイクストラ法は効率のよい最短経路探索法ではあるが、その経路(ネットワーク)が複雑になれば、探索時にワーキングエリアとして多くのメモリ量が必要となり、探索時間も長くなる。したがって、複雑なネットワークに対してリアルタイムに最短経路を求める必要がある場合には、そのつど計算する方法は困難になる。

0012

たとえば、日本全国ネット主要幹線道路をネットワークで表すと、ノード数14,853個、リンク数は27,798である。ダイクストラ法は出発地からほぼ同心円方向に探索領域を広げるので、出発地からみて目的地方向とは反対側の領域、つまり最終的には最小コスト経路とはならない領域の探索に探索時間やワーキングエリアとしてのメモリを使ってしまう難点があり、ネットワークが大きくなると探索時間とメモリ容量の点で問題があった。

0013

このような問題を避けるために、あらかじめ最短経路を計算してノード番号でその経路をすべて記録しておくとなると、大容量のメモリが必要となる。一つのノードを番号で記録するには2バイトが必要であり、あらゆる出発地とあらゆる目的地の最短経路を2バイトで登録するとなると、膨大な記録容量が必要となる。

0014

しかも将来的にみて、主要幹線道路以外も含めるとなると、ノード番号を2バイト(2バイトの正整数で表せるノード数は約3.2万)では足りなく、4バイト(4バイトの正整数で表せるノード数は約21億)が必要となり、さらに多くの容量が要求される。しかも、これらの経路があらかじめ計算され、テーブル化されたとしても、そのテーブルを効率よく検索する手法も確立されていない。本発明が解決しようとする課題は、ネットワークにおける最短経路をコンピュータを用いて少ないメモリ容量で高速に探索する手法を求めることである。

課題を解決するための手段

0015

本発明は上記の課題を解決するために、ノードとリンクで構成されたネットワークにおける出発点から目的点に到達する組み合わせのなかで最小コストなる経路を探索するコンピュータシステムにおいて、あらゆる出発点に対して、あらゆる目的点が最小コストとなる出リンク(または入リンク)をフラグで記録するフラグテーブルを導入する。

0016

このためにあらかじめ、出発点とあらゆる目的点までの最小コスト経路を求め、各ノードにおいて最小コスト経路となる出リンクにフラグを立てたフラグテーブルを作成する。

0017

ある出発点からある目的点までの最小コスト経路を、目的ノードに対応した最小コスト経路の出リンクをフラグテーブル上でたどることによって最小コスト経路を探索することができる。なお以下では有向グラフを扱い、ノードから外に向うリンクを「出リンク」とよび、内に向うリンクを「入リンク」とよぶことにする。

0018

ここで、最小コストの「コスト」はリンクの長さ(大きさ)の総称を表すもので、必ずしも費用原価を意味しない。本発明の適用の対象となるネットワークにより異なる。たとえば交通網の場合には、時間、距離、費用など、その単位はざまざまである。

0019

出発地sから目的地tまでの最小コストを距離で求めた場合と所要時間で求めた場合とでは、当然、その経路は異なる。このように同じ対象(ネットワーク)でも、求めるコスト(この場合は単位の意味)が異なれば、結果も違う。このように異なるコスト(単位)に対しては、異なるテーブルが必要となる。

0020

本発明は、最小コスト経路を求めるアルゴリズムに関するものではない。本発明では、あらかじめ最小コスト経路を求める方法としてどのようなアルゴリズムを使用するかは問わない。ここでは、一般に広く使用されているダイクストラ法を用いて説明する。

0021

従来技術で挙げた例では、出発点sから目的点tに達する最小コスト経路は途中ノードiのノード連結p(i)のチェーニングでわかる。p(i)を2バイトのノード番号でテーブル化しておけば、最小コスト経路が検索できることになるが、それでは、テーブル容量が大きくなり、実用的でない。

0022

本発明では、フラグテーブル(指標テーブル)という概念を導入する。ノードsからノードtに至る最小コスト経路は一つであるから、ノードtに至る最小コスト経路のうち、ノードsから出るリンクは1本である。このようにあらゆるノードに対して出発ノードsの出リンクが最小コスト経路か否かをフラグ(指標)として記録したテーブルがフラグテーブルである。フラグはオンオフのいずれかでよいから、ビットで表される。

0023

これをテーブル化したものが図2である。(a)フラグテーブルは、横軸が出リンク、縦軸がノードを表す。出リンクはノードに対応している。このフラグテーブルに付随するテーブルとして、どこからどこまでが注目するノードの出リンクに対応しているかを(b)出リンクポインタテーブルで、リンクの始点と終点のノードはリンク構成ノードテーブルでわかるようになっている。

0024

図の例では、ノードsに対応する出リンクはs1〜s4である。表の丸印は、ノードsからs1〜s4に対応する縦軸のノードへ行くときの最小コストとなる出リンクを示している。たとえば、出発点s(出発ノードs)から目的点t(目的ノードt)に行く場合の最小コスト経路を探索するには、まずs1〜s4(列)とノードt(行)がクロスする領域において丸印が付いているのはs1となっているから、tへ行く最小コスト経路のリンクは出リンクs1であることがわかる。

0025

つぎに、(c)リンク構成ノードテーブルを見ると、リンクs1はノードkに接続しているから、再び出リンクポインタテーブルからノードkのフラグテーブル上の位置k1〜k2を知ることができる。さらに、出リンクk1〜k2とノードtの領域から丸印を探すと、リンクk2であることがわかる。以上の操作を繰り返していけば、最終的に目的ノードtに至るまでのリンクとノードがすべてわかることになる(図2の参考の太線が求める経路を示す)。以上の処理をHIPOにまとめたものが図3である。

0026

コンピュータ処理においては、フラグテーブル、出リンクポインタテーブル、リンク構成ノードテーブルをデータベース化しておく。中心となるフラグテーブルは○と×で表せるから、データベース上はビット表現にし、○はビットがオン(1)、×はビットがオフ(0)として表す。

0027

つぎにフラグテーブルを作成する手順を説明する。各ノードにはノードに入るリンクすなわち入リンクと、ノードから出て行くリンクすなわち出リンクがある。あらかじめ入、出リンクとノードに対してすべて連番ナンバーリングしておく。ただし、通常は入リンクは他のノードの出リンクとなっているから、ここでは出リンクを中心に考える。ノード番号は連番であり、ノードから出ている出リンクもまた連番である。

0028

上記の探索手順からもわかるように、フラグテーブルに登録された○×(データベースまたはメモリ上はビットのオン/オフ)は出発ノードuから目的ノードvに至る経路のうち、最小コスト経路となるuの出リンクのみ(1本のみ)を記録(フラグ付与)しておけばよいことになる。

0029

ダイクストラ法を用いた場合には、ノードvに入ってくるリンクのうち、どのリンクがいちばん最初に到達したかがわかるから、この入リンクに印を付けておく。これを、ラベリングとよぶ。ラベリングされたリンクを逆にたどっていけば、出発ノードuのどの出リンクが目的ノードvの最小コスト経路に寄与したかがわかる。これは従来技術で挙げたP(v)のチェーニングに相当する。したがって、逆経路探索処理によって求まるノードuの出リンクに、目的ノードvの最小コスト経路寄与出リンクとして、フラグ(丸印)を付与すればよいことになる。

0030

以上の手順を、フラグテーブルにフラグを付与する手順としてまとめたものが、図4フローチャートである。なお、図4のステップS3によってセットされるフラグの領域は図5斜線部分である。図5の例では、ノードiからノードjに至る最小コスト経路は、ノードiの出リンクi2を使えばよいことを表している。

発明を実施するための最良の形態

0031

本発明の実施の形態を図6に示すような簡単なネットワークで説明する。ノード番号は○で囲まれた数字で示し、リンク番号は○無しの数字で示してある。図4のフローチャートで示す処理によって、フラグテーブルは図7の形で求まる。図7には同時に、フラグテーブルに対応した出リンクポインタテーブルとノード構成ノードテーブルも示してある。

0032

このネットワークにおいて、出発ノード(2)から目的ノード(4)に行く最小コスト経路を求める。図3に示したHIPOに従って以下の手順で行う。ただし経路テーブルを1次元の配列P(n)とし、通るノードのみを記録することにする。

0033

(ステップ1):iをノード(2)とすると同時に、P(1)にノード(2)を保管する(初期化)。
(ステップ2):iがノード(4)なら、探索は終了(終了条件判定)。
(ステップ3):出リンクポインタテーブルより、ノードi(この時点ではノード(2))のフラグテーブル上の出リンク5〜6が求まる。
(ステップ4):目的ノード(4)に至る最小コスト経路をたどるにはノードi(この時点ではノード(2))の出リンクのどれかを、フラグテーブルより求める。出リンク5、6のうち丸印の付いているのはリンク5であることから、リンク5が選出される。

0034

(ステップ5):ノードi(この時点ではノード(2))からのリンク5の行き先は、リンク構成ノードテーブルからノード(1)がわかる。この(1)をP(2)に保存し、なおかつiに代入プログラム上はノード(2)のステップに戻ることになるが、ここでは、箇条書き的に処理を羅列する。

0035

(ステップ6):iがノード(4)でないから、処理は続行(ノード(2)の終了条件チェック)。
(ステップ7):出リンクポインタテーブルより、ノードi(この時点ではノード(1))のフラグテーブル上の出リンク1〜4が求まる((3)の処理)。
(ステップ8):目的ノード(4)に至る最小コスト経路をたどるにはノードi(この時点では(1))の出リンクのどれかを、フラグテーブルより求める。出リンク1〜4のうち丸印の付いているのはリンク1であることから、リンク1が選出される(ノード(4)の処理)。

0036

(ステップ9):ノードi(この時点ではノード(1))からのリンク1の行き先として、リンク構成ノードテーブルからノード(4)が選出される。このノード(4)をP(3)に保存し、なおかつiに代入。プログラム上はノード(2)のステップに戻ることになるが、ここでは、箇条書き的に処理を羅列する(ノード(5)の処理)。

0037

(ステップ10):ノードi(この時点ではノード(4))が目的ノード(4)であるから、探索は終了(ノード(2)の終了条件チェック)。

0038

以上の処理が終了したあと、経路テーブルPの内容は
P(1)=(2)、P(2)=(1)、P(3)=(4)
となっているから、(2)から(4)に至る最小コスト経路
(2)→(1)→(4)
が求まる。

0039

本発明の実施例として、図8の函観光システムを挙げる。このシステムの使い方は、まず出発地と出発時刻、目的地、さらに観光して回りたい観光地を指定する。途中の条件として、昼食地夕食地などが指定できる。この条件のもとに、最適な観光経路を探索する。予め各地点間最短経路情報はテーブル化されており、観光順路が求まれば、観光地と観光地をつなぐ最小コスト経路はフラグテーブルより求めることができる。

0040

図8の例では、出発地が函館(JR)、出発時刻9:00、目的地(通常、宿泊地)はホテルショコ、昼食は真マメさん、昼食時間は通常の時間帯、夕食地はかねきゅう山、夕食時刻は通常の時間帯の条件下で、函館ハリストス正教会山頂駅(函館山)、五郭、函館公園を観光先として指定している。この指定のもとに経路探索を行うと、図9の結果を得る。

0041

たとえば図9のように、
山頂駅→真マメさん→五稜郭
順番が求まると、“山頂駅(出発地)→真マメさん(目的地)”、“真マメさん(出発地)→五稜郭(目的地)”の経路はフラグテーブルの探索により、最小コスト経路が選び出せる。その結果、
山頂駅→山麓駅→十字街→函館駅(市電)→真マメさん→函館駅(市電)→五稜郭公園前→五稜郭
のように途中の通過経路が求まる。なお、ここでのコストは所要時間(リンクの長さの単位)である。

0042

経路の探索はフラグテーブルのテーブルサーチで行えるために、処理速度が速く、リアルタイムなリスポンスに十分対応できる。これまでのように最小コスト経路をダイクストラ法を用いてそのたびに計算するとなると、ダイクストラ法が効率のよい最短路解法手法といっても、かなり時間のかかる処理となる。このように、本発明の最小コスト探索手法は他のプログラムのなかの一手段としての利用も可能である。

発明の効果

0043

道路網における経路探索では、従来ダイクストラ法等の最短経路探索手法が用いられてきた。ダイクストラ法の場合、出発地と目的地を与えて最小コスト経路を探索するために、経路が求まるまでに探索の手間と探索のメモリ領域が必要となる。この方法をそのつど実行するとなると、経路探索に時間がかかるという問題点ある。とくに全国ネットの道路交通網のように複雑なネットワークに対して最小コスト経路を、インターネットなどのコンピュータネットワーク下でリアルタイムに情報提供サービスをしようとすると、応答時間が遅いために、実用化が難しかった。

0044

一方、システム的には、経路探索プログラム構築や探索中のテンポラリなメモリ領域を確保しなければならないために、その分、余分なメモリを実装しなければならなかった。このようなネットワークに対して有効な手段を提唱したものが、本発明のフラグテーブルである。フラグテーブルはノードとリンクの2次元配列ビットマップ表現しただけのものであるから、複雑なネットワークに対しても少ない容量でテーブル化できる。たとえば、フラグテーブル全体のデータ容量は
データ量(バイト)=ノード数×リンク数/8
であるから、日本全国の主要幹線道路ノード数14,583個、リンク数27,798本に対して、フラグテーブルは51.6Mバイトとなり、CD-ROMなどの記憶媒体1枚に収まる。

0045

また経路を求めるとき、データベースからメモリに必要なデータを読み込む方法を採れば、必要データは目的地のノードに対するフラグデータだけなので、“リンク数/8”バイトのデータ(図2のt行参照)を読めばよいことになる。上記の日本全国の主要幹線データの場合には、わずかに3,474バイトをメインメモリに読み込めば、最小コスト経路が求められる。しかも探索は出発ノードから順に丸印の付いた出リンクをたどっていくだけでよいから、探索が速い。

0046

このようなことから、本発明を用いることによって得られる効果は以下のとおりである。
(1)データ容量が少なくてすむから、コンピュータのメインメモリおよび外部記憶媒体への、メモリ上の負担が少ない。
(2)最小コスト経路の探索が速いために、リアルタイムの処理に対応できる。たとえばインターネットにおける、交通道路の最小コスト経路の情報サービス提供などに応用できる。

0047

(3)データ量が少なくてすむために、CD-ROMなどの外部記憶媒体に容易に収まり、このような媒体で最小コスト経路を必要とする分野の商品をCD-ROM等の媒体での提供がしやすくなる。たとえば、全国主要道路網の最小コスト経路探索ソフトとデータをCD-ROMで提供し、ユーザーが1枚のCD-ROMをもとに自宅パソコンで観光地に行く場合の、道路経路情報を探索することもできる。

0048

(4)本発明の最小コスト経路探索システムは、コストの単位を選ぶことによって、さまざまな角度からの最小コスト探索が行える。たとえば、道路網に対して実測距離、所要時間、費用の、3角度から探索したいという場合には、それぞれを単位としたフラグテーブルを作成しておけば、目的に応じた情報サービスが行える。この場合でも、フラグテーブル自体が小容量で抑えることができるから、複数のフラグテーブルをもったとしても、システム的に十分に対応できる。とくにフラグテーブルを外部記憶媒体に記録しておき、必要に応じて読み出す場合でも、目的ノードの行データだけを読み込めばよいから、メインメモリへの負荷も最小限に抑えられる。

0049

(5)リアルタイムレスポンスが必要でない分野(バッチ処理のプログラムなどの場合)でも、あらかじめ最小コスト経路が求まり、しかもそのつど計算すると処理時間がかかるプログラムなどに対しては、この処理部分を本発明の手法を用いてテーブル化し、テーブル検索の方法をとれば、メモリ的にも、また処理時間的にも、効果的なプログラムが作成できる。

図面の簡単な説明

0050

図1従来技術におけるダイクストラ法の説明図である。
図2本発明における、フラグテーブル、出リンクポインタテーブル、リンク構成ノードテーブルの説明図である。
図3本発明における、フラグテーブルから最小コスト経路を探索する手順を示したHIPOである。
図4本発明における、フラグテーブルの作成手順を示したフローチャートである。
図5本発明における、図4の処理の説明図である。
図6本発明の実施の形態における簡単なネットワークの例の説明図である。
図7本発明の実施の形態における、図6のネットワークに対するフラグテーブル、出リンクポイントテーブル、リンク構成ノードテーブルの説明図である。
図8本発明の実施例におけるシステムより表示される入力画面の一例である。
図9本発明の実施例における、図8の条件に対して探索システムが求めた最適観光経路の出力図である。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ