"コンピュータを、複数のノードと、前記複数のノード同士の間を接続する複数のリンクと、からなるグラフの構造を表すグラフ構造情報を記憶する第1の記憶手段、前記各ノードの評価値を記憶する第2の記憶手段、前記各ノードのうち、算出すべき経路の始点とするノードの指定を受け付ける始点受付手段、前記第1の記憶手段に記憶された前記グラフ構造情報と、前記第2の記憶手段に記憶された前記各ノードの評価値と、に基づき、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する遷移確率計算手段、前記第2の記憶手段に記憶された前記各ノードの評価値と、前記遷移確率計算手段により計算された遷移確率群とに基づき、次の時刻における前記各ノードの評価値を計算する評価値計算手段、前記評価値計算手段により計算された次の時刻における前記各ノードの評価値により前記第2の記憶手段に記憶される前記各ノードの評価値を更新する評価値更新手段、前記遷移確率計算手段及び前記評価値計算手段に繰り返して計算を行わせ、その計算の繰り返しがあらかじめ定められた終了条件を満たした場合に繰り返しを終了し、その終了の時点において0でない評価値を持つノード群に基づいて、前記始点のノードを出発点として前記グラフのリンクを辿る経路のうち選ばれる可能性が最も高い経路を算出する経路算出手段、として機能させるためのプログラムであって、前記遷移確率計算手段は、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率として、リンク先の各ノードのうち評価値が高いノードほど遷移確率の値が高くなるように遷移確率を計算する、ことを特徴とする、プログラム。前記評価値計算手段は、前記グラフを構成する各ノードから前記始点のノードに対して0より大きいあらかじめ定められた確率でランダムに遷移するというランダム遷移を計算に入れて、前記次の時刻における前記各ノードの評価値を計算する、ことを特徴とする請求項1に記載のプログラム。前記コンピュータを、前記算出すべき経路の終点とするノードの指定を受け付ける終点受付手段、前記グラフに前記終点のノードと前記始点のノードとを結ぶリンクを追加するよう、前記第1の記憶手段に記憶される前記グラフ構造情報を変更するグラフ構造情報変更手段、として機能させると共に、前記遷移確率計算手段は、前記グラフ構造情報変更手段により変更された後の前記第1の記憶手段内の前記グラフ構造情報に基づいて、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する、ことを特徴とする請求項1又は2に記載のプログラム。前記コンピュータを、前記遷移確率計算手段及び前記評価値計算手段による計算の繰り返しを開始する前に、前記第1の記憶手段内の前記グラフ構造情報に対してページランクアルゴリズムの計算を行うことにより前記各ノードのページランク値を計算し、計算された前記各ノードのページランク値を、前記各ノードの評価値の初期値として前記第2の記憶手段に対して記憶させる初期値設定手段、として更に機能させることを特徴とする、請求項1から3のいずれか1項に記載のプログラム。複数のノードと、前記複数のノード同士の間を接続する複数のリンクと、からなるグラフの構造を表すグラフ構造情報を記憶する第1の記憶手段と、前記各ノードの評価値を記憶する第2の記憶手段と、前記各ノードのうち、算出すべき経路の始点とするノードの指定を受け付ける始点受付手段と、前記第1の記憶手段に記憶された前記グラフ構造情報と、前記第2の記憶手段に記憶された前記各ノードの評価値と、に基づき、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する遷移確率計算手段と、前記第2の記憶手段に記憶された前記各ノードの評価値と、前記遷移確率計算手段により計算された遷移確率群とに基づき、次の時刻における前記各ノードの評価値を計算する評価値計算手段と、前記評価値計算手段により計算された次の時刻における前記各ノードの評価値により前記第2の記憶手段に記憶される前記各ノードの評価値を更新する評価値更新手段と、前記遷移確率計算手段及び前記評価値計算手段に繰り返して計算を行わせ、その計算の繰り返しがあらかじめ定められた終了条件を満たした場合に繰り返しを終了し、その終了の時点において0でない評価値を持つノード群に基づいて、前記始点のノードを出発点として前記グラフのリンクを辿る経路のうち選ばれる可能性が最も高い経路を算出する経路算出手段と、を備え、前記遷移確率計算手段は、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率として、リンク先の各ノードのうち評価値が高いノードほど遷移確率の値が高くなるように遷移確率を計算する、ことを特徴とする、経路算出装置。本発明は、グラフ上のマルコフ連鎖において、指定されたノードを始点とする経路のうち、辿る可能性が最も高い経路を算出するための技術を提供する。請求項1に係る発明は、コンピュータを、複数のノードと、前記複数のノード同士の間を接続する複数のリンクと、からなるグラフの構造を表すグラフ構造情報を記憶する第1の記憶手段、前記各ノードの評価値を記憶する第2の記憶手段、前記各ノードのうち、算出すべき経路の始点とするノードの指定を受け付ける始点受付手段、前記第1の記憶手段に記憶された前記グラフ構造情報と、前記第2の記憶手段に記憶された前記各ノードの評価値と、に基づき、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する遷移確率計算手段、前記第2の記憶手段に記憶された前記各ノードの評価値と、前記遷移確率計算手段により計算された遷移確率群とに基づき、次の時刻における前記各ノードの評価値を計算する評価値計算手段、前記評価値計算手段により計算された次の時刻における前記各ノードの評価値により前記第2の記憶手段に記憶される前記各ノードの評価値を更新する評価値更新手段、前記遷移確率計算手段及び前記評価値計算手段に繰り返して計算を行わせ、その計算の繰り返しがあらかじめ定められた終了条件を満たした場合に繰り返しを終了し、その終了の時点において0でない評価値を持つノード群に基づいて、前記始点のノードを出発点として前記グラフのリンクを辿る経路のうち選ばれる可能性が最も高い経路を算出する経路算出手段、として機能させるためのプログラムであって、前記遷移確率計算手段は、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率として、リンク先の各ノードのうち評価値が高いノードほど遷移確率の値が高くなるように遷移確率を計算する、ことを特徴とする、プログラムである。請求項2に係る発明は、前記評価値計算手段は、前記グラフを構成する各ノードから前記始点のノードに対して0より大きいあらかじめ定められた確率でランダムに遷移するというランダム遷移を計算に入れて、前記次の時刻における前記各ノードの評価値を計算する、ことを特徴とする請求項1に記載のプログラムである。請求項3に係る発明は、前記コンピュータを、前記算出すべき経路の終点とするノードの指定を受け付ける終点受付手段、前記グラフに前記終点のノードと前記始点のノードとを結ぶリンクを追加するよう、前記第1の記憶手段に記憶される前記グラフ構造情報を変更するグラフ構造情報変更手段、として機能させると共に、前記遷移確率計算手段は、前記グラフ構造情報変更手段により変更された後の前記第1の記憶手段内の前記グラフ構造情報に基づいて、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する、ことを特徴とする請求項1又は2に記載のプログラムである。請求項4に係る発明は、前記コンピュータを、前記遷移確率計算手段及び前記評価値計算手段による計算の繰り返しを開始する前に、前記第1の記憶手段内の前記グラフ構造情報に対してページランクアルゴリズムの計算を行うことにより前記各ノードのページランク値を計算し、計算された前記各ノードのページランク値を、前記各ノードの評価値の初期値として前記第2の記憶手段に対して記憶させる初期値設定手段、として更に機能させることを特徴とする、請求項1から3のいずれか1項に記載のプログラムである。請求項5に係る発明は、複数のノードと、前記複数のノード同士の間を接続する複数のリンクと、からなるグラフの構造を表すグラフ構造情報を記憶する第1の記憶手段と、前記各ノードの評価値を記憶する第2の記憶手段と、前記各ノードのうち、算出すべき経路の始点とするノードの指定を受け付ける始点受付手段と、前記第1の記憶手段に記憶された前記グラフ構造情報と、前記第2の記憶手段に記憶された前記各ノードの評価値と、に基づき、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する遷移確率計算手段と、前記第2の記憶手段に記憶された前記各ノードの評価値と、前記遷移確率計算手段により計算された遷移確率群とに基づき、次の時刻における前記各ノードの評価値を計算する評価値計算手段と、前記評価値計算手段により計算された次の時刻における前記各ノードの評価値により前記第2の記憶手段に記憶される前記各ノードの評価値を更新する評価値更新手段と、前記遷移確率計算手段及び前記評価値計算手段に繰り返して計算を行わせ、その計算の繰り返しがあらかじめ定められた終了条件を満たした場合に繰り返しを終了し、その終了の時点において0でない評価値を持つノード群に基づいて、前記始点のノードを出発点として前記グラフのリンクを辿る経路のうち選ばれる可能性が最も高い経路を算出する経路算出手段と、を備え、前記遷移確率計算手段は、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率として、リンク先の各ノードのうち評価値が高いノードほど遷移確率の値が高くなるように遷移確率を計算する、ことを特徴とする、経路算出装置である。請求項1又は5に係る発明によれば、グラフ上のマルコフ連鎖において、指定されたノードを始点とする経路のうち、辿る可能性が最も高い経路を算出することができる。請求項2に係る発明によれば、辿る可能性が最も高い経路として、指定された始点のノードを必ず通る経路を求めることができる。請求項3に係る発明によれば、指定された始点と終点とを結ぶグラフ上の経路のうち、辿る可能性が最も高い経路を算出することができる。請求項4に係る発明によれば、辿る可能性が最も高い経路として算出される経路が、局所解に陥りにくくすることができる。この実施の形態では、エージェントがグラフネットワークとも呼ばれる上でマルコフランダムウォークマルコフ性を持つランダムウォークを行う場合に、そのグラフ上の様々な経路のうち、辿る確率が最も高い経路以下、このような経路を最確経路と呼ぶを求める。グラフ上の経路は、ノード間を結ぶリンクエッジとも呼ばれるの連なりである。エージェントは、グラフ上のノード間を、リンクを辿って渡り歩く何かであり、その何かは応用分野による。例えば、WWWワールドワイドウェブ上でのネットサーフィンへの応用を考える場合、エージェントは、ウェブページをサーフィングする閲覧者である。また、通信ネットワークにおけるデータ又は信号の転送経路を求める場合には、エージェントはそれら転送されるデータ又は信号である。実施の形態の処理内容について説明する前に、N個のノードからなるグラフ上で1人のエージェントが行うマルコフランダムウォークの定式化について概説する。時刻tにおいて、当該グラフのN個のノードのうちのn番目のノードnはノードの識別番号であり、1からNまでの整数のいずれかである。後述するmも同様にエージェントが存在する確率をpntとする。この場合、単位時間1だけ進んだ次の時刻t1において、n番目のノードにエージェントが存在する確率をpnt1は、次式1で求められる。ここで、Tnmは、当該グラフ上のm番目のノード以下、ノードmというからn番目のノード以下、ノードnというに遷移する確率遷移確率と呼ぶである。m及びnはそれぞれ1からNまでの整数なので、Tnmは、N×Nの行列を表す。このような行列は遷移行列又は遷移確率行列等と呼ばれる。ノードmからノードnへのリンクがグラフ状に存在しなければ、Tnmは常に0である。式1は、単位時間を1とする離散的なマルコフ連鎖を表すものであるが、連続時間でのマルコフ連鎖の時間発展は、次式2で表される。ページランクPageRank登録商標アルゴリズムは、このようなグラフ上でのマルコフランダムウォークの定常状態例えば、時刻が無限大になった極限において各ノードにエージェントが存在する確率、に基づいてページランク値を定めている。ここで、ページランクアルゴリズムは、遷移確率Tnmとして、グラフにおけるリンクの構造に基づき定められる固定的な値すなわち時間が経過しても変化しない値を用いている。より具体的には、ノードmに存在するエージェントは、ノードmから出る1以上のリンクを等確率で選択し、選択したリンクの先にあるノードへと遷移するものと仮定している。すなわち、ノードmからQ本のリンクが出ている場合、ノードmに存在するエージェントがそれらリンクのそれぞれを選択する確率は、すべて等しく1/Qである。例えば、図1に示す例では、グラフ上の特定のノードAから出る有向リンクは3本のみであり、それぞれノードB,C,Dに繋がっている。このようなリンク構造の場合、ノードAからノードB,C,Dに遷移する確率は、共に1/3となる。なお、ページランクアルゴリズムの具体的な内容については、前掲の非特許文献1及び2や、WWW上に存在するページランクアルゴリズムに関する様々な解説記事に詳しいので、ここでは説明を省略する。以上、マルコフ連鎖と、ページランクアルゴリズムにおける遷移確率の仮定について概説した。次に、この実施の形態における処理の特徴について説明する。この実施の形態では、あるノードにいるエージェントがそのノードから出る各リンクを選ぶ確率すなわち遷移確率を、それら各リンクの先のノードの評価値に応じて定める。すなわち、リンクの先のノードの評価値が高いほど、そのリンクが選ばれる確率が高くなるようにする。ここでいうノードの評価値は、ノードの重要度を表す値であり、グラフ上をマルコフランダムウォークするエージェントが当該ノードに居る確率存在確率に応じた値である。例えば、存在確率そのものを評価値として用いてもよいし、存在確率を変数とする単調増加関数を評価値としてもよい。例えば、多数のエージェントがグラフをマルコフランダムウォークする場合において、ある時点で各ノードに存在するエージェントの人数を評価値としてもよい。図2では、個々のエージェントをそれぞれ人型のマークで表しており、各ノードを示す円の中のマークの数すなわち人口が、当該ノードの評価値を示している。図2は、この実施の形態における遷移確率の考え方を説明するための図である。図2を用いて、ある時刻tにグラフ上のノードAに居るエージェントが、次の時刻tΔtΔtは単位時間にノードAのリンク先であるノードB,C,Dのそれぞれに遷移する遷移確率を説明する。図2の例では、図1の場合と同様、ノードAから出る有向リンクは、ノードB,C,Dにそれぞれ繋がる3本しか存在しないものとする。図2は、時刻tにおけるノードA,B,C,Dの評価値エージェントの人口分布を示している。図2では、時刻tにおけるノードB,C,Dの各々の評価値をpB,pC,pDとしている。そして、ある時刻tにグラフ上のノードAに居るエージェントが、次の時刻tΔtにノードBに遷移する確率は、図示のように、FpB/FpBFpCFpDと規定される。同様に、次の時刻tΔtにノードC,Dに遷移する確率は、それぞれ、FpC/FpBFpCFpDFpD/FpBFpCFpDと規定される。ここで、関数Fは、評価値pを変数とする単調増加関数である。遷移確率の計算式から分かるように、図2の例では、ある時刻tにノードAに居るエージェントは、次の時刻tΔtには必ずリンク先のノードA,B,Cのいずれかに移動するものとしているすなわち次の時刻にノードB,C,Dの各々に存在する確率の総和が1。すなわち、この方式では、グラフ上の評価値の総和は、時間が変化しても一定に保存される。図2の例では、時刻tにおいて遷移確率が最高となるのは最も評価値の高いノードCであり、次位はノードD、最下位はノードBである。したがって、次の時刻tΔtでは、もともと評価値人口が最高であったノードCの評価値が更に高まり、評価値が最低であったノードBの評価値は更に低くなる。したがって、時間を進めていくと、最終的には、ノードAから外に出るエージェントは、リンク先のノードB,C,Dのうちで評価値が最高であるノードCにすべて集まり、ノードD及びBに遷移するものは0になる。したがって、ノードAからノードCに向かう1つのリンクが、最も確からしいリンクとして残ることになる。このように、この実施の形態の遷移確率の求め方を用いると、あるノードから出るリンク群及びそれら各リンクの先にある各ノードの中でWTAWinner-Takes-All:勝者全獲得のメカニズムが働く。以上は、1つのノードからエージェントが出て行くところに着目した説明であるが、逆に1つの注目ノードに対して他の1以上のノードリンク元ノードと呼ぶからエージェントが入ってくる場合を考えると、ある時刻における注目ノードの評価値エージェントの人口は、1つ前の時刻のリンク元ノードの評価値×リンク元ノード注目ノード間の遷移確率をリンク元ノード全体で総和した値となる。したがって、例えばグラフ上のすべてのノードの評価値が等しいという条件から計算を開始すると、時間発展の初期の間は、ページランクアルゴリズムの場合と同様、他のノードからのリンクが多いノードほど高い評価値を得るという流れになる。このようにして高い評価値を得たノードは、この実施の形態のWTAのメカニズムに従って評価値を集めていき、最終的に残って最確経路の一部となる。グラフ上のすべてのノードについてそのノードから出る各リンクを選ぶ遷移確率を図2の例と同様の方法で求めるようにし、グラフ上のノードの評価値分布の時間発展を計算していくと、最終的には、グラフ上でエージェントが辿る確率の最も高い経路に沿ったノード群の評価値のみが正の値となり、その他のノードの評価値は0となる。例えば、初期条件として始点とするノードに全エージェントを集中すなわち始点ノードの評価値はある正の値、その他のノードの評価値は0させ、この実施の形態の方法に従って評価値分布の時間発展を計算していくと、その始点から始まる最確経路が求められる。以上、この実施の形態の処理の原理について説明した。次に、図3を参照して、このような原理に従った経路算出装置の具体例を説明する。図3の例は、ユーザから、グラフ上のノードのうち始点と終点の指定を受け付け、始点から始まってグラフ上の1以上のリンクを通って終点へと至る経路のうちの最確経路を求めるための装置構成の例である。この実施の形態の経路算出装置は、一例として、CPU中央演算装置等のプロセッサ100と、RAMランダムアクセスメモリ又は不揮発性記憶装置などの記憶装置200とを備えたコンピュータを用いて実現される。プロセッサ100は、以下に説明する各モジュール、すなわちグラフ構造情報入力部102、グラフ構造変更部104、初期条件設定部106、遷移確率計算部108、評価値計算部110、収束判定評価値更新部112、最確経路算出部114の機能を記述したプログラムを実行する。グラフ構造情報入力部102は、経路算出処理の対象とするグラフの構造を表すグラフ構造情報の入力を受け、入力されたグラフ構造情報を記憶装置200のグラフ構造情報記憶部202に記憶させる。グラフ構造情報としては、例えば、隣接行列Anmの形のデータを用いてもよい。隣接行列Anmは、ノードmからノードnにリンクがあればAnm=1、なければAnm=0となる成分からなるN行N列の行列Nはグラフを構成するノードの総数である。隣接行列はノード間のリンク構造を表すものであるが、グラフ構造情報には、この他に各ノードの名前その他の属性例えば、ウェブページをノードとする場合、ウェブページのタイトルやURLUniformResourceLocator等、又はリンクの属性などが含まれていてもよい。なお、グラフのリンク構造を表す情報の形式には、隣接行列以外にも様々なものがあり、この実施の形態ではそのような情報形式のいずれを用いてもよい。例えば、クローラーで収集したウェブページ間のハイパーリンクが構成するグラフを対象とする場合、それら収集したハイパーリンクの情報から、公知のソフトウエアを用いることでグラフ構造情報を生成し、生成されたグラフ構造情報をグラフ構造情報入力部102によりグラフ構造情報記憶部202に格納すればよい。始点終点指定受付部120は、最確経路を求めたい始点と終点の指定を受け付ける。始点、終点の指定の受け付け方は特に限定されない。例えば、始点終点指定受付部120は、グラフ構造情報記憶部202に記憶されたグラフ構造情報に基づいて当該経路算出装置の表示画面上にグラフを表示し、そのグラフ上から、ポインティングデバイス等を介して始点と終点のノードの指定を受け付けてもよい。また、ノードの属性等に関する検索を受け付け、検索結果の中から始点及び終点の選択を受け付けてもよい。グラフ構造変更部104は、グラフ構造情報記憶部202に記憶されているグラフ構造情報に対して、指定された終点から始点へのリンクを追加する変更を行う。すなわち、例えば、グラフの元の構造を表す隣接行列Anmに対し、終点ノードfから始点ノードiへのリンクを表わす別の隣接行列BnmすなわちBif=1、それ以外の成分は0の行列を加算する。この加算の結果得られた行列を改めて、経路探索の対象のグラフを表す隣接行列Anmとみなす。この終点から始点へのリンクの追加により、終点ノードに達したエージェントは始点ノードに戻る経路が必ずあるので、始点から終点へと移動していったエージェントが始点に戻らず他のノード群に移ってしまう可能性が低くなる。これにより、指定された始点及び終点の評価値エージェントの存在確率又は人口に応じた値が非ゼロになる可能性が高まる。このため、後述する遷移確率計算部108及び評価値計算部110によるノード群の評価値分布の時間発展の計算におけるWTA勝者全獲得において、指定された始点から指定された終点に至る経路が残りやすくなる。初期条件設定部106は、時間発展の初期条件として、グラフの各ノードに対して評価値の初期値を設定する。1つの例では、指定された始点ノードのみに正の評価値を与え例えばエージェントの存在確率を評価値とする場合、評価値1を与えるなど、他のノードの評価値は0とするという初期条件を設定する。この初期条件を採用した場合、時間発展の初期の段階では、始点ノードから流出する評価値エージェントの人口が、ページランクアルゴリズムと同様、入ってくるリンクが多いノードほど多く集まるような形で、各ノード間を伝搬していくことになる。また、別の例では、初期条件として、グラフ上の全ノードに対して等しい評価値を設定してもよい。更に別の例では、初期条件設定部106は、ページランクアルゴリズムにより各ノードのページランク値を求め、それら各ページランク値を各ノードの評価値の初期値として設定する。ページランク値は、グラフ構造情報記憶部202に記憶されたグラフ構造情報が示すリンク構造すなわち終点から始点へのリンクを追加した後の隣接行列に対し、周知のページランクアルゴリズム非特許文献1及び2等を参照を適用することにより求めればよい。各ノードの評価値の初期値としてページランク値を採用することで、局所解ローカルミニマム解に陥ることが回避され、大局的に見た最確経路が求められることとなる。初期条件設定部106は、上述のように定めた各ノードの評価値の初期値を、評価値記憶部204に記憶させる。評価値記憶部204は、ノード毎に、そのノードの評価値を記憶する。なお、評価値記憶部204に記憶される各ノードの評価値は、後述する遷移確率計算部108及び評価値計算部110による評価値分布の時間発展の計算の繰り返しの中で、繰り返しステップ毎に更新されていく。遷移確率計算部108は、評価値分布の時間発展の計算の繰り返しステップ毎に、そのステップの計算で用いるノード間の遷移確率の行列を計算する。この実施の形態では、遷移確率行列Tnmを次式3に従って計算する。式3は、エージェントがノードmからノードnへのリンクを通る遷移確率を示している。関数Fは、図2の例の場合と同様、評価値pを変数とする単調増加関数である。式3に含まれる定数εは、式3の分母の計算に現れる各ノードn’の評価値がすべて0である場合でもゼロで除する除算が生じないようにするための微小値である。εを除けば、式3は、図2に示した例と同様、分子はリンク先のノードnの時刻tにおける評価値であり、分母は、リンク元のノードmから出るすべてのリンクの先にあるノードの時刻tにおける評価値の総和となっている。すなわち、図2のリンク構造に式3を適用した場合、微小値εを除き、図に示した各リンクの遷移確率と同じ結果が得られる。なお、ノードmから出るリンクの先にある各ノードの評価値がすべて0の場合、式3から得られる遷移確率は、それらすべてのリンクについて、1/それらリンクの総数という同じ値となる。この値は、ページランクアルゴリズムにおけるノード間の遷移確率と同じ値である。例えば、指定された始点ノードのみに正の評価値を与え、他のノードの評価値は0とするという初期条件を採用した場合の時間発展の初期段階では、式3により、ページランクアルゴリズムと同じ仮定の下で評価値分布が変化していくことになる。その後、各ノードの評価値が正の値になれば、微小値であるεの影響はほとんど無視できるものとなり、図2に例示したのと同様、リンク元のノードの評価値が、リンク先の各ノードに対してそれら各ノードの評価値の大きさに応じて配分されていくことになる。遷移確率計算部108における遷移確率の計算は、以上のようにして、評価値記憶部204に記憶されている各ノードの最新時刻tの評価値pntと、グラフ構造情報記憶部202に記憶されたグラフ構造情報隣接行列Anmとに基づいて行われる。遷移確率計算部108は、式3の計算を、グラフ上のすべてのノードmとnのペアについて行う。評価値計算部110は、遷移確率計算部108で計算された時刻tにおける遷移確率行列式3と、評価値記憶部204に記憶されている時刻tにおける各ノードの評価値pntと、に基づき、微小な単位時刻Δtだけ進んだ次の時刻tΔtにおけるそれら各ノードの評価値pntΔtを計算する。この計算は、上述したマルコフ連鎖の時間発展の計算式2に従って行う。式2に、この実施の形態の遷移確率を示す式3を代入すると、次の式4が得られる。評価値計算部110は、式4を、初期条件設定部106で設定された初期条件の下で解く。ただし、評価値計算部110は、コンピュータによる離散時間での数値計算を行うので、式4を差分形式に書き換えた次の式5に従ってpntΔtを計算する。収束判定評価値更新部112は、評価値計算部110により計算されたpntΔtが収束したかを判定し、収束したと判定した場合、その時点で時間発展の繰り返し計算を打ち切る。例えば、計算された各ノードの評価値pntΔtと、評価値記憶部204に記憶されている評価値pntとの距離があらかじめ定めた閾値以下になった場合に、収束したと判定すればよい。なお、ここでの距離は、例えば、グラフ上のN個のノードの評価値の列をN次元空間の座標としたときの、時刻tΔtでの座標と時刻tでの座標とのユークリッド距離等を用いればよい。収束判定評価値更新部112は、収束していないと判定した場合は、各ノードnについて計算されたpntΔtを、最新の評価値として評価値記憶部204に書き込むことで、評価値記憶部204の記憶内容を更新する。そして、遷移確率計算部108及び評価値計算部110に対して、時刻をΔtだけ進め、次の繰り返しステップの計算を行わせる。言い換えれば、計算されたpntΔtをpntに置き換え、再び式4及び式5の計算を実行する。なお、収束判定評価値更新部112は、評価値分布pntΔtが収束しない場合でも、時間発展の繰り返しステップの回数があらかじめ定めた上限値に達した時点で、繰り返し計算を打ち切るようにしてもよい。最確経路算出部114は、収束判定評価値更新部112から収束と判定された時あるいは繰り返し計算を打ち切った時の評価値分布pntΔtのデータを受け取り、受け取ったデータに基づいて最確経路を算出する。ここで、最確経路算出部114は、受け取った評価値分布pntΔtのデータから、評価値が0でない非ゼロのノードを特定し、それら非ゼロのノード群から、指定された始点から終点への最確経路を求める。評価値分布pntΔtが収束した場合は、上述した遷移確率の定め方によるWTA勝者全獲得の性質から、評価値分布pntΔtのうち、最確経路上のノード以外のすべてのノードの評価値は0となっている。また、収束後の定常状態では、最確経路上の各ノードの評価値は、すべて等しい値となる。したがって、典型的には、受け取った評価値分布pntΔtにおいて評価値が非ゼロのノード群を、グラフ構造情報記憶部202内のグラフ構造情報が表すリンクを介して始点から終点まで連ねた系列が、最確経路となる。最確経路算出部114における非ゼロの判定は、評価値が厳密に0であるか否かという判定でもよいが、実際の数値計算では最確経路上のノード以外のノードの評価値が0より大きい微小値として残る可能性もあるので、あらかじめ定めた正の閾値よりも評価値が大きいノードを非ゼロのノードと判定するようにしてもよい。なお、評価値分布pntΔtが収束せずに計算を打ち切った場合も、最確経路上のノード以外のノードの大部分は評価値が0となっているはずである。ただし、この場合は、最確経路上のノード以外のノードの中にも、評価値が非ゼロのノードが存在する場合があり得る。この場合でも、正の閾値より評価値が大きいノードを非ゼロのノードと判定する方式で対応すればよい。最確経路算出部114は、このようにして求められた最確経路の情報をユーザに提示する。例えば、最確経路上のノードの系列をグラフの画像上で強調表示したものを最確経路算出装置の表示画面上に表示する。図3の装置による最確経路算出の具体例を、図4を参照して説明する。対象のグラフとして図4に示す、10個のノード1~10が実線矢印の有向リンクで結ばれたグラフが入力されたとする。そして、ユーザがこのグラフのノード1を始点に、ノード2を終点に指定したとする。この場合、図3の装置のグラフ構造変更部104は、終点ノード2から始点ノード1へのリンク破線矢印で示したを追加する。そして、初期条件設定部106は、各ノード1~10に対して、ページランクアルゴリズムにより求めたページランク値を評価値の初期値として設定する。ここで、時間発展の単位時間Δt=0.1として、その初期条件から出発して上述の式5を繰り返し計算し、評価値分布pntΔtが収束するまで計算を繰り返す。この例では、単調増加関数Fとして、Fx=x4を用いるただし、これはあくまで一例に過ぎない。繰り返し計算の収束時点では、各ノードnの評価値pnは、p1=p5=p8=p9=p10=p2≠0、p3=p4=p6=p7=0となる。これにより、1→5→8→9→10→2という経路が最確経路として求められることになる。ちなみに、図4のグラフでの始点ノード1から終点ノード2までの最短経路は1→3→4→2である。この例から分かるように、最確経路は、ダイクストラ法等により求められる最短経路とは一般には一致しない。次に、図5を参照して、実施の形態の経路算出装置の別の例を説明する。図3の例では指定された始点と終点を結ぶ最確経路を求めたのに対し、図5の例では、終点の指定は受けず、指定された始点から出発する経路のうちの最確経路を求める。図5において、図3に示した要素と同様の要素には同一符号を付す。図5の例が図3の例と異なる点は、始点終点指定受付部120の代わりに始点指定受付部122を有する点、グラフ構造変更部104を有しない点と、評価値計算部110aでの評価値計算の内容である。すなわち、まず、図5の例では、始点指定受付部122により始点のみの指定を受け付ける。終点が指定されないので、終点から始点へのリンクを追加するグラフ構造変更部104は不要である。図5の例における評価値計算部110aは、評価値分布の時間発展を、原理的には次の式6に従って計算する。実際の数値計算では、式6を差分形式に変換した次の式7を用いる。式6及び7は、指定された始点ノードに対して、他の各ノードからリンクの有無にかかわらずあらかじめ定められた非負の確率λでランダムにエージェントが遷移するというランダムジャンプを組み込んだ点が、式4及び5とは異なる。式6及び7において、添え字iは、始点ノードiを表す。また、δはクロネッカーのΔである。すなわち、項λδniは始点ノードiについては値λとなる。これは、始点ノードiには常にいずれかのノードから確率λでエージェント評価値の流入があることを示している。そして、全確率1からランダムジャンプによる確率λの部分を除いた残りの1-λについては、図3の例の場合と同様の遷移確率に従ってリンク元の各ノードからエージェントが流入してくるものとしている。また、始点ノードi以外のノードnについては、項λδniが0となり、この分だけ図3の例よりはエージェントの流入が減ることになるが、その減った分は始点ノードiにランダムジャンプで流入することになる。なお、λの具体的な値は、シミュレーションなどにより求めておけばよい。このような始点ノードiへのランダムジャンプを導入することで、始点ノードiの評価値は必ず非ゼロとなる。したがって、繰り返し計算の結果求められる評価値が非ゼロのノードの集合には、始点ノードiが必ず残ることになる。これにより、最終的に求められる最確経路は、始点ノードを通るものとなる。図5に示した要素のうち以上に説明した要素以外のものは、図3の例の場合と同様でよい。図5の装置による最確経路算出の具体例を、図6を参照して説明する。対象のグラフとして図6に示す、15個のノード1~15が実線矢印の有向リンクで結ばれたグラフが入力されたとする。そして、ユーザがこのグラフのノード1を始点に指定したとする。この場合、図5の装置の初期条件設定部106は、各ノード1~15に対して、ページランクアルゴリズムにより求めたページランク値を評価値の初期値として設定する。ここで、時間発展の単位時間Δt=0.1として、その初期条件から出発して上述の式7を繰り返し計算し、評価値分布pntΔtが収束するまで計算を繰り返す。この例では、単調増加関数Fとして、Fx=x4を用いるただし、これはあくまで一例に過ぎない。繰り返し計算の収束時点では、各ノードnの評価値pnは、p1=p4=p10=p2≠0、p3=p5=p6=p7=p8=p9=p11=p12=p13=p14=p15=0となる。これにより、1→4→10→2という経路が最確経路として求められることになる。ちなみに、図6のグラフの各ノードをページランク値の大きい順に並べると1,5,4,9,10,2,12,6,15,14,8,7,13,11の順になる。ここで、始点ノード1から順に、カレントのノードからリンク先のノードのうちページランク値が最大のノードに移動するという遷移規則を繰り返すことにより得られる経路は、1→5→9→2である。このように、ページランク値が最大のリンク先を選ぶという方式で求められる経路は、この実施の形態により求められる最確経路とは一般には一致しない。図5において破線の円で示したノードは、当該ノードから出る有向リンクを持たないノードいわゆるダングリングノードである。式6及び7におけるランダムジャンプ成分は、ダングリングノードに評価値が滞留することを防止する意義も有している。なお、図5の例における始点ノードへのランダムジャンプを考慮した評価値計算は、始点から終点への最確経路を求める図3の装置に適用してよい。始点へのランダムジャンプを導入することで、図3の装置により求められる最確経路は必ず始点を通るものとなる。また、図3の例において、始点へのランダムジャンプと同じ方式で終点へのランダムジャンプを組み込んだ計算式を用いてよい。これにより、図3の装置により求められる最確経路は必ず始点と終点を通るものとなる。以上に説明した実施の形態の評価値計算式4~7は、アあるノードにいるエージェントがそのノードから出るリンクの各々を選ぶ遷移確率は、それら各リンクの先のノードの評価値が高いほど高くなる、イ時間の変化によらず評価値の総和が保存される、ウ評価値は常に非負である、という条件を満たすものである。このような条件を満たすものであれば、式4~7に例示したものと異なる計算式を用いてもよい。以上に例示した経路算出装置は、例えば、汎用のコンピュータに上述の各機能モジュールの処理を表すプログラムを実行させることにより実現される。ここで、コンピュータは、例えば、ハードウエアとして、CPU等のマイクロプロセッサ、ランダムアクセスメモリRAMおよびリードオンリメモリROM等のメモリ一次記憶、HDDハードディスクドライブを制御するHDDコントローラ、各種I/O入出力インタフェース、ローカルエリアネットワークなどのネットワークとの接続のための制御を行うネットワークインタフェース等が、たとえばバスを介して接続された回路構成を有する。また、そのバスに対し、例えばI/Oインタフェース経由で、CDやDVDなどの可搬型ディスク記録媒体に対する読み取り及び/又は書き込みのためのディスクドライブ、フラッシュメモリなどの各種規格の可搬型の不揮発性記録媒体に対する読み取り及び/又は書き込みのためのメモリリーダライタ、などが接続されてもよい。上に例示した各機能モジュールの処理内容が記述されたプログラムがCDやDVD等の記録媒体を経由して、又はネットワーク等の通信手段経由で、ハードディスクドライブ等の固定記憶装置に保存され、コンピュータにインストールされる。固定記憶装置に記憶されたプログラムがRAMに読み出されCPU等のマイクロプロセッサにより実行されることにより、上に例示した機能モジュール群が実現される。なお、それら機能モジュール群のうちの一部又は全部を、専用LSI、ASICApplicationSpecificIntegratedCircuit、特定用途向け集積回路又はFPGAFieldProgrammableGateArray等のハードウエア回路として構成してもよい。"