JPH01144120A - 階層化ネットワークルート探索装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、道路のようなノードとパスから構成される
ネットワークの最短ルート探索問題に適用でき、高速に
探索可能な階層化ネットワークルート探索装置に関する
ものである。

（従来の技術） ノードとパスから構成されるネットワークの異なる２ノ
ード間の最短ルートを探索する問題は、我々の日常生活
にしばしば登場する。例えば大都市の地下鉄網で、ある
地点からある地点に至る最短ルートを求める問題がそれ
にあたる。この最短ルートを探索するアルゴリズムにつ
いては、すでにいくつかの研究があり、例えばＷｉｎｓ
ｔｏｎ著、長尾他訳、「人工知能」　（培風館）、４．
１節「基本探索Ｊ　　（ｐｐ、９９〜１０１）が詳しい
。

ネットワークの構成要素は、ノードとパスである。

第６図において、１はノードを示す。ここでは、Ａ、Ｂ
等がノード名称であり、地下鉄網では駅がノードに相当
する。２はパスであり、地下鉄網では隣接した２つの駅
の間の線路である。以後、本明細書では、ＡＢ間のパス
を名称ｒＡ　ＢＪとして扱う。第６図は地下鉄ネットワ
ークとして、各パスの長さが示しである。最短経路を求
めるには、このルートを構成する各パスの長さを合計し
た値が最小となることが望まれる。このように、ルート
選択のための評価値計算のもとどなる各パス固有の属性
を本明細書では「属性値」と呼ぶことにする。

第６図のネットワークの最短ルートは以下のようにして
求める。ただし、ＡとＨの間のルートを求めるとし、探
索はＡから開始する。Ａからルートを延ばして行き、ノ
ードによる分岐があると、ルートも複数に分岐しながら
延ばす、現在延ばしているルートの先端ノードを本明細
書では「フロンティア」と呼ぶ。探索の途中では、フロ
ンティアは、通常、複数個存在する。フロンティアが終
端（第６図ではＨ）に到達し、しかもフロンティアまで
到達していない他の全てのルートの各延長距離が、終端
まで到達しているルートよりも大となれば探索は終了し
、終端に到達しているルートが求める最短パスである。

第７図には展開中のルートを■〜■として示した。この
場合には、ハツチを施したノード（Ｅ。

Ｆ、Ｄ）がフロンティアとなる。

従来のアルゴリズムは以下のようになる。

（１）　　フロンティアを持つ全てのルートの中で、長
さ（ルートを構成するパスの属性値の合計）が最小のル
ートを選択し、これをＲとしてＲのフロンティアをＦと
する。

（２）　　ノードＦに接続する各パス毎に、ルートを分
岐延長し、各パスの（Ｆとは反対側の）ノードをフロン
ティアの集合に加える。旧フロンティアＦをフロンティ
ア集合から抹消する。各パスの長さをＲの長さに加えた
ものが、新しい各ルートの延長である。ただし、「フロ
ンティアエ終端」の時には、フロンティアの集合には含
めるが、その後の延長対象とはせず、その評価値を暫定
解（ルート）の評価値として記憶する。

（３）終端まで到達したルートがなければ（１）に戻る
。さもなければ、　（４）に飛ぶ。

（４）　　フロンティアまで到達していない他の全ての
ルートの各延長距離が、終端まで到達しているルートよ
りも大であれば　（５）へ行く。さもなければ　（１）
へ戻る。

（５）　　終了 ただし、上記アルゴリズムで探索途中のルートが他のル
ートと合流した場合には、評価値の小さなルートを優先
し、評価値の大きなルートを展開中止する必要がある。

第６図により具体的なステップを説明する。ただし、Ｆ
Ｌはフロンティアの集合を表し、Ｒ３は探索中のルート
の集合を表す。（Ａ　　Ｂ）はＡとＢからなるリストを
表す記号であり、リストの要素からなる集合を表すため
に使用する。ＮＩＬは何もないことを示す。（Ａ　　Ｂ
　　Ｃ，５）はＡからＢを経由してＣへ行くルートを表
し、最後の「５」はこのルートの評価値（ここでは長さ
）である。なお、Ｓ１〜Ｓフは各ステップを示す。

ＳＯ，Ａを探索の開始点とする。

