Turn Depth First Search into a Best-First (greedy) Search in prolog

Question

I am wanting to modify my depth first search to a best-first search.

My depth first search is as follows

goal(fivet).

move(onea,twoa).
move(onea,twob).
move(onea,twoc).
move(onea,twod).
move(twoa,threea).
move(twoa,threeb).
move(twoa,threec).
move(threea,foura).
move(threea,fourb).
move(foura,fivea).
move(fourb,fiveb).
move(threeb,fourc).
move(threeb,fourd).
move(fourc,fivec).
move(fourd,fived).
move(threec,foure).
move(threec,fourf).
move(foure,fivee).
move(fourf,fivef).
move(twob,threed).
move(twob,threee).
move(twob,threef).
move(threed,fourg).
move(threed,fourh).
move(fourg,fiveg).
move(fourh,fiveg).
move(threee,fouri).
move(threee,fourj).
move(fouri,fivei).
move(fourj,fivej).
move(threef,fourk).
move(threef,fourl).
move(fourk,fivek).
move(fourl,fivel).
move(twoc,threeg).
move(twoc,threeh).
move(twoc,threei).
move(threeg,fourm).
move(threeg,fourn).
move(fourm,fivem).
move(fourn,fiven).
move(threeh,fouro).
move(threeh,fourp).
move(fouro,fiveo).
move(fourp,fivep).
move(threei,fourq).
move(threei,fourr).
move(fourq,fiveq).
move(fourr,fiver).
move(twod,threej).
move(twod,threek).
move(twod,threel).
move(threej,fours).
move(threej,fourt).
move(fours,fives).
move(fourt,fivet).
move(threek,fouru).
move(threek,fourv).
move(fouru,fiveu).
move(fourv,fivev).
move(threel,fourw).
move(threel,fourx).
move(fourw,fivew).
move(fourx,fivex).


dfs(A, Path, Path) :- goal(A).

dfs(A, Checked, Path) :-
    % try a move
    move(A, A2),
    % ensure the resulting state is new
    \+member(A2, Checked),
    % and that this state leads to the goal
    dfs(A2, [A2|Checked], Path).

% query = dfs(onea, [], Path).

please excuse the long winded program, its a rather large search tree.

I have given all the nodes a metric X.

is it a simple process to change the above program from depth first to best-first?

any help would be much appreciated.

thank you

Answer 1

The trick is to not allow prolog to choose the next move for you, but rather gather all of the possible moves so you can use your criteria to select the best one.

Look into the find_all predicate.

Answer 2

using a fake metric (see isub) and goal

goal(fivex).

dfs(A, Path, Path) :- goal(A).
dfs(A, Checked, Path) :-
    % get all possible moves, ordered
    setof(W-A2, (
      move(A, A2),
      % avoid looping - but in displayed graph there should not be
      \+memberchk(A2, Checked),
      % fake metrics value, maybe should be reversed
      isub(A, A2, true, W)
    ), L),
    % peek next step in increasing metric
    member(_-A2, L), % 
    % leads to the goal
    dfs(A2, [A2|Checked], Path).

if you know there are no loops, you can simplify in this way, getting the path ordered from start to goal

dfs(A, [A]) :- goal(A).
dfs(A, [A|Path]) :-
    % try a move
    setof(W-A2, (
        move(A, A2),
        isub(A, A2, true, W) % fake metrics, maybe reverse
    ), L),
    % peek next step in increasing metric
    member(_-A2, L), % 
    % and that this state leads to the goal
    dfs(A2, Path).