Hello,
I have done little piece of work for finding nearest shortest route from
one point on a graph to other with connected points(cities to be
precise). The way i achieved it is by getting the nearest neighbours in
(NE, NE, SE, SW) and then traversing them one by one until i reach my
destination in the first instance of recursion. this thing works for me
and i am not looking for route solving problems but rather a peculiar
problem of running different lines of code arbitarily.
The problem with my coding is that it follows a strict route search
algorithm that i hardcoded i.e.
it first searches NE, then NW, then SE, and finally SW. this code will
always find a route but will not be the shortest route which could
either start from any direction. So i have to devise a way by which i
can run all the posibilities to find the best route. so i have to run
4*3*3*3 runs to find out the shortest route. My code is as below, any
way i can achieve it in python without typing all the posibilites.
def GetShortestRoute(source:list,destination:City,recursion=0):
print("recursion",recursion)
#print(source)
assert type(source)==list,"Source must be a list of list"
assert len(source)>0,"Source must contain atleast 1 item"
assert type(source[0])==list,"Sub items of source must be a list"
#debug
for route in source:
print (route)
#end Debug
#found something
foundlist=[]
for miniroute in source:
if destination in miniroute:
print("found",destination," in ",miniroute,":", destination
in miniroute)
foundlist.append(miniroute)
else:
print("Not found",destination," in ",miniroute,":",
destination in miniroute)
#print ("length of found list",len(foundlist),foundlist)
#retun the shortest amongst the find
shortestRoute=[None,9999999.9]
if len(foundlist)>0:
for miniroute in foundlist:
#print("shortest distance",shortestRoute[1])
distance=calculateRouteDistantce(miniroute)
#print("distance calculated",distance)
if distance<shortestRoute[1]:
shortestRoute[1]=distance
shortestRoute[0]=miniroute
return shortestRoute
#not found
duplicatesource=source[:]
for route in source:
lastCity=route[len(route)-1]
#the part i do not want to recode everytime to find the shortest route
if lastCity.NE!=None and
isCityInRouteList(lastCity.NE,source)==False:
tmproute=route[:]
tmproute.append(lastCity.NE)
if tmproute not in duplicatesource:
duplicatesource.append(tmproute)
if lastCity.NW!=None and
isCityInRouteList(lastCity.NW,source)==False:
tmproute=route[:]
tmproute.append(lastCity.NW)
if tmproute not in duplicatesource:
duplicatesource.append(tmproute)
if lastCity.SE!=None and
isCityInRouteList(lastCity.SE,source)==False:
tmproute=route[:]
tmproute.append(lastCity.SE)
if tmproute not in duplicatesource:
duplicatesource.append(tmproute)
if lastCity.SW!=None and
isCityInRouteList(lastCity.SW,source)==False:
tmproute=route[:]
tmproute.append(lastCity.SW)
if tmproute not in duplicatesource:
duplicatesource.append(tmproute)
#end of the part
return GetShortestRoute(duplicatesource,destination,recursion+1)
Thanks
George
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
