Heuristic algorithms in prolog

Question

i'm not very experienced on Prolog and i'm trying to solve an exercise that's about using a heuristic algorithm(f.e. A* or BFS or Hill-Climbing) to find a solution to a given problem.

Since i'm not familiar with this kind of programming and a search in google didn't really help me,i was wondering if anyone could give me a link to a similar already solven example to see how this is done.
I'm not trying to copy anything,it's just that I did study a lot about prolog commants etc. and i do know how these algorithms work in theory and how they solve the problem(f.e. in my exercise i think BFS or A* would be good choise) but i don't understand how i am supposed to compose a program in prolog that actually uses an algorithm and gives a solution.

Just a clarification,i really believe that real prolog-code examples would be very useful and not theoritical explanation of how an algorithm works.I do kwon how the problem is supposed to be solved,making it happen and particularly in prolog is what i fail to understand..

Thnx in advance..

Kyle Dewey Kyle Dewey · Accepted Answer · 2011-01-05T06:02:25

Oddly enough I recently implemented a BFS in Prolog. I haven't posted the code anywhere and I'm hesitant to do so, because it's a reimplementation of an assignment that will likely be reused.

I can give you the actual BFS definition:

% performs a BFS, with the given goal and queue
bfs( Goal, [[Goal|[Path]]|_], Path ).
bfs( Goal, [State|Rest], Result ) :-
    successors_list( State, Successors ),
    remove_seen( Successors, NewStates ),
    add_to_seen( NewStates ),
    append( Rest, NewStates, Queue ),
    bfs( Goal, Queue, Result ).

For this problem, "Goal" was a particular number, and "Path" was the sequence of actions needed to get to that goal. The second parameter is the queue, where each state is represented as a list of two elements (the first is the current number, and the second was the path needed to generate that number). It returns the path needed to get the given number in "Path". The set of seen states were recorded in the database itself, using asserts.

Outside of this definition everything is problem specific.

EDIT: I should have said most everything is problem specific. I revisited my code, made a few minor edits, and changed the problem it solves. It's significantly different enough from the assignment that I feel comfortable posting it, so here it is: BFS in Prolog(AI)

Heuristic algorithms in prolog

1 Answers