Suppose you have to travel Iqra University Gulshan campus 1 to Iqra University Main Campus. If the goal is IU Main campus, we need to know the straight-line distances to IU Main Campus. Implement the given graph using ,
UCS (uniform cost search),
A* search and find the optimal solution.
Design functions of initial state ,goal state, Successor function and path cost function
(Implement it by using problem solving agent steps).
Click here for Question > Link
Solution
class Graph:
def _init_(self, adjacency_list):
self.adjacency_list = adjacency_list
def get_neighbors(self, v):
return self.adjacency_list[v]
def h(self, n):
H = {
'IUGC' : 3,
'Expo Centre Bus stop' : 1,
'Sir Syed Stop' : 5,
'Patel Hospital' : 6,
'Urdu University' : 2,
'Jail Chawrangi' : 4,
'Allama Shabbir Ahmed Road' : 2,
'National Stadium' : 4,
'Rashid Minhas Road' : 8,
'Shahrah-e-Faisal road' : 2,
'Water Pump' : 3,
'Teenhatti' : 7,
'Iqra University Main campus' : 0,
}
return H[n]
def a_star_algorithm(self, start_node, stop_node):
open_list = set([start_node])
closed_list = set([])
g = {}
g[start_node] = 0
parents = {}
parents[start_node] = start_node
while len(open_list) > 0:
n = None
for v in open_list:
if n == None or g[v] + self.h(v) < g[n] + self.h(n):
n = v;
if n == None:
print('Path does not exist!')
return None
if n == stop_node:
reconst_path = []
while parents[n] != n:
reconst_path.append(n)
n = parents[n]
reconst_path.append(start_node)
reconst_path.reverse()
print('Path found: {}'.format(reconst_path))
print('Path Cost is : ',g[v] + self.h(v))
return reconst_path
for (m, weight) in self.get_neighbors(n):
if m not in open_list and m not in closed_list:
open_list.add(m)
parents[m] = n
g[m] = g[n] + weight
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n
if m in closed_list:
closed_list.remove(m)
open_list.add(m)
open_list.remove(n)
closed_list.add(n)
print('Path does not exist!')
return None
adjacency_list = {
'IUGC': [('Sir Syed Stop',6), ('Patel Hospital',3),('Water Pump',5)],
'Sir Syed Stop': [('Expo Centre Bus stop',3), ('Urdu University',1),('Rashid Minhas Road',3)],
'Patel Hospital': [('Allama Shabbir Ahmed Road',2)],
'Water Pump': [('Teenhatti',3)],
'Expo Centre Bus stop': [('National Stadium',4)],
'Urdu University': [('Jail Chawrangi',6)],
'Rashid Minhas Road': [('Shahrah-e-Faisal road',8)],
'Jail Chawrangi': [('Iqra University Main campus',12)],
'Allama Shabbir Ahmed Road': [('Rashid Minhas Road',7)],
'National Stadium': [('Shahrah-e-Faisal road',6)],
'Shahrah-e-Faisal road': [('Iqra University Main campus',15)],
'Teenhatti': [('Jail Chawrangi',9)],
'Iqra University Main campus': []
}
graph1 = Graph(adjacency_list)
graph1.a_star_algorithm('IUGC', 'Iqra University Main campus' )
import copy
import queue as Q
class UCS:
def _init_(self):
self.graph = dict()
self.cost_dict = dict()
self.final_dict = dict()
def INITIALSTATE(self,u,v,c):
if u not in self.graph:
qu = Q.PriorityQueue()
self.graph.update({u:qu})
self.graph[u].put(v)
self.cost_dict.update({(u,v):c})
def tnode(self,n):
self.visited = [False]*n
def ACTUATOR(self,s,visited,path,goal,value):
path.append(s)
visited[s] = True
if goal == s:
self.final_dict.update({tuple(path):value})
return
for i in self.graph[s].queue:
if visited[i] == False:
self.ACTUATOR(i,copy.deepcopy(visited),copy.deepcopy(path),goal,value+self.cost_dict[s,i])
def GOAL(self,s,goal):
self.visited[s] = True
path = [s]
for i in self.graph[s].queue:
if self.visited[i] == False:
value = self.cost_dict[s,i]
self.ACTUATOR(i, copy.deepcopy(self.visited), copy.deepcopy(path), goal, value)
def all_paths(self):
if bool(self.final_dict):
print("All the path: ")
for i in self.final_dict:
print("path: ",i,"cost: ",self.final_dict[i])
else:
print("No path exist between start node to goal node")
def optimal_path(self):
if bool(self.final_dict):
print("\nbest path: ",min(self.final_dict,key=self.final_dict.get))
else:
print("No path exist between start node to goal node")
graph = {'IUGC': ['Sir Syed Stop', 'Patel Hospital','Water Pump'],
'Sir Syed Stop': ['Expo Centre Bus stop', 'Urdu University','Rishid Minhas Road'],
'Patel Hospital': ['Allama Shabbir Ahmed Road'],
'Water Pump': ['Teenhatti'],
'Expo Centre Bus stop': ['National Stadium'],
'Urdu University': ['Jail Chawrangi'],
'Rishid Minhas Road': ['Shahrah-e-Faisal road'],
'Jail Chawrangi': ['Iqra University Main campus'],
'Allama Shabbir Ahmed Road': ['Rishid Minhas Road'],
'National Stadium': ['Shahrah-e-Faisal road'],
'Shahrah-e-Faisal road': ['Iqra University Main campus'],
'Teenhatti': ['Jail Chawrangi'],
'Iqra University Main campus': []
}
g = UCS()
g.tnode(13)
g.INITIALSTATE(0,1,6);g.INITIALSTATE(0,2,3);g.INITIALSTATE(0,3,5)
g.INITIALSTATE(1,4,3);g.INITIALSTATE(1,5,1);g.INITIALSTATE(1,6,3)
g.INITIALSTATE(2,8,2)
g.INITIALSTATE(3,11,7)
g.INITIALSTATE(4,9,4)
g.INITIALSTATE(5,7,6)
g.INITIALSTATE(6,10,8)
g.INITIALSTATE(7,12,12)
g.INITIALSTATE(8,6,7)
g.INITIALSTATE(9,10,6)
g.INITIALSTATE(10,12,15)
g.INITIALSTATE(11,7,9)
g.GOAL(0,12)
g.all_paths()
No comments:
Post a Comment