# Python Learning Week 7 (Solution)

Implement Greedy Best First Search Algorithm for the given example, if starting node is Arad and goal node is Bucharest.

CODE:

‘Fagaras’:[[‘Sibiu’,253],[‘Bucharest’,0]],

‘Rimniciu Vilcea’:[[‘Pitesti’,98],[‘Craiova’,160],[‘Sibiu’,253]],

‘Pitesti’:[[‘Craiova’,160],[‘Bucharest’,0]],

‘Craiova’:[[‘Pitesti’,98],[‘Dobreta’,242],[‘Rimniciu Vilcea’,193]],

‘Bucharest’:[[‘Giurgiu’,77],[‘Urziceni’,80],[‘Fagaras’,178],[‘Pitesti’,98]],

‘Giurgiu’[[‘Bucharest’,0]],

‘Urziceni’:[[‘Vaslui’,199],[‘Hirsova’,151],[‘Bucharest’,0]],

‘Vaslui’:[[‘Lasi’,226],[‘Urziceni’,80]],

‘Lasi’:[[‘Neamt’,234],[‘Vaslui’,199]],

‘Neamt’:[[‘Lasi’,226]],

‘Hirsova’:[[‘Eforie’,161],[‘Urziceni’,80]],

‘Eforie’:[[‘Hirsova’,151]]
}

def gbfs(GRAPHstartend):

explored []

queue [start]

while queue:

print (queue)

node queue.pop(0)

if node not in explored:

explored.append(node)

if node == end:
break

neighbors GRAPH[node]

neighbors.sort(key=lambda aa[1])

print (neighbors)

queue=neighbors.pop(0)

print(explored)

Start input(“Enter Starting node “)
End input(“Enter Ending node “)
print()
print(“GBFS from staring node to goal node”)
gbfs(GRAPHStartEnd)

OUTPUT:

Implement A* Algorithm for the graph given in Task1, if starting node is Arad and goal node is Bucharest.

CODE:

from
queue import PriorityQueue
GRAPH

‘Fagaras’:{‘Sibiu’:99,‘Bucharest’:211},

‘Rimniciu Vilcea’:{‘Pitesti’:97,‘Craiova’:146,‘Sibiu’:80},

‘Pitesti’:{‘Craiova’:138,‘Bucharest’:101},

‘Craiova’:{‘Pitesti’:138,‘Dobreta’:120,‘Rimniciu Vilcea’:146},

‘Bucharest’:{‘Giurgiu’:90,‘Urziceni’:85,‘Fagaras’:211,‘Pitesti’:101},

‘Giurgiu’{‘Bucharest’:90},

‘Urziceni’:{‘Vaslui’:142,‘Hirsova’:98,‘Bucharest’:85},

‘Vaslui’:{‘Lasi’:92,‘Urziceni’:142},

‘Lasi’:{‘Neamt’:87,‘Vaslui’:92},

‘Neamt’:{‘Lasi’:87},

‘Hirsova’:{‘Eforie’:86,‘Urziceni’:98},

‘Eforie’:{‘Hirsova’:86}
}

def a_star(sourcedestination):

straight_line ={

‘Zerind’374,

‘Sibiu’:  253,

‘Fagaras’:176,

‘Rimniciu Vilcea’193,

‘Timisoara’329,

‘Lugoj’244,

‘Dobreta’242,

‘Pitesti’:100,

‘Craiova’:160,

‘Bucharest’:0,

‘Giurgiu’:77,

‘Urziceni’80,

‘Vaslui’:199,

‘Lasi’:226,

‘Neamt’:234,

‘Hirsova’:151,

‘Eforie’:161

}

p_qvisited PriorityQueue(), {}

p_q.put((straight_line[source], 0source, [source]))

visited[sourcestraight_line[source]

while not p_q.empty():

(heuristiccostvertexpathp_q.get()

print(“Queue Status:
,
heuristiccostvertexpath)

if vertex == destination:
return
heuristiccostpath

for next_node in GRAPH[vertex].keys():

current_cost cost GRAPH[vertex][next_node]

heuristic current_cost straight_line[next_node]

if not next_node in visited or visited[

next_node>= heuristic:

visited[next_nodeheuristic
p_q
.put((heuristiccurrent_costnext_nodepath [next_node]))

def main():

print(‘Source :’end=‘ ‘)

source input().strip()

print(‘Destination :’end=‘ ‘)

goal input().strip()

if source not in GRAPH or goal not in GRAPH:

print(‘ CITY DOES NOT EXIST.’)

else:

heuristiccostoptimal_path a_star(sourcegoal)

print(‘min of total heuristic_value =’heuristic)

print(‘total min cost =’cost)

print(\nRoute:’)

print(‘ -> ‘.join(city for city in optimal_path))

main()

OUTPUT:

What we studied in week 7:

In this we studied Greedy breadth first search and A* search. In greedy breadth first search use heuristic as an evaluation path from any node n to goal node and find the path f(n)=h(n). This technique used to find good solution quickly although not only optimal ones. In this use straight line distance expand the node that appears to be closest to the goal. A* search find the shortest path  through a search space to goal state using heuristic function f(n)=g(n)+h(n). In this technique find minimal cost solution and is directed to a goal state. A* is complete and optimal best one from other technique. Also we Implemented both techniques in python. This is all we have studied in this week.