Search code examples
prologgraph-algorithmdepth-first-searchshortest-path

Greedy search in prolog using heuristic value

I have a graph and a heuristic table, with a list connections and node values and also the cost (heuristic table).

Graph: Graphical representation

Heuristic table: The cost of visiting node

They're represented in prolog as follows.

s(a,b,2).
s(a,c,1).
s(b,e,4).
s(b,g,2).
s(c,d,1).
s(c,x,3).
s(x,g,1).

h(a,9)
h(b,3)
h(c,2)
h(d,8)
h(e,4)
h(g,0)
h(x,2)

My query, how do I perform a greedy search using the heuristic values h(a,9) to find the next node at each iteration.

I know how to use DFS to get shortest possible path and store that path using a list. I don't know how to take the heuristic values at each node into account to account for this in a greedy search - I do know that it expands the lowest h value node, to find it's next neighbor.

DFS:

depthfirstsearch(GoalN,Path,[GoalN|Path]) :- goal(GoalN).

depthfirstsearch(Node,Path,Solution) :- s(Node,NextNode,_), \+member(NextNode,Path), 
depthfirstsearch(NextNode,[Node|Path],Solution)

As I've search SO and the web (finding notes on how greedy search works) but nothing that explains how it actually works using prolog code. It explains how to do this in java, C++, etc. but I'm not using those languages.

Can anyone put me in the right direction? I read somewhere that findall could be used? But how do I combine the heuristic value to the node, for example Node "B" with a cost of 2, from A to B. Do I substitute the cost of 2, with the heuristic value/cost of 3. Please explain in more detail or direct me to another resource that would be beneficial right now?

I could maybe create a predicate to help find the next node at each iteration (using the heuristic value of course)?

Bear in mind I'm a beginner at prolog and trying out ways but struggling to piece it all together.

Update: This link is where I find out most of the info on searches

Solution

  • I think you need to know what is a heuristic value and how it can be used in your searching algorithm.

    In my answer:

    • n is the node we want to reach

    • s is the source node

    • h() is the heuristic function. h(n) is an admissible (?) value, I prefer to think of it an estimated cost to reach n from source s. We call a heuristic good only if it does not safely over-estimate the cost.

    • w(a,b) is the actual cost to go from a to b

    • g() is a function giving actual cost to reach node n from s by summing up w(a,b) where both a and b are nodes in path from n to s.

    Now to answer your question, AFAIK you can use this heuristic in 2 ways:

    • As you have said, you can lazily ignore w(a,b) values and use h(b) values to sort the successor nodes (where b is any successor node) -- This is called best first search algorithm

    • Another way would be to sort successor nodes based on value h(b) + g(b) (where b is any successor node) -- This is called A* search algorithm.

    Recommended Reading:

    • Stuart J Russell and Peter Norvig, ―Artificial Intelligence - A Modern Approach, Third Edition

    • Ivan Brakto, ―Prolog Programming for Artificial Intelligence, Pearson Education, August 2011.

    P.S. findall is the right thing to use in prolog to implement these 2 searches.