Lab Task
Subject: Artificial Intelligence.
Name: Muhammad Daniyal Ramzan
Registration No: FA20-BCS-062
Code:
import math
from heapq import heappush, heappop, heapify
# Define Pakistan roadmap and city coordinates
pakistan = {
'Peshawar': {'Islamabad': 180, 'Quetta': 725},
'Islamabad': {'Lahore': 375, 'Peshawar': 180},
'Lahore': {'Faisalabad': 180, 'Islamabad': 375, 'Sialkot': 130},
'Sialkot': {'Lahore': 130},
'Faisalabad': {'Lahore': 180, 'Multan': 350},
'Quetta': {'Gwadar': 680, 'Multan': 500, 'Peshawar': 725, 'Sukkur':
400},
'Gwadar': {'Karachi': 630, 'Quetta': 680},
'Karachi': {'Gwadar': 630, 'Sukkur': 470},
'Sukkur': {'Karachi': 470, 'Multan': 450, 'Quetta': 400},
'Multan': {'Faisalabad': 350, 'Quetta': 500, 'Sukkur': 400}
}
city_geo = {
"Islamabad": (33.6844, 73.0479),
"Lahore": (31.5497, 74.3436),
"Faisalabad": (31.4504, 73.1350),
"Multan": (30.1575, 71.5249),
"Sukkur": (27.7059, 68.8574),
"Karachi": (24.8607, 67.0011),
"Gwadar": (25.1216, 62.3389),
"Peshawar": (34.0151, 71.5249),
"Quetta": (30.1798, 66.9750),
"Sialkot": (32.4945, 74.5229)
}
# Heuristic function using the great-circle distance
def gcircle(city1, city2):
lat1, long1 = city_geo[city1]
lat2, long2 = city_geo[city2]
degrees_to_radians = math.pi / 180.0
phi1, phi2 = lat1 * degrees_to_radians, lat2 * degrees_to_radians
theta1, theta2 = long1 * degrees_to_radians, long2 *
degrees_to_radians
cos_val = (math.cos(phi1) * math.cos(phi2) * math.cos(theta1 - theta2)
+
math.sin(phi1) * math.sin(phi2))
arc = math.acos(cos_val)
return arc * 6373 # Earth's radius in km
def goaltest(city, goal):
return city == goal
def actions(city, roadmap):
return roadmap[city]
def expand(city):
return actions(city, pakistan)
def stepcost(source, destination):
return pakistan[source][destination]
def sld(source, destination):
return gcircle(source, destination)
# Priority Queue Implementation
class PriorityQueue:
def __init__(self):
self._container = []
def empty(self):
return not self._container
def push(self, item):
heappush(self._container, item)
def pop(self):
return heappop(self._container)
class Node:
def __init__(self, state, parent=None, cost=0.0, heuristic=0.0):
self.state = state
self.parent = parent
self.cost = cost
self.heuristic = heuristic
def __lt__(self, other):
return (self.cost + self.heuristic) < (other.cost +
other.heuristic)
# Main Search Function
def search(start, goal, strategy='astar'):
explored = set()
frontier = PriorityQueue()
if strategy == 'astar':
heuristic = lambda x: sld(x, goal)
elif strategy == 'greedy':
heuristic = lambda x: sld(x, goal)
elif strategy == 'ucs':
heuristic = lambda x: 0
frontier.push(Node(start, None, 0.0, heuristic(start)))
while not frontier.empty():
currentNode = frontier.pop()
currentState = currentNode.state
if goaltest(currentState, goal):
return currentNode
explored.add(currentState)
for successor in expand(currentState):
new_cost = currentNode.cost + stepcost(currentState,
successor)
successorNode = Node(successor, currentNode, new_cost,
heuristic(successor))
if successor not in explored:
frontier.push(successorNode)
return None
# Backtrack and print the path from start to goal
def print_path(node):
path = []
while node:
path.append(node.state)
node = node.parent
print(" -> ".join(path[::-1]))
# Running and Testing the Searches
result = search("Islamabad", "Karachi", strategy="astar")
print("A* Path:")
print_path(result)
print("Total Cost:", result.cost)
result = search("Islamabad", "Karachi", strategy="greedy")
print("\nGreedy Search Path:")
print_path(result)
print("Total Cost:", result.cost)
result = search("Islamabad", "Karachi", strategy="ucs")
print("\nUniform Cost Search Path:")
print_path(result)
print("Total Cost:", result.cost)
Output is here:
A* Path:
Islamabad -> Peshawar -> Quetta -> Sukkur -> Karachi
Total Cost: 1775.0
Greedy Search Path:
Islamabad -> Peshawar -> Quetta -> Sukkur -> Karachi
Total Cost: 1775.0
Uniform Cost Search Path:
Islamabad -> Lahore -> Faisalabad -> Multan -> Sukkur -> Karachi
Total Cost: 1775.0
