(57)【要約】【課題】グラフ上のマルコフ連鎖において、指定されたノードを始点とする経路のうち、辿る可能性が最も高い経路を算出する。【解決手段】初期条件設定部１０６は、グラフ構造情報記憶部２０２に記憶されたグラフの各ノードの初期値を設定する。遷移確率計算部１０８は、ノード毎に、当該ノードからリンク先の各ノードへの遷移確率として、リンク先の各ノードのうち評価値が高いノードほど確率値が高くなるように遷移確率を計算する。評価値計算部１１０は、その遷移確率を用いて、マルコフ連鎖の計算により次の時刻の各ノードの評価値を計算する。収束判定・評価値更新部１１２は、計算された各ノードの評価値が収束するまで、時刻を進めながら遷移確率計算部１０８及び評価値計算部１１０に計算を繰り返させる。最確経路算出部１１４は、収束後の評価値が０でないノードを連ねた経路を、辿る可能性が最も高い経路（最確経路）として求める。【選択図】図３
2013041530.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
複数のノードと、前記複数のノード同士の間を接続する複数のリンクと、からなるグラフの構造を表すグラフ構造情報を記憶する第１の記憶手段、
前記各ノードの評価値を記憶する第２の記憶手段、
前記各ノードのうち、算出すべき経路の始点とするノードの指定を受け付ける始点受付手段、
前記第１の記憶手段に記憶された前記グラフ構造情報と、前記第２の記憶手段に記憶された前記各ノードの評価値と、に基づき、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する遷移確率計算手段、
前記第２の記憶手段に記憶された前記各ノードの評価値と、前記遷移確率計算手段により計算された遷移確率群とに基づき、次の時刻における前記各ノードの評価値を計算する評価値計算手段、
前記評価値計算手段により計算された次の時刻における前記各ノードの評価値により前記第２の記憶手段に記憶される前記各ノードの評価値を更新する評価値更新手段、
前記遷移確率計算手段及び前記評価値計算手段に繰り返して計算を行わせ、その計算の繰り返しがあらかじめ定められた終了条件を満たした場合に繰り返しを終了し、その終了の時点において０でない評価値を持つノード群に基づいて、前記始点のノードを出発点として前記グラフのリンクを辿る経路のうち選ばれる可能性が最も高い経路を算出する経路算出手段、
として機能させるためのプログラムであって、
前記遷移確率計算手段は、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率として、リンク先の各ノードのうち評価値が高いノードほど遷移確率の値が高くなるように遷移確率を計算する、
ことを特徴とする、プログラム。
【請求項２】
前記評価値計算手段は、前記グラフを構成する各ノードから前記始点のノードに対して０より大きいあらかじめ定められた確率でランダムに遷移するというランダム遷移を計算に入れて、前記次の時刻における前記各ノードの評価値を計算する、
ことを特徴とする請求項１に記載のプログラム。
【請求項３】
前記コンピュータを、
前記算出すべき経路の終点とするノードの指定を受け付ける終点受付手段、
前記グラフに前記終点のノードと前記始点のノードとを結ぶリンクを追加するよう、前記第１の記憶手段に記憶される前記グラフ構造情報を変更するグラフ構造情報変更手段、
として機能させると共に、
前記遷移確率計算手段は、前記グラフ構造情報変更手段により変更された後の前記第１の記憶手段内の前記グラフ構造情報に基づいて、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する、
ことを特徴とする請求項１又は２に記載のプログラム。
【請求項４】
前記コンピュータを、
前記遷移確率計算手段及び前記評価値計算手段による計算の繰り返しを開始する前に、前記第１の記憶手段内の前記グラフ構造情報に対してページランクアルゴリズムの計算を行うことにより前記各ノードのページランク値を計算し、計算された前記各ノードのページランク値を、前記各ノードの評価値の初期値として前記第２の記憶手段に対して記憶させる初期値設定手段、
として更に機能させることを特徴とする、請求項１から３のいずれか１項に記載のプログラム。
【請求項５】
複数のノードと、前記複数のノード同士の間を接続する複数のリンクと、からなるグラフの構造を表すグラフ構造情報を記憶する第１の記憶手段と、
前記各ノードの評価値を記憶する第２の記憶手段と、
前記各ノードのうち、算出すべき経路の始点とするノードの指定を受け付ける始点受付手段と、
前記第１の記憶手段に記憶された前記グラフ構造情報と、前記第２の記憶手段に記憶された前記各ノードの評価値と、に基づき、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する遷移確率計算手段と、
前記第２の記憶手段に記憶された前記各ノードの評価値と、前記遷移確率計算手段により計算された遷移確率群とに基づき、次の時刻における前記各ノードの評価値を計算する評価値計算手段と、
前記評価値計算手段により計算された次の時刻における前記各ノードの評価値により前記第２の記憶手段に記憶される前記各ノードの評価値を更新する評価値更新手段と、
前記遷移確率計算手段及び前記評価値計算手段に繰り返して計算を行わせ、その計算の繰り返しがあらかじめ定められた終了条件を満たした場合に繰り返しを終了し、その終了の時点において０でない評価値を持つノード群に基づいて、前記始点のノードを出発点として前記グラフのリンクを辿る経路のうち選ばれる可能性が最も高い経路を算出する経路算出手段と、
を備え、
前記遷移確率計算手段は、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率として、リンク先の各ノードのうち評価値が高いノードほど遷移確率の値が高くなるように遷移確率を計算する、
ことを特徴とする、経路算出装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路算出のためのプログラム及び経路算出装置に関する。
【背景技術】
【０００２】
様々な分野で、様々な目的のために、グラフ又はネットワーク上の経路探索が行われている。
【０００３】
特許文献１には、自動走行車の最適自動走行経路を探索する方法が記載されている。この方法における「最適」とは、報酬獲得に関する最適の意味である。また、この方法では、基本的に場合の数をすべて評価して、その中から最適経路を選ぶ。
【０００４】
特許文献２には、故障や輻輳に関して対応が容易なルーティングの方法が記載されている。この方法では、各ノードが、宛先となり得るアドレス毎に確率情報を有している。
【０００５】
特許文献３には、ネットワークシステムにおいて輻輳発生の確率を下げ、輻輳によるフレームの到着遅れや欠落が発生する頻度を減らすための技術が記載されている。この方法では、スパニング木を適宜更新するという方法を用いている。
【０００６】
特許文献４には、出発地から目的地までの最適経路を求める方法が開示されている。この方法では、グラフの各リンクに対してコストに関する確率分布が付与されており、コスト最小という制約条件下で、目的値に到達する確率を最大にする経路を求めている。
【０００７】
特許文献５には、リンク利用率のオーバーフローを抑制し、通常時及び故障時のトポロジにおける各最大リンク利用率を低減するＩＰ網ルーティング設計を行う技術が開示される。この技術では、オーバーフロー分をスイッチすることで、通常時及び故障時のトポロジにおける各最大リンク利用率の低減を図っている。
【０００８】
非特許文献１及び２には、ウェブページ及びハイパーリンクから構成されるグラフの構造から、個々のウェブページ（ノード）の重要度を示す「ページランク」を適切に定めるページランクアルゴリズムが示されている。概略的にいえば、ページランクアルゴリズムは、マルコフ連鎖の定常状態において各ノードに振り分けられた「確率」に応じて、各ノードのページランク値を定める。このアルゴリズムは、一人のエージェントがリンクを辿りながらノードからノードへと、グラフ上をランダムに歩き回る過程（マルコフランダムウォーク）とのアナロジーに基づいている。ノードにエージェントが存在する確率が高いほど、そのノードのページランク値が高くなる。
【０００９】
非特許文献３には、グラフ状の２つのノードの間の最短経路を多項式時間で求めるためのアルゴリズムであるダイクストラ法が開示されている。
【００１０】
非特許文献４には、マルコフ連鎖をサイクル（閉ループ）に分解する方法が示されている。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開平１０−２６０７２６号公報
【特許文献２】特開平１１−０７４９３４号公報
【特許文献３】特開２００４−１４０７７７号公報
【特許文献４】特開２００８−０７７６３６号公報
【特許文献５】特開２０１０−１３０３８２号公報
【非特許文献】
【００１２】
【非特許文献１】Page, L. et al. Stanford Digital Library Technologies Project (1998). [online]、[平成23年8月1日検索]、インターネット〈http://www-db.stanford.edu/~backrub/pageranksub.ps〉
【非特許文献２】Sergey Brin and Lawrence Page、“The Anatomy of a Large-Scale Hypertextual Web Search Engine”、[online]、Computer Science Department、 Stanford University、[平成23年8月1日検索]、インターネット〈http://infolab.stanford.edu/~backrub/google.html〉（特に“2.1.1 Description of PageRank Calculation”）
【非特許文献３】Dijkstra, E.W.、“A note on two problems in connexion with graphs”、Numerische Mathematik、Volume 1、Number 1、(1959)、269-271
【非特許文献４】Kalpazidou, S.L.、“Cycle Representations of Markov Processes”、Stochastic Modelling and Applied Probability、（米国）、第２版、Springer New York、2006年6月7日、p.17-54 (第2章および第3章)
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明は、グラフ上のマルコフ連鎖において、指定されたノードを始点とする経路のうち、辿る可能性が最も高い経路を算出するための技術を提供する。
【課題を解決するための手段】
【００１４】
請求項１に係る発明は、コンピュータを、複数のノードと、前記複数のノード同士の間を接続する複数のリンクと、からなるグラフの構造を表すグラフ構造情報を記憶する第１の記憶手段、前記各ノードの評価値を記憶する第２の記憶手段、前記各ノードのうち、算出すべき経路の始点とするノードの指定を受け付ける始点受付手段、前記第１の記憶手段に記憶された前記グラフ構造情報と、前記第２の記憶手段に記憶された前記各ノードの評価値と、に基づき、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する遷移確率計算手段、前記第２の記憶手段に記憶された前記各ノードの評価値と、前記遷移確率計算手段により計算された遷移確率群とに基づき、次の時刻における前記各ノードの評価値を計算する評価値計算手段、前記評価値計算手段により計算された次の時刻における前記各ノードの評価値により前記第２の記憶手段に記憶される前記各ノードの評価値を更新する評価値更新手段、前記遷移確率計算手段及び前記評価値計算手段に繰り返して計算を行わせ、その計算の繰り返しがあらかじめ定められた終了条件を満たした場合に繰り返しを終了し、その終了の時点において０でない評価値を持つノード群に基づいて、前記始点のノードを出発点として前記グラフのリンクを辿る経路のうち選ばれる可能性が最も高い経路を算出する経路算出手段、として機能させるためのプログラムであって、前記遷移確率計算手段は、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率として、リンク先の各ノードのうち評価値が高いノードほど遷移確率の値が高くなるように遷移確率を計算する、ことを特徴とする、プログラムである。
【００１５】
請求項２に係る発明は、前記評価値計算手段は、前記グラフを構成する各ノードから前記始点のノードに対して０より大きいあらかじめ定められた確率でランダムに遷移するというランダム遷移を計算に入れて、前記次の時刻における前記各ノードの評価値を計算する、ことを特徴とする請求項１に記載のプログラムである。
【００１６】
請求項３に係る発明は、前記コンピュータを、前記算出すべき経路の終点とするノードの指定を受け付ける終点受付手段、前記グラフに前記終点のノードと前記始点のノードとを結ぶリンクを追加するよう、前記第１の記憶手段に記憶される前記グラフ構造情報を変更するグラフ構造情報変更手段、として機能させると共に、前記遷移確率計算手段は、前記グラフ構造情報変更手段により変更された後の前記第１の記憶手段内の前記グラフ構造情報に基づいて、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する、ことを特徴とする請求項１又は２に記載のプログラムである。
【００１７】
請求項４に係る発明は、前記コンピュータを、前記遷移確率計算手段及び前記評価値計算手段による計算の繰り返しを開始する前に、前記第１の記憶手段内の前記グラフ構造情報に対してページランクアルゴリズムの計算を行うことにより前記各ノードのページランク値を計算し、計算された前記各ノードのページランク値を、前記各ノードの評価値の初期値として前記第２の記憶手段に対して記憶させる初期値設定手段、として更に機能させることを特徴とする、請求項１から３のいずれか１項に記載のプログラムである。
【００１８】
請求項５に係る発明は、複数のノードと、前記複数のノード同士の間を接続する複数のリンクと、からなるグラフの構造を表すグラフ構造情報を記憶する第１の記憶手段と、前記各ノードの評価値を記憶する第２の記憶手段と、前記各ノードのうち、算出すべき経路の始点とするノードの指定を受け付ける始点受付手段と、前記第１の記憶手段に記憶された前記グラフ構造情報と、前記第２の記憶手段に記憶された前記各ノードの評価値と、に基づき、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率を計算する遷移確率計算手段と、前記第２の記憶手段に記憶された前記各ノードの評価値と、前記遷移確率計算手段により計算された遷移確率群とに基づき、次の時刻における前記各ノードの評価値を計算する評価値計算手段と、前記評価値計算手段により計算された次の時刻における前記各ノードの評価値により前記第２の記憶手段に記憶される前記各ノードの評価値を更新する評価値更新手段と、前記遷移確率計算手段及び前記評価値計算手段に繰り返して計算を行わせ、その計算の繰り返しがあらかじめ定められた終了条件を満たした場合に繰り返しを終了し、その終了の時点において０でない評価値を持つノード群に基づいて、前記始点のノードを出発点として前記グラフのリンクを辿る経路のうち選ばれる可能性が最も高い経路を算出する経路算出手段と、を備え、前記遷移確率計算手段は、前記ノード毎に、当該ノードからリンク先の各ノードへの遷移確率として、リンク先の各ノードのうち評価値が高いノードほど遷移確率の値が高くなるように遷移確率を計算する、ことを特徴とする、経路算出装置である。
【発明の効果】
【００１９】
請求項１又は５に係る発明によれば、グラフ上のマルコフ連鎖において、指定されたノードを始点とする経路のうち、辿る可能性が最も高い経路を算出することができる。
【００２０】
請求項２に係る発明によれば、辿る可能性が最も高い経路として、指定された始点のノードを必ず通る経路を求めることができる。
【００２１】
請求項３に係る発明によれば、指定された始点と終点とを結ぶグラフ上の経路のうち、辿る可能性が最も高い経路を算出することができる。
【００２２】
請求項４に係る発明によれば、辿る可能性が最も高い経路として算出される経路が、局所解に陥りにくくすることができる。
【図面の簡単な説明】
【００２３】
【図１】ページランクアルゴリズムにおける遷移確率の定め方を説明するための図である。
【図２】実施の形態における遷移確率の定め方を説明するための図である。
【図３】実施の形態の経路算出装置の一例を示す図である。
【図４】グラフの具体例を示す図である。
【図５】実施の形態の経路算出装置の別の一例を示す図である。
【図６】グラフの具体例を示す図である。
【発明を実施するための形態】
【００２４】
この実施の形態では、エージェントがグラフ（ネットワークとも呼ばれる）上でマルコフランダムウォーク（マルコフ性を持つランダムウォーク）を行う場合に、そのグラフ上の様々な経路のうち、辿る確率が最も高い経路（以下、このような経路を「最確経路」と呼ぶ）を求める。グラフ上の経路は、ノード間を結ぶリンク（エッジとも呼ばれる）の連なりである。エージェントは、グラフ上のノード間を、リンクを辿って渡り歩く「何か」であり、その「何か」は応用分野による。例えば、ＷＷＷ（ワールド・ワイド・ウェブ）上でのネットサーフィンへの応用を考える場合、エージェントは、ウェブページをサーフィングする閲覧者である。また、通信ネットワークにおけるデータ又は信号の転送経路を求める場合には、エージェントはそれら転送されるデータ又は信号である。
【００２５】
実施の形態の処理内容について説明する前に、Ｎ個のノードからなるグラフ上で１人のエージェントが行うマルコフランダムウォークの定式化について概説する。
【００２６】
時刻ｔにおいて、当該グラフのＮ個のノードのうちのｎ番目のノード（ｎはノードの識別番号であり、１からＮまでの整数のいずれかである。後述するｍも同様）にエージェントが存在する確率をｐｎ（ｔ）とする。この場合、単位時間「１」だけ進んだ次の時刻（ｔ＋１）において、ｎ番目のノードにエージェントが存在する確率をｐｎ（ｔ＋１）は、次式（１）で求められる。
【００２７】
【数１】
2013041530.tif 000003
【００２８】
ここで、Ｔｎｍは、当該グラフ上のｍ番目のノード（以下、「ノードｍ」という）からｎ番目のノード（以下、「ノードｎ」という）に遷移する確率（「遷移確率」と呼ぶ）である。ｍ及びｎはそれぞれ１からＮまでの整数なので、Ｔｎｍは、Ｎ×Ｎの行列を表す。このような行列は遷移行列又は遷移確率行列等と呼ばれる。ノードｍからノードｎへのリンクがグラフ状に存在しなければ、Ｔｎｍは常に０である。
【００２９】
式（１）は、単位時間を「１」とする離散的なマルコフ連鎖を表すものであるが、連続時間でのマルコフ連鎖の時間発展は、次式（２）で表される。
【００３０】
【数２】
2013041530.tif 000004
【００３１】
ページランク（ＰａｇｅＲａｎｋ（登録商標））アルゴリズムは、このようなグラフ上でのマルコフランダムウォークの定常状態（例えば、時刻が無限大になった極限）において各ノードにエージェントが存在する確率、に基づいてページランク値を定めている。
【００３２】
ここで、ページランクアルゴリズムは、遷移確率Ｔｎｍとして、グラフにおけるリンクの構造に基づき定められる固定的な値（すなわち時間が経過しても変化しない値）を用いている。より具体的には、ノードｍに存在するエージェントは、ノードｍから出る１以上のリンクを等確率で選択し、選択したリンクの先にあるノードへと遷移するものと仮定している。すなわち、ノードｍからＱ本のリンクが出ている場合、ノードｍに存在するエージェントがそれらリンクのそれぞれを選択する確率は、すべて等しく１／Ｑである。例えば、図１に示す例では、グラフ上の特定のノードＡから出る有向リンクは３本のみであり、それぞれノードＢ，Ｃ，Ｄに繋がっている。このようなリンク構造の場合、ノードＡからノードＢ，Ｃ，Ｄに遷移する確率は、共に１／３となる。
【００３３】
なお、ページランクアルゴリズムの具体的な内容については、前掲の非特許文献１及び２や、ＷＷＷ上に存在するページランクアルゴリズムに関する様々な解説記事に詳しいので、ここでは説明を省略する。
【００３４】
以上、マルコフ連鎖と、ページランクアルゴリズムにおける遷移確率の仮定について概説した。
【００３５】
次に、この実施の形態における処理の特徴について説明する。
【００３６】
この実施の形態では、あるノードにいるエージェントがそのノードから出る各リンクを選ぶ確率（すなわち遷移確率）を、それら各リンクの先のノードの評価値に応じて定める。すなわち、リンクの先のノードの評価値が高いほど、そのリンクが選ばれる確率が高くなるようにする。ここでいうノードの「評価値」は、ノードの重要度を表す値であり、グラフ上をマルコフランダムウォークするエージェントが当該ノードに居る確率（存在確率）に応じた値である。例えば、存在確率そのものを評価値として用いてもよいし、存在確率を変数とする単調増加関数を評価値としてもよい。例えば、多数のエージェントがグラフをマルコフランダムウォークする場合において、ある時点で各ノードに存在するエージェントの人数を評価値としてもよい。図２では、個々のエージェントをそれぞれ人型のマークで表しており、各ノードを示す円の中のマークの数（すなわち人口）が、当該ノードの評価値を示している。
【００３７】
図２は、この実施の形態における遷移確率の考え方を説明するための図である。図２を用いて、ある時刻ｔにグラフ上のノードＡに居るエージェントが、次の時刻（ｔ＋Δｔ）（Δｔは単位時間）にノードＡのリンク先であるノードＢ，Ｃ，Ｄのそれぞれに遷移する遷移確率を説明する。図２の例では、図１の場合と同様、ノードＡから出る有向リンクは、ノードＢ，Ｃ，Ｄにそれぞれ繋がる３本しか存在しないものとする。図２は、時刻ｔにおけるノードＡ，Ｂ，Ｃ，Ｄの評価値（エージェントの人口）分布を示している。
【００３８】
図２では、時刻ｔにおけるノードＢ，Ｃ，Ｄの各々の評価値をｐＢ，ｐＣ，ｐＤとしている。そして、ある時刻ｔにグラフ上のノードＡに居るエージェントが、次の時刻（ｔ＋Δｔ）にノードＢに遷移する確率は、図示のように、
Ｆ（ｐＢ）／（Ｆ（ｐＢ）＋Ｆ（ｐＣ）＋Ｆ（ｐＤ））
と規定される。同様に、次の時刻（ｔ＋Δｔ）にノードＣ，Ｄに遷移する確率は、それぞれ、
Ｆ（ｐＣ）／（Ｆ（ｐＢ）＋Ｆ（ｐＣ）＋Ｆ（ｐＤ））
Ｆ（ｐＤ）／（Ｆ（ｐＢ）＋Ｆ（ｐＣ）＋Ｆ（ｐＤ））
と規定される。ここで、関数Ｆ（）は、評価値ｐを変数とする単調増加関数である。
【００３９】
遷移確率の計算式から分かるように、図２の例では、ある時刻ｔにノードＡに居るエージェントは、次の時刻（ｔ＋Δｔ）には必ずリンク先のノードＡ，Ｂ，Ｃのいずれかに移動するものとしている（すなわち次の時刻にノードＢ，Ｃ，Ｄの各々に存在する確率の総和が１）。すなわち、この方式では、グラフ上の評価値の総和は、時間が変化しても一定に保存される。
【００４０】
図２の例では、時刻ｔにおいて遷移確率が最高となるのは最も評価値の高いノードＣであり、次位はノードＤ、最下位はノードＢである。したがって、次の時刻（ｔ＋Δｔ）では、もともと評価値（人口）が最高であったノードＣの評価値が更に高まり、評価値が最低であったノードＢの評価値は更に低くなる。したがって、時間を進めていくと、最終的には、ノードＡから外に出るエージェントは、リンク先のノードＢ，Ｃ，Ｄのうちで評価値が最高であるノードＣにすべて集まり、ノードＤ及びＢに遷移するものは０になる。したがって、ノードＡからノードＣに向かう１つのリンクが、最も確からしいリンクとして残ることになる。
【００４１】
このように、この実施の形態の遷移確率の求め方を用いると、あるノードから出るリンク群（及びそれら各リンクの先にある各ノード）の中でＷＴＡ（Ｗｉｎｎｅｒ−Ｔａｋｅｓ−Ａｌｌ：勝者全獲得）のメカニズムが働く。
【００４２】
以上は、１つのノードからエージェントが出て行くところに着目した説明であるが、逆に１つの注目ノードに対して他の１以上のノード（「リンク元ノード」と呼ぶ）からエージェントが入ってくる場合を考えると、ある時刻における注目ノードの評価値（エージェントの人口）は、１つ前の時刻の（リンク元ノードの評価値×リンク元ノード・注目ノード間の遷移確率）をリンク元ノード全体で総和した値となる。したがって、例えばグラフ上のすべてのノードの評価値が等しいという条件から計算を開始すると、時間発展の初期の間は、ページランクアルゴリズムの場合と同様、他のノードからのリンクが多いノードほど高い評価値を得るという流れになる。このようにして高い評価値を得たノードは、この実施の形態のＷＴＡのメカニズムに従って評価値を集めていき、最終的に残って最確経路の一部となる。
【００４３】
グラフ上のすべてのノードについてそのノードから出る各リンクを選ぶ遷移確率を図２の例と同様の方法で求めるようにし、グラフ上のノードの評価値分布の時間発展を計算していくと、最終的には、グラフ上でエージェントが辿る確率の最も高い経路に沿ったノード群の評価値のみが正の値となり、その他のノードの評価値は０となる。
【００４４】
例えば、初期条件として始点とするノードに全エージェントを集中（すなわち始点ノードの評価値はある正の値、その他のノードの評価値は０）させ、この実施の形態の方法に従って評価値分布の時間発展を計算していくと、その始点から始まる最確経路が求められる。
【００４５】
以上、この実施の形態の処理の原理について説明した。次に、図３を参照して、このような原理に従った経路算出装置の具体例を説明する。図３の例は、ユーザから、グラフ上のノードのうち始点と終点の指定を受け付け、始点から始まってグラフ上の１以上のリンクを通って終点へと至る経路のうちの最確経路を求めるための装置構成の例である。
【００４６】
この実施の形態の経路算出装置は、一例として、ＣＰＵ（中央演算装置）等のプロセッサ１００と、ＲＡＭ（ランダムアクセスメモリ）又は不揮発性記憶装置などの記憶装置２００とを備えたコンピュータを用いて実現される。プロセッサ１００は、以下に説明する各モジュール、すなわちグラフ構造情報入力部１０２、グラフ構造変更部１０４、初期条件設定部１０６、遷移確率計算部１０８、評価値計算部１１０、収束判定・評価値更新部１１２、最確経路算出部１１４の機能を記述したプログラムを実行する。
【００４７】
グラフ構造情報入力部１０２は、経路算出処理の対象とするグラフの構造を表すグラフ構造情報の入力を受け、入力されたグラフ構造情報を記憶装置２００のグラフ構造情報記憶部２０２に記憶させる。グラフ構造情報としては、例えば、隣接行列（Ａnm）の形のデータを用いてもよい。隣接行列（Ａnm）は、ノードｍからノードｎにリンクがあればＡnm＝１、なければＡnm＝０となる成分からなるＮ行Ｎ列の行列（Ｎはグラフを構成するノードの総数）である。隣接行列はノード間のリンク構造を表すものであるが、グラフ構造情報には、この他に各ノードの名前その他の属性（例えば、ウェブページをノードとする場合、ウェブページのタイトルやＵＲＬ（Uniform Resource Locator）等）、又はリンクの属性などが含まれていてもよい。なお、グラフのリンク構造を表す情報の形式には、隣接行列以外にも様々なものがあり、この実施の形態ではそのような情報形式のいずれを用いてもよい。例えば、クローラーで収集したウェブページ間のハイパーリンクが構成するグラフを対象とする場合、それら収集したハイパーリンクの情報から、公知のソフトウエアを用いることでグラフ構造情報を生成し、生成されたグラフ構造情報をグラフ構造情報入力部１０２によりグラフ構造情報記憶部２０２に格納すればよい。
【００４８】
始点・終点指定受付部１２０は、最確経路を求めたい始点と終点の指定を受け付ける。始点、終点の指定の受け付け方は特に限定されない。例えば、始点・終点指定受付部１２０は、グラフ構造情報記憶部２０２に記憶されたグラフ構造情報に基づいて当該経路算出装置の表示画面上にグラフを表示し、そのグラフ上から、ポインティングデバイス等を介して始点と終点のノードの指定を受け付けてもよい。また、ノードの属性等に関する検索を受け付け、検索結果の中から始点及び終点の選択を受け付けてもよい。
【００４９】
グラフ構造変更部１０４は、グラフ構造情報記憶部２０２に記憶されているグラフ構造情報に対して、指定された終点から始点へのリンクを追加する変更を行う。すなわち、例えば、グラフの元の構造を表す隣接行列（Ａnm）に対し、終点ノードｆから始点ノードｉへのリンクを表わす別の隣接行列（Ｂnm）（すなわちＢif＝１、それ以外の成分は０の行列）を加算する。この加算の結果得られた行列を改めて、経路探索の対象のグラフを表す隣接行列（Ａnm）とみなす。
【００５０】
この終点から始点へのリンクの追加により、終点ノードに達したエージェントは始点ノードに戻る経路が必ずあるので、始点から終点へと移動していったエージェントが始点に戻らず他のノード群に移ってしまう可能性が低くなる。これにより、指定された始点及び終点の評価値（エージェントの存在確率又は人口に応じた値）が非ゼロになる可能性が高まる。このため、後述する遷移確率計算部１０８及び評価値計算部１１０によるノード群の評価値分布の時間発展の計算におけるＷＴＡ（勝者全獲得）において、指定された始点から指定された終点に至る経路が残りやすくなる。
【００５１】
初期条件設定部１０６は、時間発展の初期条件として、グラフの各ノードに対して評価値の初期値を設定する。１つの例では、指定された始点ノードのみに正の評価値を与え（例えばエージェントの存在確率を評価値とする場合、評価値「１」を与えるなど）、他のノードの評価値は０とするという初期条件を設定する。この初期条件を採用した場合、時間発展の初期の段階では、始点ノードから流出する評価値（エージェントの人口）が、ページランクアルゴリズムと同様、入ってくるリンクが多いノードほど多く集まるような形で、各ノード間を伝搬していくことになる。また、別の例では、初期条件として、グラフ上の全ノードに対して等しい評価値を設定してもよい。
【００５２】
更に別の例では、初期条件設定部１０６は、ページランクアルゴリズムにより各ノードのページランク値を求め、それら各ページランク値を各ノードの評価値の初期値として設定する。ページランク値は、グラフ構造情報記憶部２０２に記憶されたグラフ構造情報が示すリンク構造（すなわち終点から始点へのリンクを追加した後の隣接行列）に対し、周知のページランクアルゴリズム（非特許文献１及び２等を参照）を適用することにより求めればよい。各ノードの評価値の初期値としてページランク値を採用することで、局所解（ローカルミニマム解）に陥ることが回避され、大局的に見た最確経路が求められることとなる。
【００５３】
初期条件設定部１０６は、上述のように定めた各ノードの評価値の初期値を、評価値記憶部２０４に記憶させる。
【００５４】
評価値記憶部２０４は、ノード毎に、そのノードの評価値を記憶する。なお、評価値記憶部２０４に記憶される各ノードの評価値は、後述する遷移確率計算部１０８及び評価値計算部１１０による評価値分布の時間発展の計算の繰り返しの中で、繰り返しステップ毎に更新されていく。
【００５５】
遷移確率計算部１０８は、評価値分布の時間発展の計算の繰り返しステップ毎に、そのステップの計算で用いるノード間の遷移確率の行列を計算する。この実施の形態では、遷移確率行列Ｔｎｍを次式（３）に従って計算する。
【００５６】
【数３】
2013041530.tif 000005
【００５７】
式（３）は、エージェントがノードｍからノードｎへのリンクを通る遷移確率を示している。関数Ｆ（）は、図２の例の場合と同様、評価値ｐを変数とする単調増加関数である。式（３）に含まれる定数εは、式（３）の分母の計算に現れる各ノードｎ’の評価値がすべて０である場合でもゼロで除する除算が生じないようにするための微小値である。εを除けば、式（３）は、図２に示した例と同様、分子はリンク先のノードｎの時刻ｔにおける評価値であり、分母は、リンク元のノードｍから出るすべてのリンクの先にあるノードの時刻ｔにおける評価値の総和となっている。すなわち、図２のリンク構造に式（３）を適用した場合、微小値εを除き、図に示した各リンクの遷移確率と同じ結果が得られる。
【００５８】
なお、ノードｍから出るリンクの先にある各ノードの評価値がすべて０の場合、式（３）から得られる遷移確率は、それらすべてのリンクについて、１／（それらリンクの総数）という同じ値となる。この値は、ページランクアルゴリズムにおけるノード間の遷移確率と同じ値である。例えば、指定された始点ノードのみに正の評価値を与え、他のノードの評価値は０とするという初期条件を採用した場合の時間発展の初期段階では、式（３）により、ページランクアルゴリズムと同じ仮定の下で評価値分布が変化していくことになる。その後、各ノードの評価値が正の値になれば、微小値であるεの影響はほとんど無視できるものとなり、図２に例示したのと同様、リンク元のノードの評価値が、リンク先の各ノードに対してそれら各ノードの評価値の大きさに応じて配分されていくことになる。
【００５９】
遷移確率計算部１０８における遷移確率の計算は、以上のようにして、評価値記憶部２０４に記憶されている各ノードの最新（時刻ｔ）の評価値ｐｎ（ｔ）と、グラフ構造情報記憶部２０２に記憶されたグラフ構造情報（隣接行列（Ａnm））とに基づいて行われる。遷移確率計算部１０８は、式（３）の計算を、グラフ上のすべてのノードｍとｎのペアについて行う。
【００６０】
評価値計算部１１０は、遷移確率計算部１０８で計算された時刻ｔにおける遷移確率行列（式（３））と、評価値記憶部２０４に記憶されている時刻ｔにおける各ノードの評価値ｐｎ（ｔ）と、に基づき、微小な単位時刻Δｔだけ進んだ次の時刻（ｔ＋Δｔ）におけるそれら各ノードの評価値ｐｎ（ｔ＋Δｔ）を計算する。
【００６１】
この計算は、上述したマルコフ連鎖の時間発展の計算式（２）に従って行う。式（２）に、この実施の形態の遷移確率を示す式（３）を代入すると、次の式（４）が得られる。
【００６２】
【数４】
2013041530.tif 000006
【００６３】
評価値計算部１１０は、式（４）を、初期条件設定部１０６で設定された初期条件の下で解く。ただし、評価値計算部１１０は、コンピュータによる離散時間での数値計算を行うので、式（４）を差分形式に書き換えた次の式（５）に従ってｐｎ（ｔ＋Δｔ）を計算する。
【００６４】
【数５】
2013041530.tif 000007
【００６５】
収束判定・評価値更新部１１２は、評価値計算部１１０により計算されたｐｎ（ｔ＋Δｔ）が収束したかを判定し、収束したと判定した場合、その時点で時間発展の繰り返し計算を打ち切る。例えば、計算された各ノードの評価値ｐｎ（ｔ＋Δｔ）と、評価値記憶部２０４に記憶されている評価値ｐｎ（ｔ）との距離があらかじめ定めた閾値以下になった場合に、収束したと判定すればよい。なお、ここでの「距離」は、例えば、グラフ上のＮ個のノードの評価値の列をＮ次元空間の座標としたときの、時刻（ｔ＋Δｔ）での座標と時刻ｔでの座標とのユークリッド距離等を用いればよい。
【００６６】
収束判定・評価値更新部１１２は、収束していないと判定した場合は、各ノードｎについて計算されたｐｎ（ｔ＋Δｔ）を、最新の評価値として評価値記憶部２０４に書き込むことで、評価値記憶部２０４の記憶内容を更新する。そして、遷移確率計算部１０８及び評価値計算部１１０に対して、時刻をΔｔだけ進め、次の繰り返しステップの計算を行わせる。言い換えれば、計算されたｐｎ（ｔ＋Δｔ）をｐｎ（ｔ）に置き換え、再び式（４）及び式（５）の計算を実行する。
【００６７】
なお、収束判定・評価値更新部１１２は、評価値分布ｐｎ（ｔ＋Δｔ）が収束しない場合でも、時間発展の繰り返しステップの回数があらかじめ定めた上限値に達した時点で、繰り返し計算を打ち切るようにしてもよい。
【００６８】
最確経路算出部１１４は、収束判定・評価値更新部１１２から収束と判定された時（あるいは繰り返し計算を打ち切った時）の評価値分布ｐｎ（ｔ＋Δｔ）のデータを受け取り、受け取ったデータに基づいて最確経路を算出する。ここで、最確経路算出部１１４は、受け取った評価値分布ｐｎ（ｔ＋Δｔ）のデータから、評価値が０でない（非ゼロ）のノードを特定し、それら「非ゼロ」のノード群から、指定された始点から終点への最確経路を求める。評価値分布ｐｎ（ｔ＋Δｔ）が収束した場合は、上述した遷移確率の定め方によるＷＴＡ（勝者全獲得）の性質から、評価値分布ｐｎ（ｔ＋Δｔ）のうち、最確経路上のノード以外のすべてのノードの評価値は０となっている。また、収束後の定常状態では、最確経路上の各ノードの評価値は、すべて等しい値となる。したがって、典型的には、受け取った評価値分布ｐｎ（ｔ＋Δｔ）において評価値が非ゼロのノード群を、グラフ構造情報記憶部２０２内のグラフ構造情報が表すリンクを介して始点から終点まで連ねた系列が、最確経路となる。
【００６９】
最確経路算出部１１４における「非ゼロ」の判定は、評価値が厳密に０であるか否かという判定でもよいが、実際の数値計算では最確経路上のノード以外のノードの評価値が０より大きい微小値として残る可能性もあるので、あらかじめ定めた正の閾値よりも評価値が大きいノードを「非ゼロ」のノードと判定するようにしてもよい。
【００７０】
なお、評価値分布ｐｎ（ｔ＋Δｔ）が収束せずに計算を打ち切った場合も、最確経路上のノード以外のノードの大部分は評価値が０となっているはずである。ただし、この場合は、最確経路上のノード以外のノードの中にも、評価値が非ゼロのノードが存在する場合があり得る。この場合でも、正の閾値より評価値が大きいノードを「非ゼロ」のノードと判定する方式で対応すればよい。
【００７１】
最確経路算出部１１４は、このようにして求められた最確経路の情報をユーザに提示する。例えば、最確経路上のノードの系列をグラフの画像上で強調表示したものを最確経路算出装置の表示画面上に表示する。
【００７２】
図３の装置による最確経路算出の具体例を、図４を参照して説明する。対象のグラフとして図４に示す、１０個のノード１〜１０が実線矢印の有向リンクで結ばれたグラフが入力されたとする。そして、ユーザがこのグラフのノード１を始点に、ノード２を終点に指定したとする。この場合、図３の装置のグラフ構造変更部１０４は、終点ノード２から始点ノード１へのリンク（破線矢印で示した）を追加する。そして、初期条件設定部１０６は、各ノード１〜１０に対して、ページランクアルゴリズムにより求めたページランク値を評価値の初期値として設定する。ここで、時間発展の単位時間Δｔ＝０．１として、その初期条件から出発して上述の式（５）を繰り返し計算し、評価値分布ｐｎ（ｔ＋Δｔ）が収束するまで計算を繰り返す。この例では、単調増加関数Ｆ（）として、Ｆ（ｘ）＝ｘ４を用いる（ただし、これはあくまで一例に過ぎない）。繰り返し計算の収束時点では、各ノードｎの評価値ｐｎは、ｐ１＝ｐ５＝ｐ８＝ｐ９＝ｐ１０＝ｐ２≠０、ｐ３＝ｐ４＝ｐ６＝ｐ７＝０となる。これにより、１→５→８→９→１０→２という経路が最確経路として求められることになる。
【００７３】
ちなみに、図４のグラフでの始点ノード１から終点ノード２までの最短経路は１→３→４→２である。この例から分かるように、最確経路は、ダイクストラ法等により求められる最短経路とは一般には一致しない。
【００７４】
次に、図５を参照して、実施の形態の経路算出装置の別の例を説明する。図３の例では指定された始点と終点を結ぶ最確経路を求めたのに対し、図５の例では、終点の指定は受けず、指定された始点から出発する経路のうちの最確経路を求める。図５において、図３に示した要素と同様の要素には同一符号を付す。
【００７５】
図５の例が図３の例と異なる点は、始点・終点指定受付部１２０の代わりに始点指定受付部１２２を有する点、グラフ構造変更部１０４を有しない点と、評価値計算部１１０ａでの評価値計算の内容である。
【００７６】
すなわち、まず、図５の例では、始点指定受付部１２２により始点のみの指定を受け付ける。終点が指定されないので、終点から始点へのリンクを追加するグラフ構造変更部１０４は不要である。
【００７７】
図５の例における評価値計算部１１０ａは、評価値分布の時間発展を、原理的には次の式（６）に従って計算する。
【００７８】
【数６】
2013041530.tif 000008
【００７９】
実際の数値計算では、式（６）を差分形式に変換した次の式（７）を用いる。
【００８０】
【数７】
2013041530.tif 000009
【００８１】
式（６）及び（７）は、指定された始点ノードに対して、他の各ノードから（リンクの有無にかかわらず）あらかじめ定められた非負の確率λでランダムにエージェントが遷移するという「ランダムジャンプ」を組み込んだ点が、式（４）及び（５）とは異なる。式（６）及び（７）において、添え字ｉは、始点ノードｉを表す。また、「δ」はクロネッカーのΔである。すなわち、項「λδｎｉ」は始点ノードｉについては値λとなる。これは、始点ノードiには常にいずれかのノードから確率λでエージェント（評価値）の流入があることを示している。そして、全確率１からランダムジャンプによる確率λの部分を除いた残りの（１−λ）については、図３の例の場合と同様の遷移確率に従ってリンク元の各ノードからエージェントが流入してくるものとしている。また、始点ノードｉ以外のノードｎについては、項「λδｎｉ」が０となり、この分だけ図３の例よりはエージェントの流入が減ることになるが、その減った分は始点ノードｉにランダムジャンプで流入することになる。なお、λの具体的な値は、シミュレーションなどにより求めておけばよい。
【００８２】
このような始点ノードｉへのランダムジャンプを導入することで、始点ノードｉの評価値は必ず非ゼロとなる。したがって、繰り返し計算の結果求められる評価値が非ゼロのノードの集合には、始点ノードｉが必ず残ることになる。これにより、最終的に求められる最確経路は、始点ノードを通るものとなる。
【００８３】
図５に示した要素のうち以上に説明した要素以外のものは、図３の例の場合と同様でよい。
【００８４】
図５の装置による最確経路算出の具体例を、図６を参照して説明する。対象のグラフとして図６に示す、１５個のノード１〜１５が実線矢印の有向リンクで結ばれたグラフが入力されたとする。そして、ユーザがこのグラフのノード１を始点に指定したとする。この場合、図５の装置の初期条件設定部１０６は、各ノード１〜１５に対して、ページランクアルゴリズムにより求めたページランク値を評価値の初期値として設定する。ここで、時間発展の単位時間Δｔ＝０．１として、その初期条件から出発して上述の式（７）を繰り返し計算し、評価値分布ｐｎ（ｔ＋Δｔ）が収束するまで計算を繰り返す。この例では、単調増加関数Ｆ（）として、Ｆ（ｘ）＝ｘ４を用いる（ただし、これはあくまで一例に過ぎない）。繰り返し計算の収束時点では、各ノードｎの評価値ｐｎは、ｐ１＝ｐ４＝ｐ１０＝ｐ２≠０、ｐ３＝ｐ５＝ｐ６＝ｐ７＝ｐ８＝ｐ９＝ｐ１１＝ｐ１２＝ｐ１３＝ｐ１４＝ｐ１５＝０となる。これにより、１→４→１０→２という経路が最確経路として求められることになる。
【００８５】
ちなみに、図６のグラフの各ノードをページランク値の大きい順に並べると１，５，４，９，１０，２，１２，６，１５，１４，８，７，１３，１１の順になる。ここで、始点ノード１から順に、「カレントのノードからリンク先のノードのうちページランク値が最大のノードに移動する」という遷移規則を繰り返すことにより得られる経路は、１→５→９→２である。このように、ページランク値が最大のリンク先を選ぶという方式で求められる経路は、この実施の形態により求められる最確経路とは一般には一致しない。
【００８６】
図５において破線の円で示したノードは、当該ノードから出る有向リンクを持たないノード（いわゆるダングリングノード）である。式（６）及び（７）におけるランダムジャンプ成分は、ダングリングノードに評価値が滞留することを防止する意義も有している。
【００８７】
なお、図５の例における始点ノードへのランダムジャンプを考慮した評価値計算は、始点から終点への最確経路を求める図３の装置に適用してよい。始点へのランダムジャンプを導入することで、図３の装置により求められる最確経路は必ず始点を通るものとなる。また、図３の例において、始点へのランダムジャンプと同じ方式で終点へのランダムジャンプを組み込んだ計算式を用いてよい。これにより、図３の装置により求められる最確経路は必ず始点と終点を通るものとなる。
【００８８】
以上に説明した実施の形態の評価値計算（式（４）〜（７））は、（ア）あるノードにいるエージェントがそのノードから出るリンクの各々を選ぶ遷移確率は、それら各リンクの先のノードの評価値が高いほど高くなる、（イ）時間の変化によらず評価値の総和が保存される、（ウ）評価値は常に非負である、という条件を満たすものである。このような条件を満たすものであれば、式（４）〜（７）に例示したものと異なる計算式を用いてもよい。
【００８９】
以上に例示した経路算出装置は、例えば、汎用のコンピュータに上述の各機能モジュールの処理を表すプログラムを実行させることにより実現される。ここで、コンピュータは、例えば、ハードウエアとして、ＣＰＵ等のマイクロプロセッサ、ランダムアクセスメモリ（ＲＡＭ）およびリードオンリメモリ（ＲＯＭ）等のメモリ（一次記憶）、ＨＤＤ（ハードディスクドライブ）を制御するＨＤＤコントローラ、各種Ｉ／Ｏ（入出力）インタフェース、ローカル・エリア・ネットワークなどのネットワークとの接続のための制御を行うネットワークインタフェース等が、たとえばバスを介して接続された回路構成を有する。また、そのバスに対し、例えばＩ／Ｏインタフェース経由で、ＣＤやＤＶＤなどの可搬型ディスク記録媒体に対する読み取り及び／又は書き込みのためのディスクドライブ、フラッシュメモリなどの各種規格の可搬型の不揮発性記録媒体に対する読み取り及び／又は書き込みのためのメモリリーダライタ、などが接続されてもよい。上に例示した各機能モジュールの処理内容が記述されたプログラムがＣＤやＤＶＤ等の記録媒体を経由して、又はネットワーク等の通信手段経由で、ハードディスクドライブ等の固定記憶装置に保存され、コンピュータにインストールされる。固定記憶装置に記憶されたプログラムがＲＡＭに読み出されＣＰＵ等のマイクロプロセッサにより実行されることにより、上に例示した機能モジュール群が実現される。なお、それら機能モジュール群のうちの一部又は全部を、専用ＬＳＩ(Large Scale Integration)、ＡＳＩＣ（Application Specific Integrated Circuit、特定用途向け集積回路）又はＦＰＧＡ（Field Programmable Gate Array）等のハードウエア回路として構成してもよい。
【産業上の利用可能性】
【００９０】
上述の実施の形態の経路算出装置、又はその経路算出装置が実行する方法は、グラフ構造において、ページランクアルゴリズムが定めるところの、「点」としてのノードの重要度だけでなく、ノードがリンクで一列に結ばれて構成される「経路」の重要度を定めることが求められる場合一般に利用され得る。例えば、引用関係により構成される文書のネットワークにおいて、文書Ａから出発して、Ａの次に読むべき文書Ｂ、Ｂの次に読むべき文書Ｃ、Ｃの次に読むべき文書Ｄ、…という具合に、一連の文書Ｂ、Ｃ、Ｄ、…の系列を推薦する場合である。一般に、Ａからは複数の文書に引用のリンクが張られており、その一つ一つからもさらに複数の文書に引用のリンクが張られている。従って一般には、Ａを始点とする非常に多くの経路がある。それらの中から一つを選ぶために、個々の経路の重要度、あるいは、どれが最も重要な経路か、ということを定める必要がある。したがって、文書間の引用関係を表す有向グラフのデータが与えられ、その中から始点とする文書の指定をユーザから受け付ければ、その有向グラフのデータに対して上記実施の形態の処理を実行することにより、その始点からみて最も重要と考えられる引用の経路（すなわち引用の経路として最も確からしい経路）が求められることになる。
【００９１】
また、上記実施の形態の手法は、ウェブページの閲覧順序の推薦にも利用し得る。例えば、ウェブページＡから出発して、Ａの次に閲覧すべきページＢ、Ｂの次に閲覧すべきページＣ、Ｃの次に閲覧すべきページＤ、…という具合に、ウェブページの閲覧順Ｂ、Ｃ、Ｄ、…を推薦する場合である。この場合も引用のときと同様、非常に多くの閲覧経路があり、それらの中から一つを選ぶために、個々の経路の重要度、あるいは、どれが最も重要な経路か、ということを定める必要がある。処理の適用対象であるウェブページのリンク構造がなすグラフの情報は、例えば、周知のクローラー技術等を用いて収集すればよい。ユーザが始点とするウェブページを指定すると、そのグラフに対して上記実施の形態の処理を実行することにより、その始点からみて最もユーザが辿りやすいと考えられるウェブページの順序系列が求められる。
【符号の説明】
【００９２】
１００  プロセッサ、１０２  グラフ構造情報入力部、１０４  グラフ構造変更部、１０６  初期条件設定部、１０８  遷移確率計算部、１１０  評価値計算部、１１２  収束判定・評価値更新部、１１４  最確経路算出部、１２０  始点・終点指定受付部、１２２  始点指定受付部、２００  記憶装置、２０２  グラフ構造情報記憶部、２０４  評価値記憶部。
【図１】
2013041530.tif 000010
【図２】
2013041530.tif 000011
【図３】
2013041530.tif 000012
【図４】
2013041530.tif 000013
【図５】
2013041530.tif 000014
【図６】
2013041530.tif 000015