ＦＬ←（Ａ）　　　Ｒ３←ＮＩＬ Ｓｌ、ＡからＢとＣヘルート延長 ＦＬ←（Ｂ　　Ｃ） ＲＳ←（（Ａ　　Ｂ　　３）　　（Ａ　　Ｃ２））２ル
ート（Ａ　　Ｂ）　　（Ａ　　Ｃ）の中、評価値の小さ
な（Ａ　　Ｃ）を次に延長する。

Ｓ２．ＣからＥとＤヘルート延長 ＦＬ←（Ｂ　　Ｅ　　Ｄ） Ｒ３−（（Ａ　　Ｂ　　３）　（Ａ　　ＣＥ　　５）（
Ａ　　ＣＤ　　５）） 例えば（Ａ　　ＣＥ）の評価値は、Ａ、Ｃの２ＫｍとＣ
Ｅの３Ｋｍの合計である。

３ルート（Ａ　　Ｂ）（Ａ　　ＣＥ）（Ａ　　ＣＤ）の
中、評価値の小さな（Ａ　　Ｂ）を次に延長する。

Ｓ３．ＢからＥとＦヘルート延長 ＦＬ←　（Ｅ　　　Ｆ　　　Ｄ） ＲＳ←（（Ａ　　　Ｂ　　　Ｅ　　　５）（Ａ　　　Ｃ
Ｅ　　　５）（Ａ　　　Ｂ　　　Ｆ　　　６）（Ａ　　
　ＣＤ　　　５））ここで、Ｅをフロンティアとするル
ートが２本あり、その評価値が同一のため無作為に（Ａ
ＣＥ　　５）を抹消する。

２ルート（Ａ　　Ｂ　　Ｅ）　　（Ａ　　ＣＤ）は評価
値が同一なので、無作為に（Ａ　　ＣＤ）を次の展開候
補とする。

Ｓ４．ＤからＨヘルートを延ばす ＦＬ−（ＥＦＨ） Ｒ３−（（Ａ　　Ｂ　　Ｅ　　５）（Ａ　　Ｂ　　Ｆ　
　６）（Ａ　　ＣＤ　　Ｈ９）） 終端Ｈに到達したので、暫定の解候補を（ＡＣＤ　　Ｈ
）とする。その評価値は９である。

他の展開途中のルート（Ａ　　Ｂ　　Ｅ　　５）（ＡＢ
　　Ｆ　　６）の評価値の最小値は５で、暫定解の評価
値９より小さいので、ルートの展開を続行する。下線を
付したルートは終端ノードまで到達し、延長対象外のル
ートである。

３つのルート中で、評価値の小さな（Ａ　　ＢＥ　　５
）を次の展開候補とする。

Ｓ５．ＥからＦ、Ｇヘルートを延ばす。ここで、Ｅから
Ｃへのルートは、遠くなることが分るので展開しない。

ＦＬ←（Ｆ　　Ｇ　　Ｈ） ＲＳ←（（Ａ　　Ｂ　　Ｅ　　Ｆ　　７）（Ａ　　Ｂ　
　ａ６）（Ａ　　Ｂ　　Ｆ　　６）（Ａ　　ＣＤ　　Ｈ
旦）） ここで、Ｆをフロンティアとするルートが２本あり、そ
の評価値の大きい（Ａ　　Ｂ　　Ｅ　　Ｆ７）を抹消す
る。展開中のルートの評価値が９より小のため、探索を
続行する。

２ルート（Ａ　　Ｂ　　Ｅ　　Ｇ）（Ａ　　Ｂ　　Ｆ）
は評価値が同一なので、無作為に（Ａ　　Ｂ　　Ｆ）を
次の展開候補とする。

Ｓ６．ＦからＨヘルートを延ばす。

ＦＬ←（Ｇ　　Ｈ） ＲＳ←（（Ａ　　Ｂ　　Ｅ　　Ｇ　　６）（Ａ　　Ｂ　
　ＦＨ９）（Ａ　　　ＣＤ　　　Ｈ９）） 展開中のルートの評価値が９より小のため、探索を続行
する。

暫定解の評価値９よりも小さな評価値を持つルートは（
Ａ　　Ｂ　　Ｅ　　Ｇ）のみ。

Ｓ７．ＧからＨヘルートを延ばす ＦＬ←（Ｈ） フロンティアはＨのみで、最小の延長を持つルートは（
Ａ　　Ｂ　　Ｅ　　Ｇ　　Ｈ）である。

〔探索終了〕

以上の既存のアルゴリズムでは、７回のルート展開を実
行している。

