Branch and Bound Shortest Path in Prolog
Branch and bound shortest path algorithm can be implemented with restart. The algorithm doesn't use any dynamic database only backtracking and recursion. Lets say we have this graph:
Which we can represent in Prolog as these facts:
% edge(-Vertex, -Vertex)
edge(a, b). edge(a, c).
edge(a, d). edge(b, c).
edge(c, d). edge(c, e).
edge(d, e).
We first need a bounded path finder. This can be realized as a predicate that takes an upper bound, and then returns the number of hops subtracted from the upper bound, with the guarantee that the result is never below zero:
% path(+Vertex, +Vertex, +Integer, -Integer)
path(X, X, N, N).
path(X, Y, N, M) :- N > 0,
H is N-1,
edge(X, Z),
path(Z, Y, H, M).
The bounded path finder is non-deterministic and uses backtracking for its search. We now add a further predicate that restarts the path finder by recursively using a smaller upper bound, whenever a path was found. This way the smallest length is found:
% bb_path(+Vertex, +Vertex, +Integer, -Integer)
bb_path(X, Y, N, M) :- N > 0,
H is N-1,
path(X, Y, H, K), !,
L is H-K,
bb_path(X, Y, L, M).
bb_path(_, _, N, N).
Note the use of a cut in the predicate branch and bound predicate. Here is an example run. We start with an upper bound which is the number of edges plus one. We can first manually call path/4 multiple times and simulate the search:
?- path(a, e, 7, K), L is 7-K.
K = 3,
L = 4
?- path(a, e, 3, K), L is 3-K.
K = 0,
L = 3
?- path(a, e, 2, K), L is 2-K.
K = 0,
L = 2
?- path(a, e, 1, K), L is 1-K.
No
So starting with an upper bound 8, we gradually get better upper bounds 4, 3 and 2, until no more improvements are possible. The predicate bb_path/4 does this search for us:
?- bb_path(a, e, 8, X).
X = 2
Author And Source
この問題について(Branch and Bound Shortest Path in Prolog), 我々は、より多くの情報をここで見つけました https://qiita.com/j4n_bur53/items/e92ebc36498df733abb2著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .