最短経路問題

LMNtalの最短経路問題のエンコードは過去に複数の方法[15]が提案されているが, そ

の中で膜を使用しないエンコード方法¹と新たにハイパーリンクを使用したエンコード方 法に関して本節では述べる.

5.1.1 膜を使用しない最短経路問題のエンコード

膜を使用しない方法で最短経路問題をエンコードしたLMNtalプログラム例を図5.2に 示す. このプログラムは図5.1に示した重み付き無向グラフにおいて,ノードaを基準とす る単一始点最短経路問題をエンコードしたプログラムである. このプログラムは2つの主 要なアトム(e, cost)と１本のルールから成り立つ.

アトムeは3引数のアトムであり,エンコードされるグラフのエッジの情報を所持する. 第一引数にはエッジの始点の情報を持ったunary型のアトム,第二引数にはエッジの終点 の情報を持ったunary型のアトム,第三引数にはそのエッジの重みを表す1以上の整数ア トムにそれぞれ接続されている. アトムe単体では1つの有向重み付きエッジを意味する が, 第一引数と第二引数が入れ替わり, 第三引数が等しいアトムeが存在する場合は無向

1 http://www.ueda.info.waseda.ac.jp/lmntal/demo/shortestpathAll2all.lmn

1 3

2

1 3

d c

b a

図5.1 扱う重み付き無向グラフ

cost(a,a,0), cost(a,b,100), cost(a,c,100), cost(a,d,100), e(a,b,2), e(a,c,1), e(c,b,3), e(b,d,1), e(c,d,3),

e(b,a,2), e(c,a,1), e(b,c,3), e(d,b,1), e(d,c,3).

cost($s0,$p,$w1), e($p0,$t0,$w0), cost($s,$t,$w2)

:-$s0==$s, $p0==$p, $t0==$t, $w=$w0+$w1, $w<$w2 | cost($s0,$p,$w1), e($p0,$t0,$w0), cost($s,$t,$w).

図5.2 LMNtalで記述した最短経路問題

エッジを表現することができる. アトムeの具体的なグラフを図5.3に示す.

アトムcost もアトムeと同様な構造をしており,  第一引数のノードから第二引数の ノードまでにかかるコストを第三引数で表している. 第三引数の初期値として, 第一引数 と第二引数が同じノード名の場合には0,異なる場合は100を接続する. (100はマジック ナンバーであり,意味としては∞^{として使用している}. LMNtalでは∞^{を意味するアトム} は表現できない)最終的にプログラムが停止した時, アトムcostの第三引数に所持してい る値が最小のコストとなる. アトムcostの具体的なグラフを図5.4に示す.

e

a b 1

図5.3 アトムeの例

cost

a a 0

図5.4 アトムcostの例

LMNtalにおける最短経路問題はアトム costで所持している第三引数の値をルールに

よって更新していくことで実行が進む. ルールが適用される条件を図5.5に示す. この部分

LMNtalグラフは図5.6のグラフを意味している. 図中のw1 はノードs, p間の道のコスト である. このルールは現在のコスト値wよりも w1+w2 のコスト値の方が小さい場合,w がノードs, t間の最小コストではないと分かるため, 新たにw₁+w₂ をコスト値として更

新する. LMNtalによる最短経路問題のエンコードの特徴として,一本の簡潔なルールで最

短経路問題を解くことができる点が挙げられる.

cost

s p w₁

cost

s t w

e

p t w₂

図5.5 ルールの適用条件

s

t

w w

p

w

図5.6 図5.5を意味するグラフ構造

このエンコード方法の短所として,パターンマッチの回数が必要以上に多くなることが 挙げれる. 現状のエンコードは 1回のパターンマッチにおいて,アトムeを含む部分グラ フを１つ,アトムcostを含む部分グラフを2つ抽出している. このとき,リンク先の情報の 比較によって適用できるかどうかをチェックするため,アトムe,アトムcostそれぞれ存在 する個数を|e|,|c|^とすると, 1回のルール適用あたり最悪O(|e| ∗ |c|²)の計算量が生じる.

5.1.2 HyperLMNtal を使用した最短経路問題のエンコード

現状の最短経路問題のエンコード方法の問題点を解決するために,新たにHyperLMNtal を使用したエンコード方法を行った. HyperLMNtalで記述した最短経路問題を図5.7に示 す. 図5.2の記述方法と異なる点として,同じノードを指すリンク先をハイパーリンクに よってまとめていることにある. ハイパーリンクで同じノードのリンクをまとめることで, ハイパーリンクを使用した最適化探索を適用することができ,探索すべきアトムの量を減 らすことが可能となった. つまり,図5.2では連結していなかった3つの部分グラフ構造を ハイパーリンクによって接続することで,すべてのノードをリンクとハイパーリンクでた どれるようになった.

HyperLMNtalでエンコードした際にルール適用する部分グラフを図5.8に示す. 図5.5

の条件が3つの連結グラフから成り立つのに対し,図5.8の条件が1つの連結グラフから 成り立っていることが分かる. LMNtalでモデルを記述する際に,ルール左辺に存在する連 結グラフの数を最小限にすることがパターンマッチング処理の削減につながる.

init.

init:-cost(!A,!A,0), cost(!A,!B,100), cost(!A,!C,100), cost(!A,!D,100), e(!A,!B,2), e(!A,!C,1), e(!C,!B,3), e(!B,!D,1), e(!C,!D,3),

e(!B,!A,2), e(!C,!A,1), e(!B,!A,3), e(!D,!B,1), e(!D,!C,3).

cost(!S,!P,$c1), e(!P,!T,$c0), cost(!S,!T,$c2)

:-$c=$c0+$c1, $c<$c2 |

cost(!S,!P,$c1), e(!P,!T,$c0), cost(!S,!T,$c).

図5.7 HyperLMNtalで記述した最短経路問題

cost w₁

cost w

e

w₂

!T

!P

!S

図5.8 HyperLMNtalでエンコードした際のルールの適用条件