第８図には従来の技術のネットワークルート探索装置を
示す。１０はネットワークルート探索機構であり、ワー
キングメモリ部１１と探索機構１２から構成される。ワ
ーキングメモリ部１１は人工知能技術の分野でｒフレー
ム」としてよく知られた形式で実現されており、各ノー
ドを表すフレーム３０および各パスを表すフレーム４０
を保持している。３１はフレームの名称であり、ここで
はフレームの名称、すなわちノード名称は「Ｃ」である
。各ノードに対応するフレーム３０は、各々ｒノードク
ラス」に属する「インスタンス」と呼称され、インスタ
ンスフレーム３０の上位には、クラスを表すクラスフレ
ーム２０が置かれ、クラスフレーム２０とインスタンス
フレーム３０の間にはポインタによる接続が張られてい
る。パスのクラスフレーム２１の配下にも複数のパスを
表すフレーム４０が存在する。

各フレームにはスロットと呼ばれる記憶場所３２が設け
られる。第８図のフレーム「Ａ」では、ｒＰＡＴ）ＩＪ
　　ｒＲＯＵＴＥＪの２種類のスロットがあり、そのス
ロットの値３３として各々「（ＡＢ　　ＢＣ）Ｊ　　ｒ
（Ａ　　Ｏ）Ｊが記憶されている。

第８図の例での各スロットの意味は明らかであろう。す
なわち現在、Ａからルート展開を開始した時点の状態で
あり、ノードフレームＡはｒノードＡからは、ＡＢとＡ
Ｃの２つのパスがあり、ルートとしてはｒ　（Ａ）Ｊの
みであり、その評価値は「０」である。１ことを表示し
ている。Ｃフレームでは展開中のルートは（Ａ　　Ｃ）
であ゛す、その評価値は２である。１２は探索機構であ
り、現在のフレームがどこにあるかを記憶するフロンテ
ィアリスト記憶領域５５、フロンティアリスト記憶領域
５５からデータアクセスパス５４によりフロンティアを
読み出して、評価値最小のルートを検出する最短ルート
検出機構５３、そして最短ルート検出機構５３の出力結
果５２に基づいて、次のルート展開を行う次パス展開機
構５０から構成される。６０と６１は探索機構１２とワ
ーキングメモリ部１１との間のデータ転送路である。ま
た、５１は次パス展開機構５０からフロンティアリスト
記憶領域５５へのフロンティアノード修正指示パスであ
る。

第８図のネットワークルート探索装置の動作については
、アルゴリズムの説明から明らかであろう。最短ルート
検出機構５３は、フロンティアリスト記憶領域５５に記
憶されている各フロンティアノード名称に対応する（ワ
ーキングメモリ部１１中の）ノードフレームをアクセス
し、各ノードのｒＲＯＵＴＥＪスロットに記憶されてい
る全てのルートの中から、最も小さな評価値を持つルー
トを選び出す。次に、次パス展開機構５ｏは、最も小さ
な評価値を持つルートから次に展開すべきノードを取り
出し、展開すべきノードに対応する（ワーキングメモリ
部１１中の）ノードフレームのｒＲＡＴＨＪスロットか
ら展開対象となるパスの名称を取り出し、ルートを後戻
りしないパスのみを選択し、各パスについて（ワーキン
グメモリ部１１中の）パスフレームをアクセスして、「
ＬＥＮＧＴＨＪスロットからパスの属性値である長さを
取り出す。さらに、この属性値に基づいて、新しいルー
ト情報を生成して、ノードフレームに転送するとともに
、フロンティアノード修正指示パス５１により新しいフ
ロンティアを追加し、古いフロンティアを消去する指示
を出す。

次パス展開機構５０について、より具体的に説明する。

例えば（Ａ　　Ｃ５）が展開されるべきルートであれば
、ノードＣのｒＰＡＴＨＪスロットからパス候補ＡＣ，
ＣＥ、ＣＤを取り出し、この中で後戻りを意味するＡＣ
を除いてＣＥ、ＣＤが展開パスとなる。次パス展開機構
５ｏはＣＥ。

ＣＤフレームから展開すべきパスの長さがそれぞれ３と
３であることを読み取り、（Ａ　　ＣＥ８）（Ａ　　Ｃ
Ｄ　　８）を新たなルートとしてノードＥとＤのｒＲＯ
ＵＴＥＪフレームに登録する。さらに、次パス展開機構
５０はフロンティアリスト記憶領域５５からフロンティ
アＣを消去し、かわりにフロンティアＥとＤを追加する
。

なお、実際には最短ルート検出機構５３は、フロンティ
アが目標の終端に到達したことを検出する機能、暫定解
を記憶し、現在展開中のルートとその暫定解を比較する
機能も必要である。また、次パス展開機構５ｏについて
も、ルート展開した先のノードに既に他のルートが存在
している時には、既存のルートが有利か、現在展開した
ものが有利かを判定して、不要なルートを抹消する機能
が必要である（ルートの展開の際に後戻りするルートを
除去したのもこの機能である）。しかし、これら細かい
機能は、この発明の要旨には直接関係はないので今後の
説明では省略する。

〔発明が解決しようとする問題点〕

以上述べた従来のルート探索アルゴリズムは、数学的に
はニレガントであるが、現実の問題に適用しようとする
と大きな問題点を有している。まず、第１に現実のネッ
トワークでは、第６図に示したような少ないノード数で
あることはありえない。東京の地下鉄でも駅は数十ある
し、全国のＪＲ網となるとノードの個数は莫大なものと
なる。

上記探索アルゴリズムでは、主要な処理時間はフロンテ
ィアからパスを延ばす処理と、複数のルートから最も小
さな評価値を持つルートを選ぶソーティング処理時間で
ある。この内、パスの延長回数は、はぼネットワーク上
のパスの個数に比例する。ソーティング処理時間はフロ
ンティアの個数（Ｎｒとする）のＮｒ３・ＬｏｇｌＪ、
に比例し、Ｎ、はほぼネットワーク上のノードの個数の
平方根に比例する。このため、ノード数の増加につれて
その処理時間は急速に増加し、現状の計算機の能力では
東京の地下鉄の最短ルートでも、人間が必要とする短い
応答は困難である。

しかし、人間は、上記のような網羅的な探索を行ってい
るのであろうか？現実の道路網を考えると、道路には一
級国道もあればうら道もある。我々がある地点からある
地点に到達するルートをさがす時には、幹線を優先して
探索することは明かである。近くに国道があるのに、わ
ざわざ商店街のみをくねくねと経由するルートを選んだ
りはしない。言い換えると、大きなネットワークには必
ず「幹線」と「支線」があり、我々は無意識のうちに幹
線を優先したルート探索をしている。しかし、従来のア
ルゴリズムを用いたネットワークルート探索装置では、
このような効率の高い探索を実現することはできないと
いう問題点があった。

この発明の目的は、上記ネットワーク探索において、パ
スの優先度を区別する手段を設け、人間の探索方式に類
似したより効率のよいルート探索を可能とするネットワ
ークルート探索装置を実現することである。

（問題点を解決するための手段） この発明にかかる階層化ネットワークルート探索装置は
、ノードならびにパスから形成されるネットワークの接
続情報をフレーム形式で記憶するワーキングメモリ部と
、該ネットワークの異なる２ノード間のルートを同時に
複数本展開し、評価値の小さなルートから先に延長する
ルート探索機構とを有し、該ネットワーク上のパスをそ
の優先度に応じて少なくとも２個以上のクラスに階層化
させ、該ネットワーク接続情報表現用フレームに、パス
のクラス区分を記憶するスロットと、パス自身の属性値
を記憶するスロットとを設けものである。

〔作用〕

この発明においては、現在展開している複数のルートか
ら次に延長するルートを選択するための各ルートの評価
値の算出にあたっては、各ルートを構成している各パス
の属性値とクラス区分の双方から評価値を算出し、該評
価値にもとづいて優先度の高いパスを優先的に展開して
２ノード間のルートを求める。

〔実施例〕

第１図はこの発明の一実施例を示す。また、この発明で
は、ネットワーク上のパスを優先度に応じて階層化する
が、第４図には２階層に階層化したネットワーク例を示
した。第４図のネットワークは第６図と類似のものであ
るが、ルート（ＡＢ　　Ｅ　　Ｇ　　Ｈ）が「幹線」と
してなっており、他のパスは全て「支線」である。ここ
では、階層を２階層としたが、一般には何階層あっても
よい。また、このような「幹線」と「支線」を分ける考
え方は、我々の日常の生活においても自然なものである
。この発明ではパスの階層に対応して、その優先度を示
す「重み」を与える。第５図には、第４図のパスの属性
値（具体的には長さ）と重みの一覧が示しである。重み
が１のパスが幹線であり、優先度が高い。

