<div class="notebook"> <div class="nb-cell markdown" name="md1"> # Non-termination of SLD resolution At the bottom there is predicate that models a small part of the London Underground connections. We will search this network for a connection. First, let us display the map: </div> <div class="nb-cell query" name="q1"> findall(_A-_B, connected(_A,_B), _Pairs), Map = digraph(_Pairs). </div> <div class="nb-cell markdown" name="md2"> Now we are a logician and define the transitive closure over this relation </div> <div class="nb-cell program" name="p2"> % connections go both ways connected(A, B) :- connected(B, A). % and connections are transitive connected(Start, End) :- connected(Start, Somewhere), connected(Somewhere, End). </div> <div class="nb-cell query" data-tabled="true" name="q2"> connected(oxford_circus, green_park). </div> <div class="nb-cell markdown" name="md3"> Hmmm. That doesn't work because SLD resolution doesn't take into account what it is already trying to solve and thus connected(S1,S2) uses the first rule, turning connected(S2,S1) into its current goal that matches the first rule, ... How can we fix this? - Stratification - Keep track of where you have been </div> <div class="nb-cell program" name="p3"> adjacent(S1, S2) :- connected(S1, S2). adjacent(S1, S2) :- connected(S2, S1). travel(S1, S2, Route) :- travel(S1, S2, [S1], Route). travel(S, S, Route, Route). travel(S1, S2, Route0, Route) :- adjacent(S1, Sx), \+ member(Sx, Route0), travel(Sx, S2, [Sx|Route0], Route). </div> <div class="nb-cell query" data-tabled="true" name="q3"> travel(oxford_circus, green_park,Route). </div> <div class="nb-cell markdown" name="md4"> *|Better!|* It now terminates and tells us how to travel. But, if we apply this to the railways and make it plan from Amsterdam to Poznań we might explore all tracks on the Eurasian continent. Breath-first search would be better. Can we do that? Of course, as Prolog performs simple SLD resolution we can _implement any algorithm_ in it. We follow a common pattern using a list as an _agenda_, each node of which is a pair `Station-Route`. If we are not at the target we expand the first node of the agenda and append this expansion to the end of the agenda: </div> <div class="nb-cell program" name="p4"> travel(S1, S2, Route) :- travel_bf(S2, [S1-[S1]], Route). travel_bf(To, [To-Route|_], Route). travel_bf(To, [S-Route0|T], Route) :- findall(S1-[S1|Route0], (adjacent(S,S1),\+member(S1,T)), New), append(T, New, Agenda), travel_bf(To, Agenda, Route). adjacent(S1, S2) :- connected(S1, S2). adjacent(S1, S2) :- connected(S2, S1). </div> <div class="nb-cell query" data-tabled="true" name="q4"> travel(oxford_circus, green_park, Route). </div> <div class="nb-cell markdown" name="md5"> Now we nicely get routes, first trying in the neighbourhood. Traveling from Amsterdam to Poznań will still be a problem as also the breath-first search already covers quite some railway stations before we find Poznań. That is a mere matter of reordering the agenda smartly instead of appending our new stations. That way we can easily implement e.g., [A*](https://en.wikipedia.org/wiki/A*_search_algorithm) </div> <div class="nb-cell program" data-background="true" name="p1"> % Abstract a little. connected(S1, S2) :- connected(S1, S2, _Line). connected(bond_street,oxford_circus,central). connected(oxford_circus,tottenham_court_road,central). connected(bond_street,green_park,jubilee). connected(green_park,charing_cross,jubilee). connected(green_park,piccadilly_circus,piccadilly). connected(piccadilly_circus,leicester_square,piccadilly). connected(green_park,oxford_circus,victoria). connected(oxford_circus,piccadilly_circus,bakerloo). connected(piccadilly_circus,charing_cross,bakerloo). connected(tottenham_court_road,leicester_square,northern). connected(leicester_square,charing_cross,northern). </div> <div class="nb-cell program" data-background="true" name="p5"> :- use_rendering(graphviz). </div> </div>