(57)【要約】    【課題】重み付きグラフの最小経路を並列分散処理により求解する際の計算時間を減少させること。    【解決手段】初期入力部１１と、グラフの枝毎の重みに対応する遅延量を記憶したメモリを有する遅延部１２−１〜１２−８と、グラフの各節点に対応する出力決定部１３−１〜１３−４と、論理和回路１４−１〜１４−４と、パス保存部１５とからなるニューラルネットワークを用い、初期入力部の目的節点に対応する出力端に信号を送信し、遅延部により論理和回路の出力端から出力された信号を遅延量分遅らせて送信し、各出力決定部により最初に得られた信号のみを一方の出力端に送信するとともに、最初に信号が得られた入力端に対応する枝の情報を他方の出力端に出力し、これを当該出力決定部に対応する節点から目的節点へ到達する最小経路の一部分としてパス保存部に記憶する。【選択図】図８
2006246105.tif 000002
【特許請求の範囲】
【請求項１】
入力端及び出力端をそれぞれ少なくとも１つ有する複数の節点と、一の節点の入力端と他の節点の出力端とを１対１で接続する枝と、枝毎に与えられる数値情報である重みとで構成される重み付きグラフにおいて、任意の出発節点から任意の目的節点へ到達可能な経路のうち通過する枝の重みの和が最小となる経路を求める最小経路問題を解く計算方法であって、
各節点において当該節点から目的節点までの最小経路を示す情報のうち、当該節点に接続しているどの枝を選択するかという情報のみを求める
ことを特徴とする最小経路計算方法。
【請求項２】
請求項１に記載の最小経路計算方法において、
グラフの各節点に対応する複数の出力端を有する初期入力部と、
それぞれがグラフの枝毎の重みに対応する遅延量を記憶したメモリを有する遅延部と、
それぞれがグラフの各節点に対応し、該各節点における入力端に対応する入力端と２つの出力端とを有する複数の出力決定部と、
各出力決定部の一方の出力端及び初期入力部の前記各出力決定部と同一の節点に対応する出力端をそれぞれ入力とする複数の論理和回路と、
各出力決定部の他方の出力端と接続されたパス保存部とからなり、
各出力決定部のそれぞれの入力端が、グラフ中の枝の接続元の節点に対応する初期入力部の出力端を一方の入力とする論理和回路の出力端と当該枝に対応する遅延部を介して接続されてなるニューラルネットワークを用い、
初期入力部の目的節点に対応する出力端に信号を送信し、
遅延部により、論理和回路の出力端から出力された信号をメモリに記憶した遅延量分遅らせて送信し、
各出力決定部により、最初に信号が得られた入力端に対応する枝の情報を他方の出力端に出力するとともに、当該最初に得られた信号のみを一方の出力端に送信し、
パス保存部により、各出力決定部の他方の出力端より出力された枝の情報を当該出力決定部に対応する節点から目的節点へ到達する最小経路の一部分としてそれぞれ記憶する
ことを特徴とする最小経路計算方法。
【請求項３】
入力端及び出力端をそれぞれ少なくとも１つ有する複数の節点と、一の節点の入力端と他の節点の出力端とを１対１で接続する枝と、枝毎に与えられる数値情報である重みとで構成される重み付きグラフにおいて、任意の出発節点から任意の目的節点へ到達可能な経路のうち通過する枝の重みの和が最小となる経路を求める最小経路問題を解く計算装置であって、
グラフの各節点に対応する複数の出力端を有する初期入力部と、
それぞれがグラフの枝毎の重みに対応する遅延量を記憶したメモリを有する遅延部と、
それぞれがグラフの各節点に対応し、該各節点における入力端に対応する入力端と２つの出力端とを有する複数の出力決定部と、
各出力決定部の一方の出力端及び初期入力部の前記各出力決定部と同一の節点に対応する出力端をそれぞれ入力とする複数の論理和回路と、
各出力決定部の他方の出力端と接続されたパス保存部とからなり、
各出力決定部のそれぞれの入力端は、グラフ中の枝の接続元の節点に対応する初期入力部の出力端を一方の入力とする論理和回路の出力端と当該枝に対応する遅延部を介して接続され、
さらに、
初期入力部は、任意の目的節点に対応する出力端に信号を送信する機能を有し、
遅延部は、論理和回路の出力端から出力された信号をメモリに記憶した遅延量に対応する時間分遅らせて送信する機能を有し、
各出力決定部は、最初に信号が得られた入力端に対応する枝の情報を他方の出力端に出力するとともに、当該最初に得られた信号のみを一方の出力端に送信する機能を有し、
パス保存部は、各出力決定部の他方の出力端より出力された枝の情報を当該出力決定部に対応する節点から目的節点へ到達する最小経路の一部分としてそれぞれ記憶する機能を有する
ことを特徴とする最小経路計算装置。
【請求項４】
請求項３に記載の最小経路計算装置において、
メモリに記憶する遅延量及びその動作を任意に設定可能な枝の数と同数以上の遅延部と、
所定の数の入力端と２つの出力端とを有する節点の数と同数以上の出力決定部とを備え、
各出力決定部のそれぞれの入力端は、他の出力決定部の一方の出力端と論理和回路及び近傍の遅延部を介して接続され、
前記遅延部のうちグラフ中の枝に対応する遅延部にのみ当該枝の重みに対応する遅延量を記憶させるとともにグラフ中の枝に対応しない遅延部は遮断状態とする
ことを特徴とする最小経路計算装置。
【請求項５】
請求項３に記載の最小経路計算装置において、
メモリに記憶する遅延量を任意に設定可能な枝の数と同数以上の互いに近接配置された遅延部と、
所定の数の入力端と２つの出力端とを有する節点の数と同数以上の互いに近接配置された出力決定部と、
各出力決定部のそれぞれの入力端と各遅延部との間及び各論理和回路の出力端と各遅延部との間に格子状に配置されたスイッチとを備え、
グラフ中の枝の重みに対応する遅延量が設定された遅延部を当該グラフ中の枝に対応する出力決定部の入力端と論理和回路の出力端との間に接続するようにスイッチを動作させる
ことを特徴とする最小経路計算装置。
【請求項６】
節点に対応するノードと、枝に対応するリンクとによって構成される通信ネットワークであって、
各ノードは、請求項３記載の最小経路計算装置のうち、
自ノードから他ノードへ接続するリンクに対応した遅延部と、
自ノードに対応した出力決定部と、
目的ノードへ通信を行うために自ノードから近傍のどのノードに情報を転送すればよいかを示すパス情報を記憶するパス保存部とを備えた
ことを特徴とする通信ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、重み付きグラフにおける最小経路を計算（探索）する技術に関する。
【背景技術】
【０００２】
光通信ネットワークでは、光ファイバの広帯域性を活用したＷＤＭ技術の導入が行われている。基幹部またはバックボーンネットワークといった従来のＷＤＭの適用分野においては、目的のノードへ伝送する信号を伝達するために他のどのノードを経由するかというパスの更新は秒〜分という比較的遅いものである。これに対し、ＬＡＮやメトロといった、よりユーザに近いネットワークでは目的ノードが異なる確率が高く、ＩＰ電話に代表されるリアルタイム通信で許容できる転送遅延は２０〜１００ミリ秒以下と言われてる（非特許文献１参照）。より高頻度に目的ノードが変化するネットワークにおいて、通信網を効率的に利用するためには従来より高速にパスの更新を行う必要がある。
【０００３】
従来、パス更新のために用いられている計算アルゴリズムには逐次処理型と並列分散処理型がある。逐次処理型のアルゴリズムには、ダイクストラ法（特許文献１参照）やベルマンフォード法（特許文献２参照）がある。どちらも（１）複数の入力端及び出力端を有する複数の節点、（２）一の節点の入力端と他の節点の出力端とを１対１で接続する枝、（３）枝毎に与えられる数値情報である重み、で構成される重み付きグラフの単一節点から複数節点、または全節点から全節点へ到達するまでに通過する枝の重みの和の最小を求めるアルゴリズムである。また、並列分散処理型にはニューラルネットワークを用いた方式が提案されている（非特許文献２、特許文献３参照）。
【０００４】
図１、図２は重み付きグラフの例を示すもので、この例では４つの節点Ａ，Ｂ，Ｃ，Ｄと、４つの枝と、枝の重みｗij（ｉ，ｊ＝Ａ，Ｂ，Ｃ，Ｄ）とでグラフを構成している。ここで、図１は枝が一方通行であったり、枝の方向によって重みの値が異なる、つまり節点間の接続に方向性が存在するグラフの例を示すものであり、また、図２は節点間の接続に方向性がないグラフの例を示すものである。
【０００５】
重み付きグラフにおける最小経路をダイクストラ法により求解する際のフローチャートを図３に示す。この方法では、調査中リストが空になるために最大節点数の繰り返しが起こり得る。また、ステップ４．５．６．では最大節点数の調査が必要となる。そのため、ソフトウェアで構成した場合、節点数の２乗で計算量が増加し、専用ハードウェアでステップ４．５．６．の処理を１回の計算で可能とした場合でも、節点数に対し１乗で計算量が増加する。ダイクストラ法の計算量を減らす方法として、枝数が少ない疎なグラフに対してデータの格納法を工夫するヒープソートを用いた方法がある（特許文献１参照）。
【０００６】
非特許文献２に開示された遅延素子を用いたニューラルネットワークを用いて、図１に示した重み付きグラフにおける最小経路を求解する際の回路（模擬回路）構成を図４に示す。回路は、枝数の２倍の遅延回路（遅延素子）１と、節点数と同数の論理和回路２と、１つの判定回路３とで構成される。
【０００７】
節点Ａから節点Ｄへの最小経路を求める場合を考える。初めに目的節点であるＤに相当する信号ＯDのみを出力１とする。各遅延回路１は論理和回路２を介して信号Ｏi（ｉ＝Ａ，Ｂ，Ｃ，Ｄ）が入力されると枝の重みに応じた遅延後、判定回路３へ信号Ｉk（ｋ＝Ａ，Ｂ，Ｃ，Ｄ）を与えるため、ここでは信号ＩBのみ出力１となる。判定回路３では最初に入力された信号Ｉk、ここではＩBを記憶し、この信号ＩBに対応する節点、即ちＢが節点Ｄの直前の節点となる。この後、より大きな遅延を持った信号が判定回路３に入力される可能性があるため、遅延回路１及び判定回路３をリセットした後、求めた直前の節点からその直前の節点を求める。この動作をリンク数（＝枝数）繰り返すことにより、最小経路を求解する。
【０００８】
図５に前記遅延素子を用いたニューラルネットワークによる求解方法の流れを示す。この手法は並列演算処理であるため、複数の作業がパラレルに進行する。このアルゴリズムでは節点数に対応する数の作業が並列に動作するため、計算量は重みに対応して停止するステップ数と、作業の繰り返し数である中継節点の数とに比例する。
【０００９】
図６にダイクストラ法による求解方法と遅延素子を用いたニューラルネットワークによる求解方法とにおける計算ステップを比較して示す。ダイクストラ法では図３におけるステップ４．５．６．の処理に節点数の計算量がかかり、それらの処理を節点数回繰り返す。一方、遅延素子を用いたニューラルネットワークによる求解方法は、遅延時間に対応する計算ステップが出発節点から目的節点へ到達するまでに通過する節点（中継節点）の数の回数繰り返される。一般に、中継節点の数は節点数以下であるため、節点数が増加すると遅延素子を用いたニューラルネットワークによる方法の方がダイクストラ法よりも計算ステップが少なくなる。
【００１０】
非特許文献２のニューラルネットワークによる求解方法の課題である、（１）最小経路のリンク数の繰り返しにより計算時間が増大する、（２）遅延素子及び判定回路をリンク毎に接続して測定する必要があるため、遅延素子及び判定回路の挿入・抜去に時間を要する、などの点を改善した方法が特許文献３に記載されている。
【００１１】
図７は特許文献３に開示された遅延素子を用いたニューラルネットワークを用いて、図１に示した重み付きグラフにおける最小経路を求解する際の回路（模擬回路）構成を示すもので、回路は、枝数の２倍の遅延回路（遅延素子）１と、節点数と同数の論理和回路２と、１つのテスト回路４と、節点数と同数の分析素子５と、１つの判定回路６とで構成される。
【００１２】
テスト回路では、先頭を表すパルス及びリンク数に等しいだけのパルスを出力する。遅延回路１では重みに相当する遅延をかけると同時に自遅延回路に割り当てた番号のパルスのみを欠落させる。先頭を表すパルスにより、非特許文献２に開示された方法の場合と同様に直前の節点を判定することが可能になる。分析素子５では、複数の入力Ｉijのうち最初に到達したものを出力し、その後は動作を停止し、いかなる入力にも反応しない。全ての分析素子５の動作が停止した時に計算終了となる。判定回路６では分析素子５でのパルスの欠落情報からどのリンク（枝）を辿ってきたかを判定する。
【特許文献１】特開平１０−１３２５９４号公報
【特許文献２】特開平６−９７９６４号公報
【特許文献３】特開平８−１６３１２６号公報
【非特許文献１】佐藤健一、古賀正文「広帯域光ネットワーキング技術」電子情報通信学会、２００３、１４３頁〜１４５頁
【非特許文献２】松本隆男「通信網を模擬したニューラルネットによる高速ルーティング」電子情報通信学会技術報告ＮＣ９１−３０、１９９１、１頁〜８頁
【発明の開示】
【発明が解決しようとする課題】
【００１３】
逐次処理型アルゴリズムは、ソフトウェアとしてもハードウェアとしても実装可能であるが、ソフトウェア実装ではヒープソートを利用しても計算量がノード数の１次関数以上に増加する。また、ハードウェア実装では高度なヒープソートを搭載することが困難なため、計算量が２乗で増加するという欠点がある。
【００１４】
また、並列分散処理型アルゴリズムは、逐次処理と比較して同時刻に動作している演算部が多いため、高速に計算を行う可能性を持っているが、非特許文献２に開示された方法は、特許文献３に記載されているように（１）最小経路のリンク数の繰り返しにより計算時間が増大する、（２）遅延素子及び判定回路をリンク毎に接続して測定する必要があるため、遅延素子及び判定回路の挿入・抜去に時間を要するという問題がある。さらに、非特許文献２に開示された方法では、通過したリンク（枝）の情報から経路を再構成しなくてはならない。例えば、全ての枝を通過した場合、先頭パルスのみの信号となる。この情報から経路を判定するのにリンク数の計算量が必要となり、節点数・枝数の増加により計算時間が増大する。
【課題を解決するための手段】
【００１５】
本発明は並列分散処理による計算量の減少を狙うもので、特許文献３に開示された方法とは異なる方式により、非特許文献２に開示された方法の計算時間の高速化を行う。
【００１６】
通信などのルーティングにおいては、出発節点から目的節点までの全ての経路情報ではなく、出発節点を含めた各中継節点において、次に近傍のどの節点に転送するかという情報が必要となる。そのため、従来は、目的節点から各中継節点まで通過した枝の情報から通過した順番を計算し、各中継節点がどの近傍点に転送するかを決定する。
【００１７】
本発明の特徴とするところは、目的節点から各中継節点に対し、グラフ内の各節点は目的節点まで到達する最小経路情報を全て持つ必要はない、という考えに基づき、節点は自節点に最初に受けた入力を与えた枝の情報のみから経路決定を行うことにある。
【発明の効果】
【００１８】
本発明によれば、遅延素子を用いたニューラルネットワークに対して、（１）最小経路のリンク数の繰り返しにより計算時間が増大する、（２）遅延素子及び判定回路をリンク毎に接続して測定する必要があるため、遅延素子及び判定回路の挿入・抜去に時間を要するといった問題点が生じないため、計算時間が短くなる。改良型の遅延素子を用いたニューラルネットワークに対しては、複数パルスを発生させるテスト回路が不要であり、遅延回路に複数の時分割スイッチを設ける必要がない、分析素子の動作終了後に計算結果を解析する分析回路が必要ない、といったハードウェア化における回路規模の減少が可能である。また、解析に伴う計算が不要であるため、計算時間が高速になる。
【発明を実施するための最良の形態】
【００１９】
＜第１の実施の形態＞
図８は本発明の最小経路計算装置の第１の実施の形態、ここでは図１に示した重み付きグラフに対応した例を示すもので、図中、１１はグラフの各節点（Ａ，Ｂ，Ｃ，Ｄ）に対応する複数の出力端を有する初期入力部、１２−１〜１２−８はそれぞれがグラフの枝毎の重みに対応する遅延量（Ｔij）を記憶したメモリを有する遅延部、１３−１〜１３−４はそれぞれがグラフの各節点に対応し、該各節点における入力端に対応する入力端と２つの出力端とを有する複数の出力決定部、１４−１〜１４−４は各出力決定部１３−１〜１３−４の一方の出力端及び初期入力部１１の前記各出力決定部１３−１〜１３−４と同一の節点に対応する出力端をそれぞれ入力とする複数の論理和回路、１５は各出力決定部１３−１〜１３−４の他方の出力端と接続されたパス保存部である。
【００２０】
ここで、各出力決定部１３−１〜１３−４のそれぞれの入力端は、グラフ中の枝の接続元の節点に対応する初期入力部１１の出力端を一方の入力とする論理和回路１４−１〜１４−４の出力端と当該枝に対応する遅延部１２−１〜１２−８を介して接続される。
【００２１】
また、初期入力部１１は、任意の目的節点に対応する出力端に信号を送信する機能を有し、遅延部１２−１〜１２−８は、論理和回路１４−１〜１４−４の出力端から出力された信号をメモリに記憶した遅延量分送らせて送信する機能を有する。
【００２２】
また、各出力決定部１３−１〜１３−４は、最初に信号が得られた入力端に対応する枝の情報を他方の出力端に出力するとともに、当該最初に得られた信号のみを一方の出力端に送信する機能を有し、パス保存部１５は、各出力決定部１３−１〜１３−４の他方の出力端より出力された枝の情報を当該出力決定部に対応する節点から目的節点へ到達する最小経路の一部分としてそれぞれ記憶する機能を有する。
【００２３】
なお、図２に示したような節点間の接続に方向性がないグラフの場合、遅延部を共通化することでその個数を半減させることができる。図９はこの場合の装置構成を示すもので、グラフ中の枝で接続された２つの節点にそれぞれ対応する初期入力部１１の出力端を一方の入力とする２つの論理和回路の出力端同士を入力とする新たな論理和回路１６−１〜１６−４の出力端と、前記２つの節点に対応する２つの出力決定部の入力端との間に、前記枝の重みに対応する遅延量を記憶したメモリを有する遅延部を接続すれば良い。
【００２４】
また、図８、図９の例ではパス保存部を１つの回路として構成したが、各出力判定部に対応し、該各出力決定部の他方の出力端とそれぞれ接続される複数の回路、あるいは入力端の総和が出力決定部の数（グラフの節点の数）と一致し、該各入力端を介して各出力決定部の他方の出力端と接続される２以上の回路で構成しても良い。
【００２５】
次に、本装置の動作を述べる。
【００２６】
まず、初期入力部１１により、その目的節点に対応する出力端にのみ信号を送信すると、この信号は前記目的節点に対応する出力端を一方の入力とする論理和回路１４−１〜１４−４を通過し、この論理和回路の出力端に接続された遅延部１２−１〜１２−８に入力される。
【００２７】
各遅延部１２−１〜１２−８は、入力された信号を、記憶した遅延量に対応する時間分遅らせて送信するため、初期入力部１１の信号を送信した出力端と論理和回路を介して接続している遅延部は、記憶した遅延量に対応する時間分遅らせた後、信号を送信する。グラフの各節点における入力端に対応する入力端を介して複数の遅延部と接続している各出力決定部１３−１〜１３−４では、最初に信号が得られた入力端に対応する遅延部、即ちグラフにおける枝の情報をパス保存部１５へ出力するとともに、論理和回路１４−１〜１４−４と接続する出力端から当該最初に得られた信号のみを送信する。パス保存部１５では、前記枝の情報を該当する出力決定部に対応する節点から目的節点へ到達する最小経路の一部分の情報として記憶する。
【００２８】
計算を開始してから一番早く信号が到達した出力決定部に対応する節点が、その節点と目的節点とを接続する枝の重みの値が最も小さくなる節点である。一度、信号を出力した出力決定部は、計算終了までいかなる入力に対しても信号を出力しない。以下、一度、信号を出力した出力決定部の状態を停止と呼ぶことにする。
【００２９】
この後も装置は動作を続け、全ての出力決定部が停止状態になると計算を終了する。全ての出力決定部１３−１〜１３−４が停止した時点でパス保存部１５に記憶されている枝の情報は、それぞれが各節点から目的節点へ到達する最小経路の一部分の情報であり、また、これらの情報をまとめて全ての節点から目的節点へ到達する最小経路の情報とすることもできる。
【００３０】
図１０に第１の実施の形態における動作の一例、ここでは任意の節点から節点Ａに到達するパスを計算する動作の例に対応する信号波形を示す。目的節点（節点Ａ）に対応する初期入力部１１の出力端に「１」の信号ＩAを与えると、該初期入力部１１の出力端と論理和回路１４−１並びに遅延部１２−３及び１２−６を介して接続されている出力決定部１３−２及び１３−３の入力端へは、該遅延部１２−３及び１２−６に記憶された遅延量に対応する時間分の後、「１」が与えられる。この際、出力決定部１３−２及び１３−３の各入力端に対する最初の信号「１」であれば、当該出力決定部から対応する論理和回路へ出力される信号が「１」となり、停止状態となる。
【００３１】
ここでは遅延部１２−６で遅延された信号が出力決定部１３−３の各入力端に対する最初の信号「１」であり、その結果、当該遅延部１２−６における遅延量に対応する時間ｔ（ｗCA）の後、当該出力決定部１３−３からの信号を受けた論理和回路１４−３の信号ＩCが「１」となることが示されている。また、この際、パス保存部１５には、節点Ｃに対応する出力決定部１３−３から、最初に信号が得られた入力端に対応する枝の情報として節点Ｃから節点Ａへ向かう枝の情報が記憶される。
【００３２】
以下、同様の動作を繰り返し、全ての出力決定部１３−１〜１３−４が停止状態になって信号ＩA〜ＩDが「１」になると、計算終了となる。最後にパス保存部１５に記憶された各出力決定部１３−１〜１３−４毎の情報から目的節点へ向かう全ての節点からの最小転送先を求めることができる。
【００３３】
図１１に特許文献３に開示された従来技術と本発明とにおける計算ステップを比較して示す。ここでは、図５に示す遅延素子を用いたニューラルネットワークによる求解方法において並列に処理される各作業のみに対応して示している。
【００３４】
従来技術では、経路をパルス列の欠落情報で表しているが、このパルス列の欠落情報は出発節点から目的節点への最小経路において通過する枝を示すが、それら枝をどの順番に通過するかという情報がない。そのため、パルスの欠落情報から経路を特定する処理が必要となる。
【００３５】
一方、本発明では、各節点は目的節点へ到達する最小経路情報を全て持つ必要はない、という考えに基づく。即ち、ある節点において目的節点へ最小経路で到達するために結合しているどの枝を通過するかという情報を全ての節点が各々持っていれば、全ての節点から目的節点への最小経路が分かる。この考えを実現するには、各節点は自節点に最初に入力を与えた枝を記憶すれば良い。そのため、従来技術で必要な、パルスを欠落させる、欠落パルスから経路を判定という処理が必要ない。
【００３６】
図１２に特許文献３に開示された従来技術と本発明とにおけるハードウェア規模を定性的に比較して示す。
【００３７】
初期の入力を与えるという点で同じ役割を有する従来技術におけるテスト回路と本発明における初期入力部とを比較すると、テスト回路はリンク数のパルスを発生させる必要があるのに対し、初期入力部は単パルスまたはロー（Low）からハイ（High）へと変化する信号を発生させるのみで良く、明らかに簡単な回路構成で済む。
【００３８】
また、遅延をかける遅延回路と遅延部を比較すると、従来技術における遅延回路は複数パルスから自遅延回路に割り当てられた番号に対応するパルスを欠落させるために、入力の連続パルスを前段の時分割スイッチによって単パルスに変換し、それぞれをメモリに記憶し、後段の時分割スイッチを制御回路で遅延をかけてスイッチングという動作を行っている（特許文献３の図３参照）。一方の本発明における遅延部では、制御回路で遅延をかけた後にスイッチングするのみで良いため、時分割スイッチとメモリが不要になり、制御回路も単純になる。
【００３９】
また、最小経路情報を保持する記憶部へ情報を与えるためには、従来技術ではパルスの欠落情報から経路を再構成するための判定回路が必要になるが、本発明では不要である。
【００４０】
以上のことから個々の構成要素において本発明の方が機能的に単純であり、それゆえに実装時のハードウェア規模は小さくなると言える。
【００４１】
図１３に従来技術と本発明との実装回路における計算速度を定性的に比較して示す。ここで、従来技術において、分析素子に遅延回路から入力が入り、その入力信号を出力し、それ以降の遅延回路からの入力信号を出力しない状態のことを分析素子が停止したと呼ぶ。また本発明においても同様に、出力決定部が出力を行った状態をその出力決定部が停止したと呼ぶことにする。ここでは従来技術及び本発明の全ての分析素子または出力決定部が停止するまでの時間を同じと仮定している。
【００４２】
従来技術では、分析素子に遅延回路から入力が一度以上入ると、判定回路がその分析素子に入力されたパルスの欠落情報から経路を判定し、記憶回路に保存する。
【００４３】
従来技術１の判定回路は、ｉ組のパルス列に対して演算を行う回路を仮定しているので、判定回路が動作中に他の分析素子の動作が停止しても、その分析素子に対してすぐに判定を行うことができず、待ち時間が生じる。このため全ての情報を書き込むために多くの時間がかかる可能性がある。そのため従来技術２では、判定回路を節点数と同数用意することで、書き込み終了までの時間を短縮している。
【００４４】
一方、本発明では、判定回路が存在しないため、これら従来技術よりも計算開始から書き込み終了までの時間を短縮することが可能である。即ち、従来技術１に対しては１回の判定回路の動作時間以上の速度向上が見られ、従来技術２に対しては１回の判定回路の動作時間の速度向上に加え、図１２における判定回路の規模が節点数増大するため、ハードウェア規模的な効果も期待できる。
【００４５】
＜第２の実施の形態＞
図１４は本発明の最小経路計算装置の第２の実施の形態、ここでは回路構成を自由に変更可能とするとともに集積化に適した例を示すもので、図中、２１は枝の数と同数以上の遅延部、２２は節点の数と同数以上の出力決定部である。なお、図面では初期入力部、論理和回路及びパス保存部は省略している。
【００４６】
遅延部２１は、メモリに記憶する遅延量及びその動作を任意に設定可能となっており、また、出力決定部２２は、所定の数（ここでは６）の入力端と２つの出力端（但し、図面では、そのうちの一方について図示しない論理和回路を経た後を６つに分けて表し、図示しないパス保存部に接続される他方については省略している。）とを有し、各出力決定部２２のそれぞれの入力端は、他の出力決定部２１の一方の出力端と図示しない論理和回路及び近傍の遅延部２１を介して接続されている（なお、図面上の矢印は矢の向いた方向が入力端であることを表している。）。
【００４７】
この状態において、遅延部２１のうちグラフ中の枝に対応する遅延部２１にのみ当該枝の重みに対応する遅延量を記憶させるとともにグラフ中の枝に対応しない遅延部２１は遮断状態とすることにより、任意の重み付きグラフに対応した回路を構成することができる（例えば図１４において、黒塗りで表した遅延部２１に図１の重み付きグラフにおける重みに対応した遅延量をそれぞれ設定し、他の遅延部２１を遮断状態とすることにより、図１の重み付きグラフに対応した回路を構成できる。）。
【００４８】
また、本装置は、各出力決定部２２を近傍の遅延部２１を介して周囲の出力決定部２２と接続するのみで良く、ＬＳＩのような回路を多数集積するものにおいて高集積化を妨げる配線量を大幅に減少させることが可能である。
【００４９】
なお、１つの節点に接続される枝の数が１つの出力決定部の入力端の数以上（図１４の例では６以上）である場合は、２以上の出力決定部間の遅延部を遅延量０とすることにより、当該２以上の出力決定部で１つの節点に対応する出力決定部を実現することができる（または入力端の数の異なる出力決定部を配置することでも実現可能である。）。
【００５０】
＜第３の実施の形態＞
図１５は本発明の最小経路計算装置の第３の実施の形態、ここでは回路構成を自由に変更可能とするとともに遅延部を効率的に利用可能とした例を示すもので、図中、３１は枝の数と同数以上の互いに近接配置された遅延部、３２は節点の数と同数以上の互いに近接配置された出力決定部、３３は多数のスイッチである。なお、図面では初期入力部、論理和回路及びパス保存部は省略している。
【００５１】
遅延部３１は、メモリに記憶する遅延量を任意に設定可能となっており、また、出力決定部３２は、所定の数（ここでは１）の入力端と２つの出力端（但し、図面では、そのうちの一方について図示しない論理和回路を経た後を示し、図示しないパス保存部に接続される他方については省略している。）とを有し、また、スイッチ３３は、各出力決定部３２のそれぞれの入力端と各遅延部３１との間及び図示しない各論理和回路の出力端と各遅延部３１との間、ここでは出力決定部３２の入力端に接続された入力線及び出力端に図示しない論理和回路を介して接続された出力線と、遅延部３１の入力側及び出力側にそれぞれ接続された入力線及び出力線との間に格子状に配置されている。
【００５２】
この状態において、グラフ中の枝の重みに対応する遅延量が設定された遅延部３１を当該グラフ中の枝に対応する出力決定部３２の入力端と図示しない論理和回路の出力端との間に接続するようにスイッチ３３を動作させることにより、任意の重み付きグラフに対応した回路を構成することができる。
【００５３】
一般的な重み付きグラフは、節点よりも枝の方が多い。また回路構成上、節点に対応する出力決定部よりも枝に対応する遅延部の方が複雑でハードウェア規模が大きい場合が多い。これらのことから遅延部を効率的に利用することが限られた回路実装規模の中で様々なグラフの最小経路を求める上で重要であることがわかる。
【００５４】
本装置では、遅延部３１及び出力決定部３２がそれぞれ近傍に配置され、各出力決定部３２のそれぞれの入力端と各遅延部３１との間及び図示しない各論理和回路の出力端と各遅延部３１との間に多数のスイッチが格子状に配置され、任意の遅延部３１を出力決定部３２の入力端と図示しない論理和回路の出力端との間に接続することが可能であるため、遅延部の効率的な利用が可能となる。
【００５５】
＜第４の実施の形態＞
図１６は本発明の最小経路計算装置の第４の実施の形態、ここでは通信ネットワークに適用した例を示すもので、図中、４０Ａ〜４０Ｄは節点に対応するノード、４１−１〜４１−８は自ノードから他ノードへ接続するリンクに対応した遅延部、４２−１〜４２−４は自ノードに対応した出力決定部、４３−１〜４３−４は目的ノードへ通信を行うために自ノードから近傍のどのノードに情報を転送すればよいかを示すパス情報を記憶するパス保存部である。
【００５６】
この例における節点と枝の接続は図１と同様である。各通信ノード４０Ａ〜４０Ｄは、接続しているノード数と同数またはその２倍の遅延部を有し、１つの出力決定部及びパス保存部を有する。ノードが物理的に離れた場所にあるため、遅延部４１−１〜４１−８及び出力決定部４２−１〜４２−４の存在場所も物理的に離れた場所に分散するが、これら回路の動作は第１の実施の形態の装置と変わらない。パス保存部４３−１〜４３−４は各ノードが任意の目的ノードに情報を伝達する際に近傍のどのノードに伝達情報を転送するかというルーティングテーブル情報が保存される。ＭＰＬＳなど、現状の通信ネットワークにおけるパス設定においては、計算終了後、ネットワーク内の全てのノードが計算結果であるルーティングテーブルを更新したことを確認してから通信を開始しなければ、正しくルーティングされず、ルーティングテーブル情報の伝達及び更新の確認には分単位の時間がかかっている。
【００５７】
本発明では、目的ノードに相当する節点から計算を開始しているので、あるノードに対応する出力決定部が停止状態にあれば、そのノードから目的ノードまでのパスは確定しており、その他の停止状態にない出力決定部に対応するノードの計算が終わるのを待つ必要がないため、ネットワーク内の全てのノードのルーティングテーブル更新の確認を待たずに高速な通信が可能になる。
【図面の簡単な説明】
【００５８】
【図１】重み付きグラフの一例を示す説明図
【図２】重み付きグラフの他の例を示す説明図
【図３】重み付きグラフの最小経路をダイクストラ法により求解する際のフローチャート
【図４】重み付きグラフの最小経路をニューラルネットワークを用いて求解する際の回路の一例を示す構成図
【図５】遅延素子を用いたニューラルネットワークによる求解方法の流れ図
【図６】ダイクストラ法による求解方法と遅延素子を用いたニューラルネットワークによる求解方法との計算ステップの比較を示す説明図
【図７】重み付きグラフの最小経路をニューラルネットワークを用いて求解する際の回路の他の例を示す構成図
【図８】本発明の最小経路計算装置の第１の実施の形態を示す構成図
【図９】第１の実施の形態の変形例を示す構成図
【図１０】第１の実施の形態における動作の一例を示す信号波形図
【図１１】従来技術と本発明との計算ステップの比較を示す説明図
【図１２】従来技術と本発明とのハードウェア規模の定性的な比較を示す説明図
【図１３】従来技術と本発明との実装回路における計算速度の定性的な比較を示す説明図
【図１４】本発明の最小経路計算装置の第２の実施の形態を示す構成図
【図１５】本発明の最小経路計算装置の第３の実施の形態を示す構成図
【図１６】本発明の最小経路計算装置の第４の実施の形態を示す構成図
【符号の説明】
【００５９】
１１：初期入力部、１２−１〜１２−８，２１，３１，４１−１〜４１−８：遅延部、１３−１〜１３−４，２２，３２，４２−１〜４２−４：出力決定部、１４−１〜１４−４，１６−１〜１６−４：論理和回路、１５，４３−１〜４３−４：パス保存部、３３：スイッチ、４０Ａ〜４０Ｄ：ノード。
【図１】
2006246105.tif 000003
【図２】
2006246105.tif 000004
【図３】
2006246105.tif 000005
【図４】
2006246105.tif 000006
【図５】
2006246105.tif 000007
【図６】
2006246105.tif 000008
【図７】
2006246105.tif 000009
【図８】
2006246105.tif 000010
【図９】
2006246105.tif 000011
【図１０】
2006246105.tif 000012
【図１１】
2006246105.tif 000013
【図１２】
2006246105.tif 000014
【図１３】
2006246105.tif 000015
【図１４】
2006246105.tif 000016
【図１５】
2006246105.tif 000017
【図１６】
2006246105.tif 000018