How to implement Greedy Search algorithm

Question

I have a project that is given on my Artificial Intelligence course. I need to implement Greedy Search algorithm for my program. Description of my project is: Two text files called “tree.txt” and “heuristic.txt” are given. “tree.txt” will define the search tree where each line will contain a parent-child relation and a path cost between them. Each data will be seperated with a space.

e.g.

A B 5

A C 3

B D 6

The first character in the first line will be the Start node (A in here) and the goal node will be “G”.

“heuristic.txt” will define the heuristic, h(n), values. Each line will contain the heuristic value of each node. Each data will be seperated with a space.

e.g.

A 20

B 15

C 18

Output: The program should give the solution path and the path cost from start node to goal.

Now my problem is that i am familiar with Greedy Search theoretically, but never implemented it practically in coding. I really dont know from where to start. We are free to develop our program in any language. Mostly, i have skills in Java and C#. If anybody can give me some ideas, or help me with any similar examples or tutorials. Any kind of help will be greatly appreciated. Sorry for so much writing. Thank you in advance:)))

Answer 1

I suggest this solution using python. To implement the graph in your program use a simple python dictionary. Here's the code:

class Tree:

     def _init_(self,dict,heuristic):
     self.tree=tree
     self.heuristic=heuristic



     def getHeuristicValue(self,state)
     value=self.heuristic.get(state)
     return value

The constructor call is something like:

g = Graph({'A':{'B':5,'C':3},'B':{'D':6}},{'A':20,'B':15,'C':18})

The getHeuristic python function pass accepts a state as an argument and returns the value of the heuristic of this state.

To learn about python's dictionary class I suggest you read the tutorial

To implement the search algorithm with python you should implement this simple pseudocode:

function Tree-Search(initialNode,goalNode) returns a solution,or failure
frontier.push(initialNode) with the value of the function heuristic(initialNode.state)+the path cost to reaxh this node
while(frontier)
  node<-frontier.pop()
  if node.state==GoalNode.state
    return node
  expand node, adding the resulting nodes to the frontier
return None

For the frontier you must use a priority queue because you must pop the node with the lower value of g(n)+h(n) (where g(n) is the path cost to reach this node and h(n) is the value of the heuristic function).

To implement priority queue you should use a heap of the standard library heapq

The node is a data structure that must contain four components:

node.state:the state in the state space to which the node corresponds.

node.parent:the node in the search tree that generated this node.

node.action: the action that was applied to the parent to generated the node.

node.pathCost: is g(n),the cost of the path from the initial state to the node.

Lastly, for expanding the node, you can use this python function:

def actions(self,state):
    '''return a tuple that contain the state child of state '''
    return tuple(self.tree.get(state))

I suggest you to look this for your problem.

You can get the solution simply go back from the node.state that returns from the output of the algorithm while node.parent is not null that is your solution.

I hope this is useful for your project.