This assignment asks you to apply the A search algorithm to graphs over the set of nodes f1; 2; 3; : : :g, with arcs N,M and costs Cost induced by a positive integer Seed as follows
arc(N,M,Seed,Cost) :- M is N*Seed, Cost=1.
arc(N,M,Seed,Cost) :- M is N*Seed + 1, Cost=2.
(E.g. Seed = 3 yields arc 1,3 with cost 1 and 1,4 with cost 2.) Let us agree also that the goal nodes are given by a positive integer Target as those nodes divisible by Target | i.e. Target, 2*Target, 3*Target, : : :
goal(N,Target) :- 0 is N mod Target.
Given Target, let us set the heuristic function to 0 on goal nodes, and to the reciprocal elsewhere.
h(N,Hvalue,Target) :- goal(N,Target), !, Hvalue is 0
;
Hvalue is 1/N.
Your task is to de ne a predicate
a-star(+Start,+Seed,+Target,?Found)
that given positive integers Start, Seed and Target returns the lowest cost goal node Found calculated by A .
The idea is to modify the skeletal search algorithm
search([Node|FRest]) :- goal(Node).
search([Node|FRest]) :- setof(X,arc(Node,X), FNode), add-to-frontier(FNode,FRest,FNew), search(FNew).
so that the list FNew obtained in add-to-frontier is (as prescribed by A ) sorted in order of increasing f-values, where f(node) = cost(node) + h(node).
Hint. Let the frontier be a list of node-cost pairs (instead of just nodes), being careful to add the cost of the parent to its children, and to bring in the heuristic function in ordering the frontier FNew.
less-than([Node1,Cost1],[Node2,Cost2],Target) :-h(Node1,Hvalue1,Target), h(Node2,Hvalue2,Target), F1 is Cost1+Hvalue1, F2 is Cost2+Hvalue2,
F1 =< F2.
Test your de nitions with queries such as
?- a-star(1,3,6,F).
For any extensions beyond that date, email your demonstrator/marker, David Woods (dwoods@tcd.ie).