第１図において、１１０はこの発明のネットワークルー
ト探索機構、１１１はワーキングメモリ部、１１２はル
ート探索機構である。１２１はパスクラスフレーム、１
４０はパスフレームである。２００は新に追加されたｒ
ＷＥ　Ｉ　ＧＨＴＪスロットであり、１５３は最短ルー
ト検出機構である。

第１図の実施例において、第８図の従来例との相違点は
２つあり、いずれも第１図において「網かけ」で示しで
ある。その第１は、パスフレーム１４０に優先度を示す
ｒＷＥ　Ｉ　ＧＨＴＪスロットを追加し、第５図に示し
た重みを記憶している点、その第２は、ルート探索機構
１１２が後述する第　（２）式に基づいて次に延長すべ
きルートを探索している点である。

次に第１図により具体的にルート探索を実行する。ただ
し、ＦＬはフロンティアのリスト、ＲＳはルートの集合
である。評価値はルートの長さではなく、各パスの長さ
に重みを乗じた値を加算したものとなる。

Ｓｏ、Ａを探索の開始点とする。

ＦＬ←（Ａ）ＲＳ−ＮＩＬ Ｓｌ、ＡからＢとＣヘルート延長 ＦＬ←（Ｂ　　Ｃ） ＲＳ←（（Ａ　　Ｂ　　３）　　（Ａ　　Ｃ４））ここ
でルート（Ａ　　Ｂ）の評価値は３×１、（Ａ　　Ｃ）
の評価値は２×２である。

２ルート（Ａ　　Ｂ）　　（Ａ　　Ｃ）中、評価値の小
さな（Ａ　　Ｂ）を次に延長する。

Ｓ２．８からＥとＦヘルート延長 ＦＬ←（ＣＥ　　Ｆ） ＲＳ←（（Ａ　　Ｂ　　Ｅ　　５）（Ａ　　Ｂ　　Ｆ　
　９）（Ａ　　Ｃ４）） ルート（Ａ　　Ｃ４）を次の展開候補とする。

Ｓ３．ＣからＥとＤヘルート延長 ＦＬ←（Ｅ　　Ｄ　　Ｆ） ＲＳ←（（Ａ　　ＣＤ　　１０）（Ａ　　Ｂ　　Ｅ　　
５）（Ａ　　Ｂ　　Ｆ　　９）（Ａ　　ＣＥ　　１０）
）Ｅをフロンティアとするルートが２本あるが評価値の
大きなルート（Ａ　　ＣＥ　　１０）を抹消する。

ルー１−（Ａ　　Ｂ　　Ｅ　　５）を次の展開候補とす
る。

Ｓ４．ＥからＦ、Ｇヘルートを延ばす ＦＬ←（Ｄ　　Ｆ　　Ｇ） ＲＳ←（（Ａ　　ＣＤ　　　１０）（Ａ　　Ｂ　　Ｅ　
　Ｆ９）（Ａ　　Ｂ　　Ｅ　　Ｇ　　６）（Ａ　　Ｂ　
　Ｆここで、Ｆをフロンティアとするルートが２本あり
、その評価値が同一のため、無作為に（Ａ　　Ｂ　　Ｅ
　　Ｆ　　９）を抹消する。

ルート（Ａ　　Ｂ　　Ｅ　　Ｇ）を次の展開候補とする
。

Ｓ５．ＧからＨヘルートを延ばす。

ＦＬ←（Ｄ　　Ｆ　　Ｈ） ＲＳ←（（Ａ　　ＣＤ　　１０）（Ａ　　Ｂ　　Ｅ　　
ＧＨ８）（Ａ　　Ｂ　　Ｆ　　９）） ここで、（Ａ　　Ｂ　　Ｅ　　Ｇ　　Ｈ）が終端に到達
し、それ以外のルートの評価値が８より大きいので、終
了とする。

〔探索終了〕

