このディレクトリの索引
http://hibari.2ch.net/test/read.cgi/tech/1286978599/863
#  [1] 授業単元:自然言語処理  
#  [2] 問題文(含コード&リンク): 
#  ttp://nlp.dse.ibaraki.ac.jp/~shinnou/lecture/nl/rep1.pdf 
#  課題2のみです。 
# 課題2 次の図はループのない有向グラフである。辺の向きは記載されていないが、左から右である。
# V9 ! V12 とV13 ! V3 に注意すること。
# V0 をStart ノード、V6 をEnd ノードとして、V0 からV6 に至るパスのうちで、重みの和が
# 最大となるようなパスをViterbi アルゴリズムにより求めるプログラムをC あるいはJava
# で作成せよ。
# ただしグラフは、入力する形でなくても、プログラムの中で予め配列などで作成しておく形
# でもよい。
# > kadai2.exe
# 重みが最大のパスは
# V0 --> V* --> V* ・・・・--> V6
# 重みの和は***
# 有向グラフ('V0','V1',1).
# 有向グラフ('V1','V2',2).
# 有向グラフ('V2','V3',5).
# 有向グラフ('V3','V4',8).
# 有向グラフ('V4','V5',2).
# 有向グラフ('V5','V6',1).
# 有向グラフ('V7','V6',2).
# 有向グラフ('V8','V7',1).
# 有向グラフ('V9','V8',5).
# 有向グラフ('V10','V9',2).
# 有向グラフ('V10','V11',6).
# 有向グラフ('V11','V12',5).
# 有向グラフ('V12','V13',1).
# 有向グラフ('V0','V10',3).
# 有向グラフ('V1','V11',1).
# 有向グラフ('V2','V12',4).
# 有向グラフ('V8','V5',6).
# 有向グラフ('V9','V12',7).
# 有向グラフ('V9','V13',1).
# 有向グラフ('V11','V9',3).
# 有向グラフ('V12','V3',8).
# 有向グラフ('V12','V5',2).
# 有向グラフ('V13','V8',3).
# 有向グラフ('V13','V3',1).
# 
# グラフのデータ構造の例、0 が辺なし、‐の値は向きが逆、+の値は向きが正しい重み。
# #include 
# #define N 14 /* 頂点の数*/
# #define START 0 /* 始点の頂点番号*/
# #define END 6 /* 終点の頂点番号*/
# int g[N][N] = { /* グラフG はN 行N 列の配列*/
# /* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 */
# { 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0},
# { -1, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
# { 0, -2, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0},
# { 0, 0, -5, 0, 8, 0, 0, 0, 0, 0, 0, 0, -8, -1},
# { 0, 0, 0, -8, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0},
# { 0, 0, 0, 0, -2, 0, 1, 0, -6, 0, 0, 0, -2, 0},
# { 0, 0, 0, 0, 0, -1, 0, -2, 0, 0, 0, 0, 0, 0},
# { 0, 0, 0, 0, 0, 0, 2, 0, -1, 0, 0, 0, 0, 0},
# { 0, 0, 0, 0, 0, 6, 0, 1, 0, -5, 0, 0, 0, -3},
# { 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, -2, -3, 7, 1},
# { -3, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 6, 0, 0},
# { 0, -1, 0, 0, 0, 0, 0, 0, 0, 3, -6, 0, 5, 0},
# { 0, 0, -4, 8, 0, 2, 0, 0, 0, -7, 0, -5, 0, 1},
# { 0, 0, 0, 1, 0, 0, 0, 0, 3, -1, 0, 0, -1, 0}
# };
# ・・・・

有向グラフ('V0','V1',1).
有向グラフ('V1','V2',2).
有向グラフ('V2','V3',5).
有向グラフ('V3','V4',8).
有向グラフ('V4','V5',2).
有向グラフ('V5','V6',1).
有向グラフ('V7','V6',2).
有向グラフ('V8','V7',1).
有向グラフ('V9','V8',5).
有向グラフ('V10','V9',2).
有向グラフ('V10','V11',6).
有向グラフ('V11','V12',5).
有向グラフ('V12','V13',1).
有向グラフ('V0','V10',3).
有向グラフ('V1','V11',1).
有向グラフ('V2','V12',4).
有向グラフ('V8','V5',6).
有向グラフ('V9','V12',7).
有向グラフ('V9','V13',1).
有向グラフ('V11','V9',3).
有向グラフ('V12','V3',8).
有向グラフ('V12','V5',2).
有向グラフ('V13','V8',3).
有向グラフ('V13','V3',1).

'V0 をStart ノード、V6 をEnd ノードとして、V0 からV6 に至るパスのうちで、重みの和が最大となるようなパスを求める'(_最大の重みの和,_バス) :-
        findmax(_重みの和,到達('V0','V6',_重みの和,_パス),_最大の重みの和),
        到達('V0','V6',_最大の重みの和,_パス).

到達(_節,_隣接節,_重み,[_節,_隣接節]) :-
        有向グラフ(_節,_隣接節,_重み).
到達(_開始節,_到達節,_重みの和,[_開始節|_隣接節から到達節までのパス]) :-
        有向グラフ(_開始節,_隣接節,_重み),
        到達(_隣接節,_到達節,_隣接節から到達節までの重みの和,_隣接節から到達節までのパス),
        _重みの和 is _重み + _隣接節から到達節までの重みの和.


% findmax/3