12.6. Informed search

Solution 6.1 

Suppose the call children(Current,Children) results in an ordered list of children. Write a predicate merge/3 which directly merges this list with the current agenda.

This predicate is a little bit special because it requires two recursion arguments. Therefore, there are two recursive clauses and two base cases. Note that in the second clause the first argument is required to be a non-empty list. This is done to prevent the query ?-merge([],[],L) from succeeding twice.

merge([],Agenda,Agenda).
merge([Child|Children],[],[Child|Children]).  % empty agenda
merge([Child|Children],[Node|Agenda],[Child|NewAgenda]):-
    eval(Child,ChildValue),
    eval(Node,NodeValue),
    ChildValue < NodeValue,                   % Child is better than Node
    merge(Children,[Node|Agenda],NewAgenda).
merge([Child|Children],[Node|Agenda],[Node|NewAgenda]):-
    eval(Child,ChildValue),
    eval(Node,NodeValue),
    ChildValue >= NodeValue,                  % Child not better than Node
    merge([Child|Children],Agenda,NewAgenda).

Solution 6.4 

Find a position for which the third heuristic is too pessimistic.

It is too pessimistic for the starting position (minimal cost 15, estimate 18).