上記のようにこの発明によれば、ルートの展開回数は５
回であり、従来技術の７回に比べて減少している。ネッ
トワークが小さいため、発明の効果はさほど顕著なもの
ではない。しかし、ネットワークが大きくなると探索回
数の差は増大し、この発明の効果がより顕著となる。な
お、この方式では、パスに重みをつけているため、かな
らずしも距離最小のルートが解として見つかるとはかぎ
らない。しかし、これは我々自身の日常でもよくあるこ
とである。つまり、我々は遠方に行く時にはいくら最小
のルートでも時間がかかってしまう時は、多少遠回りで
も国道や特急の走る幹線を利用する。また、反対に、時
間に余裕がある時は遠回りとなっても安い料金で行ける
ルートを選ぶであろう。このようにパスの重みをつけか
えることによって、距離最小のルートだけでなく、時間
最小、料金最低などの利用者の目的にあったルートを選
び出すこことができる。

さて、上記では幹線が一種類の場合であるので、パス自
体に重みをつけていた。つまり、そのパスが幹線であれ
ば重みは１であった。しかし、幹線が数種類あり、しか
もそれらが交差している場合は、幹線の間でも重みを変
えなくてはならない。ここでは、パスの重みはパスが固
有に持つのではなく、そのパスを展開する直前に展開さ
れたルートの方向によってその都度決まることとする。

次にワーキングメモリ部１１１およびルート探索機構１
１２のより詳細な実現方法を示す。

第２図（ａ）はワーキングメモリ部１１１の実現例を示
したものである。ワーキングメモリ部１１１は記憶セル
ブレーン３０４と、この記憶セルプレーン３０４を付勢
するためのアドレスデコーダ３ｏ３．アドレスレジスタ
３００．記憶セルからの読み出し情報を記憶するリード
データレジスタ３０１．記憶セルへの書き込み情報を記
憶するライトデータレジスタ３０２および全体の制御を
行う制御部３１１から構成される。３０６はアドレス情
報転送路、３０５はセル付勢路、３０７は書き込み情報
転送路、３０８は読み出し情報転送路、３０９はアドレ
ス情報転送路、３１０は制御信号転送路である。

第２図（ａ）の記憶セルブレーン３０４上には、ワーキ
ングメモリ上のフレーム情報が記憶されるが、第２図に
示すようにフレーム名称とアドレスとはあらかじめコン
パイラにより対応がつけられている。この対応づけは、
当業者には一般的なコンパル手法により可能である。第
２図（ｂ）の３２０はシンボルとアドレスの対応図であ
る。

第２図（ａ）の意味は、フレーム（ＰＡＴＨ）はアドレ
ス１２に対応しており、ＰＡＴＨのアドレス１２の記憶
セルには、そのフレームのシンボル名称ｒＰＡＴＨＪが
記憶され、当該アドレスからアドレス加算方向にセルを
次々と読むことにより、クラスｒＰＡＴＨＪのインスタ
ンスｒＡＢＪｒＡＣＪの入れられているアドレスが得ら
れる。

ｒ／ＥＮＤＪはインタフタンス情報がそこで終了したこ
とを示すシンボルである。また、フレームｒＡＣＪには
１０番のアドレスにシンボルが入っている名称のスロッ
トと、１１番のアドレスにシンボルが入っている名称の
スロットが存在していることを示している。

ネットワーク探索システムにより、スロットの値を読む
場合には、以下のような動作による。まず、フレームｒ
ＡｃＪのスロットｒ　ＷＨＩＧＨＴＪを読むとする。こ
の場合、フレーム名称ｒＡｃＪでワーキングメモリ部１
１１がアクセスされるのではなく、アドレス５番に格納
されているフレームの「スロット名称ニアドレス１１番
」であるスロットの値を取ってくることがワーキングメ
モリ部に対して要求される。

制御部３１１に制御信号転送路３１０から制御信号が送
られて、スロット値の読み出し動作が開始される。読み
出しアドレス５が、まずアドレスレジスタ３００に入れ
られる。また、スロット名称に相当するアドレスは比較
のためリードデータレジスタ３０１に格納される。アド
レスレジスタ３００では、このアドレスを１加算して、
この情報をアドレスデコーダ３０３にアドレス情報転送
路３０６により転送する。アドレスデコーダ３０３はこ
の６番の記憶セルを付勢し、セル情報をリードデータレ
ジスタ３０１に読みだす。ここでは、このリードデータ
レジスタ３０１の内容はアドレス１０番であり、期待し
ていた１１番ではない。したがって、アドレスレジスタ
３００では、さらに２を加算したアドレスを作成する。

