續草稿: Dijkstra’s Algorithm in Prolog

本文續前文為 https://yauhsien.wordpress.com/2011/01/25/%E8%8D%89%E7%A8%BF%EF%BC%9A-dijkstras-algorithm-in-prolog/ (草稿: Dijkstra’s Algorithm in Prolog)

在前文中,我用鄰接法 (adjacent form) 表達一張無向圖,是很常用的方法。 link/3 表達哪個點與哪個點連接,並且權重多少。但我很快就注意到這樣的表達還不夠,我還需要一個結構用來紀錄任何二個點之間的距離,在 Dijkstra’s algorithm 是稱為 tentative distance ,簡單說,就是在求解過程中暫時知道的二點之間的最短距離。

有三個 predicates 用來搭配處理這種任意二點距離。首先有 default_distances/3 取一開始從指定開始點到達多個目的點的最短距離。

default_distances(From, Targets, Distances) :-
bagof([[B, From], W], (member(B, Targets), weight(From B, W)), Distances).

用法為:

?- default_distances(‘1’, [‘2′,’3′,’4′,’5′,’6’], Ds).

Ds = [[[‘2’, ‘1’], 7], [[‘3’, ‘1’], 9], [[‘4’, ‘1’], infinite], [[‘5’, ‘1’], infinite], [[‘6’, ‘1’], 14]].

每一個項目包含一段路徑及其暫時的最短距離。順道提到,在前文所寫的 weight/3 改寫成以下樣式:

weight(A, B, 0) :- A == B, !.
weight(A, B, W) :- link(A, B, W), !.
weight(A, B, W) :- link(B, A, W), !.
weight(_, _, infinite).

第二個有關 tentative distances 的 predicate 是 tentative_distance/4 ,只要知道一個 Ds 資料庫,並且知道要問從哪個開始點到哪個目的點的暫時最短距離,就會求解。等於是做資料庫查詢。

tentative_distance([], _, _, []).
tentative_distance([[Path, D]|_], From, Target, [Path, D]) :-
[Target|_] = Path
, !
, last(Path, From).
tentative_distance([_|Ds], From, Target, D) :-
tentative_distance(Ds, From, Target, D).

last/2 的定義是求列表的最後一項:

last([X], X).
last([_|Xs], X) :- last(Xs, X).

第三個 tentative distances 相關 predicate 是把新的暫時最短路徑更新到資料庫。 update_distances_/3 定義如下:

update_distances_([], _, []).
update_distances_([[Path, D]|Ds], [Path1, D1], [[Path1, D1]|Ds]) :-
[Target|_] = Path
, [Target|_] = Path1
, shorter(D, D1, D1)
, !.
update_distances_([[Path, D]|Ds], [Path1, _], [[Path, D]|Ds]) :-
[Target|_] = Path
, [Target|_] = Path1
, !.
update_distances_([D|Ds], PInfo, [D|Ds1]) :-
update_distances_(Ds, PInfo, Ds1).

我想完整的 path info 劃分為 path 與 tentative distance 二部份,個別為以上 PInfo 、 Path 及 D 變數所代表。 shorter/3 用來判斷距離的大小,因為距離可能是數字或 infinite 。

shorter(D, infinite, D) :- D \== infinite, !.
shorter(infinite, D, D) :- D \== infinite, !.
shorter(D, D1, D) :- D \== infinite, D =< D1, !.
shorter(D, D1, D1) :- D1 \== infinite, D > D1, !.

有了以上三個 default_distances/3 、 tentative_distance/4 、 update_distances_/3 ,主程式大概會是:

solusion(From, Target, [Distance, Path]) :-
Vs = [‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’]
, without(Vs, [From], Targets)
, default_distances(From, Targets, Ds)
, shortest_path([From], Target, Ds, [Path, Distances]).

shortest_path(Path, G, Ds, PInfo) :-
next_paths(Path, Pss)
, update_distances(Ds, Pss, Ds1)
, shorter_path(Ds1, Pss, [Path1, D])
, (member(G, Path1) -> PInfo = [Path1, D]
;    not(member(G, Path1)) -> shortest_path(Path1, G, Ds1, PInfo)
).

update_distances/3 與前述的 update_distances_/3 不同,前者是指將每個可能的路線的潛在的最短距離都更新到 Ds 資料庫,會使用到後者並且加上一些檢查判斷是原有在 Ds 資料庫的最短距離比較短、或者是新加入的路線造成的最短距離比較短。

目前程式還沒完成。最後發現我忘了定義一個點 P 到 P 自己的 tentative distance 為 0 的情況。不過這幾天看著 Dijkstra’s algorithm 的 Wikipedia 條目琢磨了不少時間,程式改寫了三次,對 tentative distance 的心得很夠了。

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Prolog, Strip。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s