Prolog:アローダイアグラム クリティカルパスを求める問題(基本情報処理技術者試験)を解いてみる

基本情報技術者試験で出てくるアローダイヤグラムでクリティカルパスを求める問題ですが、prologを使うとスッキリかけるのではないかと思い挑戦してみました。使用したprologの処理系はgprologとなります。

問題は以下のようなものでした。

問題のダイアグラム

問題の情報をprologで表現したものが以下となります。

ブランチ情報

% ブランチ情報
% branchInfo(ブランチ名, 元ノード, 先ノード, コスト).
branchInfo(a,   n1, n2, 1).
branchInfo(b,   n1, n3, 5).
branchInfo(c,   n2, n3, 3).
branchInfo(d,   n2, n4, 3).
branchInfo(e,   n3, n5, 4).
branchInfo(dmy, n5, n4, 0).
branchInfo(f,   n5, n6, 5).
branchInfo(g,   n4, n6, 4).

ブランチ情報からパス情報を得る述語を次のように定義しました。

パス

% パス
%path(元ノード, 先ノード, [ブランチ情報]).
path(StartNode, EndNode, [branchInfo(PathName, StartNode, EndNode, Weight)]) :-
  branchInfo(PathName, StartNode, EndNode, Weight).

path(StartNode, EndNode, [branchInfo(PathName, StartNode, NextStart, Weight)|T]) :-
  branchInfo(PathName, StartNode, NextStart, Weight),
  path(NextStart, EndNode, T).

これでStartNodeからEndNodeに至るブランチのリストが得られます。
例としてn1からn3のパスを確認してみます。

パスの確認(n1->n3)

| ?- path(n1,n3,P).

P = [branchInfo(b,n1,n3,5)] ? ;

P = [branchInfo(a,n1,n2,1),branchInfo(c,n2,n3,3)] ? ;

no

続いてブランチの名前とコストを集める述語を定義しました。

% pathCost(元ノード, 先ノード, result(パス, コスト)).
pathCost(StartNode, EndNode, result(Rout, Cost)) :-

  % パスを得る。
  path(StartNode, EndNode, R),

  % パスの経路名を集める。
  maplist(branchName, R, Rout),

  % パスのコストを得る。
  maplist(weight, R, Ws), sum_list(Ws, Cost).

branchName(branchInfo(Name,_,_,_), Name).
weight(branchInfo(_, _, _, Weight), Weight).

prologならではなのですが、pathCost(n1,n6,R)で問い合わせて「；」や「a」でn１からn6に至る各ルートのコストが得られるのでほぼ、答えは得ているような感じになりました。

パスのコスト(n1->n6)

| ?- pathCost(n1,n6,R).

R = result([a,c,e,f],13) ? ;

R = result([a,c,e,dmy,g],12) ? a

R = result([a,d,g],8)

R = result([b,e,f],14)

R = result([b,e,dmy,g],13)

no

クリティカルパスを求める述語を定義します。

クリティカルパス

% クリティカルパスを得る。
criticalPath(StartNode, EndNode, CriticalPath) :-

  % 各ルートとコスト情報を得る。
  findall(D,pathCost(StartNode,EndNode,D),Ds),

  % 最大コストの場所を得る。
  maplist(cost,Ds,Cs), max_list(Cs,Max), nth(Pos,Cs,Max),

  % クリティカルパスの情報を得る。
  nth(Pos,Ds,CriticalPath).

cost(result(_,C), C).

クリティカルパス(n1->n6)

クリティカルパスを問い合わせてみます。

| ?- criticalPath(n1,n6,Cp).

Cp = result([b,e,f],14) ? ;

no

一応全体は以下のようになります。

コード全体

% ブランチ情報
% branchInfo(ブランチ名, 元ノード, 先ノード, コスト).
branchInfo(a,   n1, n2, 1).
branchInfo(b,   n1, n3, 5).
branchInfo(c,   n2, n3, 3).
branchInfo(d,   n2, n4, 3).
branchInfo(e,   n3, n5, 4).
branchInfo(dmy, n5, n4, 0).
branchInfo(f,   n5, n6, 5).
branchInfo(g,   n4, n6, 4).

% パス
%path(元ノード, 先ノード, [パス情報]).
path(StartNode, EndNode, [branchInfo(PathName, StartNode, EndNode, Weight)]) :-
  branchInfo(PathName, StartNode, EndNode, Weight).

path(StartNode, EndNode, [branchInfo(PathName, StartNode, NextStart, Weight)|T]) :-
  branchInfo(PathName, StartNode, NextStart, Weight),
  path(NextStart, EndNode, T).

% pathCost(元ノード, 先ノード, result([ブランチ名], コスト)).
pathCost(StartNode, EndNode, result(BranchNames, Cost)) :-

  % ルートを得る。
  path(StartNode, EndNode, R),

  % ルートの経路名を集める。
  maplist(branchName, R, BranchNames),

  % ルートのコストを得る。
  maplist(weight, R, Ws), sum_list(Ws, Cost).

branchName(branchInfo(Name,_,_,_), Name).
weight(branchInfo(_, _, _, Weight), Weight).

% クリティカルパスを得る。
criticalPath(StartNode, EndNode, CriticalPath) :-

  % 各ルートとコスト情報を得る。
  findall(D,pathCost(StartNode,EndNode,D),Ds),

  % 最大コストの場所を得る。
  maplist(cost,Ds,Cs), max_list(Cs,Max), nth(Pos,Cs,Max),

  % クリティカルパスの情報を得る。
  nth(Pos,Ds,CriticalPath).

cost(result(_,C), C).