Skip to content
Gallery
All Pracs
Share
Explore
RMP File
dict_hn = {'Arad': 336, 'Bucharest': 0, 'Craiova': 160, 'Drobeta': 242, 'Eforie': 161,
'Fagaras': 176, 'Giurgiu': 77, 'Hirsova': 151, 'Iasi': 226, 'Lugoj': 244,
'Mehadia': 241, 'Neamt': 234, 'Oradea': 380, 'Pitesti': 100, 'Rimnicu': 193,
'Sibiu': 253, 'Timisoara': 329, 'Urziceni': 80, 'Vaslui': 199, 'Zerind': 374}
dict_gn = dict(
Arad=dict(Zerind=75, Timisoara=118, Sibiu=140),
Bucharest=dict(Urziceni=85, Giurgiu=90, Pitesti=101, Fagaras=211),
Craiova=dict(Drobeta=120, Pitesti=138, Rimnicu=146),
Drobeta=dict(Mehadia=75, Craiova=120),
Eforie=dict(Hirsova=86),
Fagaras=dict(Sibiu=99, Bucharest=211),
Giurgiu=dict(Bucharest=90),
Hirsova=dict(Eforie=86, Urziceni=98),
Iasi=dict(Neamt=87, Vaslui=92),
Lugoj=dict(Mehadia=70, Timisoara=111),
Mehadia=dict(Lugoj=70, Drobeta=75),
Neamt=dict(Iasi=87),
Oradea=dict(Zerind=71, Sibiu=151),
Pitesti=dict(Rimnicu=97, Bucharest=101, Craiova=138),
Rimnicu=dict(Sibiu=80, Pitesti=97, Craiova=146),
Sibiu=dict(Rimnicu=80, Fagaras=99, Arad=140, Oradea=151),
Timisoara=dict(Lugoj=111, Arad=118),
Urziceni=dict(Bucharest=85, Hirsova=98, Vaslui=142),
Vaslui=dict(Iasi=92, Urziceni=142),
Zerind=dict(Oradea=71, Arad=75)
)

Practical 1

AIM: Implement Breadth first search algorithm for Romanian map problem.
Code
import queue as Q
from RMP import dict_gn
start = 'Arad'
goal = 'Bucharest'
result = ''
def BFS(city, cityq, visitedq):
global result
if city == start:
result = result + ' '+city
for eachcity in dict_gn[city].keys():
if eachcity == goal:
result = result+' '+eachcity
return
if eachcity not in cityq.queue and eachcity not in visitedq.queue:
cityq.put(eachcity)
result = result+' '+eachcity
visitedq.put(city)
BFS(cityq.get(), cityq, visitedq)

def main():
cityq = Q.Queue()
visitedq = Q.Queue()
BFS(start, cityq, visitedq)
print("BFS Traversal from", start, "to", goal, "is: ")
print(result)

main()

Practical 2

AIM: Implement IDDFS(Iterative Deepening Depth-First Search).
import queue as Q
from RMP import dict_gn
start = 'Arad'
goal = 'Bucharest'
result = ''

def DLS(city, visitedstack, startlimit, endlimit):
global result
found = 0
result = result+city+''
visitedstack.append(city)
if city == goal:
return 1
if startlimit == endlimit:
return 0
for eachcity in dict_gn[city].keys():
if eachcity not in visitedstack:
found = DLS(eachcity, visitedstack, startlimit+1, endlimit)
if found:
return found

def IDDFS(city, visitedstack, endlimit):
global result
for i in range(0, endlimit):
print("Searching at Limit: ", i)
found = DLS(city, visitedstack, 0, 1)
if found:
print("Found")
break
else:
print("Not found!")
print(result)
print("--------")
result = ''
visitedstack = []

def main():
visitedstack = []
IDDFS(start, visitedstack, 9)
print("IDDFS Traversal from", start, " to ", goal, "is: ")
print(result)

main()

Practical 3

AIM: Implement A* search.
import queue as Q
from RMP import dict_gn
from RMP import dict_hn
start = 'Arad'
goal = 'Bucharest'
result = ''

def get_fn(citystr):
cities = citystr.split(" , ")
hn = gn = 0
for ctr in range(0, len(cities)-1):
gn = gn+dict_gn[cities[ctr]][cities[ctr+1]]
hn = dict_hn[cities[len(cities)-1]]
return(hn+gn)

def expand(cityq):
global result
tot, citystr, thiscity = cityq.get()
if thiscity == goal:
result = citystr+" : : "+str(tot)
return
for cty in dict_gn[thiscity]:
cityq.put((get_fn(citystr+" , "+cty), citystr+" , "+cty, cty))
expand(cityq)

def main():
cityq = Q.PriorityQueue()
thiscity = start
cityq.put((get_fn(start), start, thiscity))
expand(cityq)
print("The A* path wiht total is : ")
print(result)

main()

Practical 4

AIM: RBFS(Recursive Breadth First Search)
import queue as Q
from RMP import dict_gn
from RMP import dict_hn
start='Arad'
goal='Bucharest'
result=''
def get_fn(citystr):
cities=citystr.split(',')
hn=gn=0
for ctr in range(0,len(cities)-1):
gn=gn+dict_gn[cities[ctr]][cities[ctr+1]]
hn=dict_hn[cities[len(cities)-1]]
return(hn+gn)
def printout(cityq):
for i in range(0,cityq.qsize()):
print(cityq.queue[i])
def expand(cityq):
global result
tot,citystr,thiscity=cityq.get()
nexttot=999
if not cityq.empty():
nexttot,nextcitystr,nextthiscity=cityq.queue[0]
if thiscity==goal and tot<nexttot:
result=citystr+'::'+str(tot)
return
print("Expanded city---------------",thiscity)
print("Second best f(n)--------------",nexttot)
tempq=Q.PriorityQueue()
for cty in dict_gn[thiscity]:
tempq.put((get_fn(citystr+','+cty),citystr+','+cty,cty))
for ctr in range(1,3):
ctrtot,ctrcitystr,ctrthiscity=tempq.get()
if ctrtot<nexttot:
cityq.put((ctrtot,ctrcitystr,ctrthiscity))
else:
cityq.put((ctrtot,citystr,thiscity))
break
printout(cityq)
expand(cityq)
def main():
cityq=Q.PriorityQueue()
thiscity=start
cityq.put((999,"NA","NA"))
cityq.put((get_fn(start),start,thiscity))
expand(cityq)
print(result)
main()

Practical 5

AIM: Implement Decision-Tree learning algorithm. #REQUIREMENTS:
balance-scale.names
2.2 kB
balance-scale.data
6.3 kB
1)---file1(balance-scale.data) & file2(balance-scale.names)
Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.