最短経路問題

次に，最短経路問題においてのヒューリスティック関数とコスト関数の記述方法を説明 する．以下に最短経路問題のLMNtalプログラムとヒューリスティック関数の例を示す．

最短経路問題の例としてルーマニアの都市の例について考える．目的地はBucharestであ り，ヒューリスティック関数としてBucharestまでの直線距離を用いる．Bucharestまで の直線距離を表6.1に示す．LMNtalプログラムでは，ヒューリスティック関数を計算す るためにsldというアトムを用いて目的地までの直線距離を表している．グラフのエッ ジをeというアトムで表し，e の第一引数はエッジの始点を，第二引数はエッジの終点 を，第三引数はエッジの重みが表している．stateアトムを用いて，現在の状態を表して いて，第一引数が現在いる都市，第二引数がその一つ前の都市となっている．最後に移動 のルールがあり，このルールは現在いる都市を始点とするエッジを探し，位置を更新する ようなルールとなっている．

表6.1 各都市とBucharestまでの直線距離

都市名 距離(km) 都市名 距離(km)

A - Arad 366 M - Mehadia 241

B - Bucharest 0 N - Neamt 234

C - Craiova 160 O - Oradea 380

D - Dobreta 242 P - Pitesti 100

E - Eforie 161 R - Rimnicu Vilcea 193

F - Fagaras 176 S - Sibiu 253

G - Giurgiu 77 T - Timisoara 329

H - Hirsova 151 U - Urziceni 80

I - Iasi 226 V - Vaslui 199

L - Lugoj 244 Z - Zerind 374

LMNtalプログラム

// Bucharestまでの直線距離(straight line distance) sld(arad, 366),

sld(bucharest, 0), ...

sld(zerind, 374).

// _エッジ

e(oradea, zerind, 71), e(zerind, oradea, 71), e(zerind, arad, 75), e(arad, zerind, 75), ...

e(iasi, neamt, 87), e(neamt, iasi, 87).

// _状態

state(arad, nothing).

//_{移動ルール}

e(S, D, C) \ state(A, B) :- A==S, unary(B), unary(D) | state(D, S).

コスト関数・ヒューリスティック関数

// cost function

c = e[_.1 == state.2 & _.2 == state.1].3

// heuristic function h = sld[_.1 == state.1].2

次に最短経路問題におけるDSLを用いたコスト関数とヒューリスティック関数がどの ように計算されるかを説明する．まず，状態遷移時のコストであるコスト関数としては エッジの重みが対応していて，c = e[ .1 == state.2 & .2 == state.1].3と記述 できる．これは e というアトム名のアトム集合の内，論理式[ .1 == state.2 & .2

== state.1]を満たすような eを取得して，その第三引数のエッジの重みを結果として cとするようにしている．論理式の意味としては，stateアトムの第二引数である一つ前 の都市を第一引数に，stateアトムの第一引数である現在の都市を第二引数とするという

条件を表している．従って，e[ .1 == state.2 & .2 == state.1]は一つ前の都市を エッジの始点に，現在の都市をエッジの終点とするようなeというアトムにマッチする．

同様に，h = sld[ .1 == state.1].2は現在の都市を第一引数に持つようなsld とい うアトムを取得して，その第二引数の直線距離をヒューリスティック関数hとしている．

第 7 _章

評価実験

本章では，実行時処理系 SLIMにおいて導入したA*探索について，8パズルの問題ま たはその同種の問題についてさまざまな初期状態について評価実験を行う．ヒューリス ティック関数はマンハッタン距離を利用している．表7.1に実験環境を示す．

表7.1 実験環境

OS CentOS 5.10

CPU AMD Opteron(tm) Processor 6176 SE (48CPUs)

Cache Size 512KB

Cache Alignment 64B

Memory 256Gbyte

7.1 逐次実行

本節では，新規機能であるA*探索の実行結果の例を示し，また，逐次実行における測 定結果とその考察を示す．