# Python Learning Week 6 (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(GRAPH, start, end):

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 a: a[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(GRAPH, Start, End)

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(source, destination):

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_q, visited = PriorityQueue(), {}

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

visited[source] = straight_line[source]

while not p_q.empty():

(heuristic, cost, vertex, path) = p_q.get()

print(“Queue Status:
,
heuristic, cost, vertex, path)

if vertex == destination:
return
heuristic, cost, path

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_node] = heuristic
p_q
.put((heuristic, current_cost, next_node, path + [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:

heuristic, cost, optimal_path = a_star(source, goal)

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 6:

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.