このアドレス８番をアクセスすると、たしかに目的とす
るアドレス１１が格納されているので、さらにアドレス
レジスタ３００を１進めて９番のアドレスから目的とす
る情報（ここでは、２）をリードデータレジスタ３０１
に転送する。以上では、スロット値の読みだしを説明し
たが、書き込みも同様であり、書き込む武器データをラ
イトデータレジスタ３０２にいれておいて、目的とする
スロット値が付勢された状態で、記憶セルにデータを転
送する点のみが異なる。

第３図はルート探索機構１１２のより詳細な図である。

フロンティリスト記憶機構５５は、新に追加されるフロ
ンティアノード名称を記憶するレジスタ４１０、フロン
ティアリストを記憶するメモリ４１４、追加フロンティ
アリストノードとフロンティアリストの内容をマージす
るマーシャ４１２、フロンティアノードのダブリを検査
して重複を除く重複チエッカ４１３およびフロンティア
リストの内容を読み出して保持するリードデータバッフ
ァ４１１から構成される。フロンティアリストの内容は
、転送路５１５によりマーシャ４１２に転送され、ここ
で転送路５１４から送られてくる新しいフロンティアノ
ードが加えられ、古いフロンティアノードが除去される
。マージ結果は、−転送路５１６を経由し重複チエッカ
４１３におくられ、フロンティアノードの重複が除かれ
る。新しいフロンティアリストは転送路５１７を経由し
て、再びフロンティアリストを記憶するメモリ４１４に
記憶される。フロンティアリストを記憶するメモリ４１
４の内容は転送路５１１によりリードデータバッファ４
１１に送られ、最短ルート検出機構１５３により使用さ
れる。

最短ルート検出機構１５３は、フロンティアリストの各
ノードに相当するフレームを転送路５０８によりアクセ
スして、展開中のすべてのルートを読み出すアクセス部
４０５、読み出されたルートを記憶するルートメモリ４
０６、ルートメモリ４０６の内容をソートするソータ４
０７および展開ルートを記憶するレジスタ４０９から構
成される。ワーキングメモリから読み出されたルート情
報は、転送路５０７を経由してアクセス部４０５に入力
され、転送路５０９を経由してルートメモリ４０６に記
憶される。この中からソータ４０７は転送路５１０を利
用して、最も小さな評価値を持つルートを捜し出す。そ
の結果は転送路４０Ｂによりレジスタ４０９に蓄える。

次パス展開機構５０は、展開すべきルート情報から展開
するフロンティアノード名称を読み取り、ワーキングメ
モリをアクセスして、当該ノードに接続されたパスを読
み出すアクセス機構４０４、読み出されたパス情報を記
憶するレジスタ４０３、ルート展開を行うルートエキス
パンダ４゜１および生成されたルートをワーキングメモ
リに書き込むライトデータレジスタ４００から構成され
る。なお、新に生成されたフロンティアノード名称は、
フロンティアノード修正指示パス５１によりフロンティ
リスト記憶機構５５に転送される。アクセス機構４０４
は、転送路５０４によりノード名称を指定してワーキン
グメモリ部１１をアクセスする。その結果、スロットか
らパス情報は転送路５０３を経由して読み出され、転送
路５ｏ６を経由してレジスタ４０３に記憶される。この
パス情報を転送路５０５により読み出して、ルートエキ
スパンダ４０１は新なルート情報を生成し、転送路５０
１を経由して、ライトデータレジスタ４００に送る。ラ
イトデータレジスタ４００の内容は、転送路５０２を経
由してワーキングメモリ部１１に送られる。

なお、以上の構成例は、レジスタ、転送路等を用いて構
成したが、汎用のμＰ（マイクロプロセッサ）とプログ
ラムによりこの発明の趣旨にしたがって構成することも
当業者には可能である。また、本明細書では、優先度は
パスの情報として提供されるとしたが、ノードを通過す
る時の「パス選択の容易さ」により優先パスをしてもよ
い。この場合は、−旦乗った電車から極力降りないでそ
のまま乗ってゆくことに相当する。

上記のとおり、この発明のネットワークルート探索装置
では従来技術とな異なり、パスを表現するフレームにそ
の優先度を示す属性情報が記憶されている点に特徴があ
る。すなわち従来のネットワークルート探索機構では、
ルートの評価値ＥＶを算出する時に当該ルートを形成す
る各パスの長さをＬｌとして、 ＥＶ＝　　Σ　Ｌ　監　　　　　　　　　　　　　　　
　　　　　　　　　　　・・・　・・・　　（１）によ
り評価値を計算しているのに対して、この発明のネット
ワークルート探索機構では、各パスの優先度を示す重み
づけ値ＷＩを併用し、ＥＶ＝ＸＬ＋　　　ＸＷ＋　　　
　　　　　　　　　　　　　　”””　　　（２）とし
て評価値を計算する。優先度の高い、すなわち重みの小
さなパスを通るほど、ＥＶ値の増加は小さくなり、ルー
トの探索が優先度の高いパスを優先して実行されること
になる。

なお、上記第　（２）式は、優先度の高いパスはど評価
値の増加を押えられるような相関を有する関数であれば
、どんな関数を選んでもよく、第（２）式の関数形式が
この発明の趣旨に影響を与えることはない。さらに、付
は加えると、この明細書では評価値が小さくなる方がよ
いルートとして議論を進めているが、評価値が大きくな
る方向を良いルートとして探索を実行する場合も考えら
れる。

しかし、この場合でも優先度の高いパスはど評価値の増
加が促進されるような相関を有する関数であれば、評価
値を計算する関数としてどんな関数が選ばれても、この
発明の趣旨を変えるものではない。

〔発明の効果） 以上説明したようにこの発明は、ノードならびにパスか
ら形成されるネットワークの接続情報をフレーム形式で
記憶するワーキングメモリ部と、該ネットワークの異な
る２ノード間のルートを同時に複数本展開し、評価値の
小さなルートから先に延長するルート探索機構とを有し
、該ネットワーク上のパスをその優先度に応じて少なく
とも２個以上のクラスに階層化させ、該ネットワーク接
続情報表現用フレームに、パスのクラス区分を記憶する
スロットと、パス自身の属性値を記憶するスロットとを
設けてなり、該２ノード間のルートを探索する探索機構
が、現在展開している複数のルートから次に延長するル
ートを選択するための各ルートの評価値の算出にあたフ
ては、各ルートを構成している各パスの属性値とクラス
区分の双方から評価値を算出し、該評価値にもとづいて
優先度の高いパスを優先的に展開して２ノード間のルー
トを求めるようにしたので、ネットワークのノード数が
増加しても探索に必要な時間を少なく押えることができ
る。また、この発明では、人間が通常行う幹線を優先し
たルート設定が可能であり、人間にとって自然な探索解
を提示できる特徴がある。

【図面の簡単な説明】

第１図はここの発明のネットワークルート探索装置の一
実施例を示すブロック図、第２図（ａ）。 （ｂ）はワーキングメモリ部のより詳細な構成図および
シンボルとアドレスの対応図、第３図は探索機構のより
詳細な構成図、第４図は幹線を有するネットワークの例
を示す図、第５図はこの発明に使用する重みづけ情報の
例を示す図、第６図はネットワークの例を示す図、第７
図はフロンティアノードを明示したネットワークの例を
示す図、第８図は従来のネットワークルート探索装置を
示す図である。 図中、５ｏは次パス展開機構、５１はフロンティアノー
ド修正指示パス、５２は最短ルート検出機構の出力結果
、５４はデータアクセスパス、５５はフロンティアリス
ト記憶領域、６０．６１はデータ転送路、１１０はネッ
トワークルート探索機構、１１１はワーキングメモリ部
、１１２は探索機構、１２１はパスのクラスフレーム、
１４０はパスのクラスフレーム、１５３は最短ルート検
出機構、２００は重みスロットである。 第４図 第５図 第６図 第７図

Claims (1)

【特許請求の範囲】
1. ノードならびにパスから形成されるネットワークの接続
   情報をフレーム形式で記憶するワーキングメモリ部と、
   該ネットワークの異なる２ノード間のルートを同時に複
   数本展開し、評価値の小さなルートから先に延長するル
   ート探索機構とを有し、該ネットワーク上のパスをその
   優先度に応じて少なくとも２個以上のクラスに階層化さ
   せ、該ネットワーク接続情報表現用フレームに、パスの
   クラス区分を記憶するスロットと、パス自身のパスの属
   性値を記憶するスロットとを設けてなり、該２ノード間
   のルートを探索する探索機構が、現在展開している複数
   のルートから次に延長するルートを選択するための各ル
   ートの評価値の算出にあたっては、各ルートを構成して
   いる各パスの属性値と該クラス区分の双方から評価値を
   算出し、該評価値にもとづいて優先度の高いパスを優先
   的に展開して２ノード間のルートを求めることを特徴と
   する階層化ネットワークルート探索装置。