Homework 3.17 - 3.18
Vocabulary
- Problem:
- Decision Problem: A problem with yes/no answer
- Organization Problem: A problem with the goal of finding a best answer
- Instance: Problem with specific input
- Efficiency: How much computing you need for a problem to be resolved
- Polynomial Efficiency (Good): Proportional amount of time (linear) the more work you do
- Exponential Efficiency (Bad): Exponential amount of time the more work you do (ex: double the amount of time)
- Heuristic Approach: Finding a more efficient optimal solution
- Decidable Problem: A decision problem with a solution that always outputs correctly
- Undecidable Problem: A decision problem with no solution
Notes
- Code that performs the same task can have a different amount of time that it runs
- The more functions you add, the more time it takes to run the code
For example, an add function that converts
tointand thentostrwill take up more seconds than a function that merely adds the functions and returns the value to a print statement (because a print statement can print an integer if that is the only value) - Polynomial creates the least cycles (ex: 3x and (2x)^2) vs exponential which creates more cycles (ex: 3^x)
- Undecidable problem: Give multiple answers or none
import time
numlist = [1,3,5,7,9,11,13,15,17,19]
valuelist = [0,3,6,9,12,15,18,21]
def isvalue(value,array):
#--------------------
min = 0
max = len(numlist) - 1
while max >= min:
mid = (min + max) // 2
if array[mid] == value:
return True
elif array[mid] > value:
max = mid - 1
else:
min = mid + 1
return False
#--------------------
starttime = time.time()
for i in range(100000):
for i in range(len(valuelist)):
x = isvalue(valuelist[i],numlist)
endtime = time.time()
print(endtime-starttime,'seconds')
Homework!
Make an algorithm that finds the fastest route that hits every location once starting and ending at Del Norte. Make sure to show your thinking. If you are strugling, try using a huristic approach. Remember, what matters more than having perfectly functioning code is that you tried your hardest.
dataset = {
'DelNorte':{
'Westview':15,
'MtCarmel':20,
'Poway':35,
'RanchoBernardo':50
},
'Westview':{
'DelNorte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernardo': 45
},
'MtCarmel':{
'Westview':35,
'DelNorte':20,
'Poway':40,
'RanchoBernardo':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'DelNorte':35,
'RanchoBernardo':15
},
'RanchoBernardo':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'DelNorte':50
}
}
Ver 1
I don't know how to make the most efficient algorithm to find the best path. This is my code below, which uses nested for loops to find the shortest route to each location (while making sure that they haven't been reached yet). I also have multiple attempts below that worked and did not work to show that I did try many times (took me 2 hours to figure out lol)
def fastestroute(start,data):
drivetime = 0
order = []
#CODE,CODE,CODE
order.append(start)
travelPlace2 = start
for i in range (len(dataset) - 1):
shortestTime = 100
travelPlace = travelPlace2
for j in range(len(dataset[travelPlace])):
if list(dataset[travelPlace].values())[j] < shortestTime:
if list(dataset[travelPlace].keys())[j] not in order:
shortestTime = list(dataset[travelPlace].values())[j]
travelPlace2 = list(dataset[travelPlace].keys())[j]
else:
continue
order.append(travelPlace2)
drivetime += shortestTime
drivetime += dataset[travelPlace2]["DelNorte"]
start = 'DelNorte'
data = dataset
fastestroute(start, data)
print("The route is: " + str(order))
print("Total time is: " + str(drivetime))
# 'dataset' is the name of the nested key value pair
drivetime = 0
def fastestroute(start,data):
global drivetime
drivetime = 0
global order
order = []
#CODE,CODE,CODE
order.append(start)
travelPlace2 = start
shortestTime = 100
travelPlace = travelPlace2
for j in range(len(dataset[travelPlace])):
if list(dataset[travelPlace].values())[j] < shortestTime:
if list(dataset[travelPlace].keys())[j] not in order:
shortestTime = list(dataset[travelPlace].values())[j]
travelPlace2 = list(dataset[travelPlace].keys())[j]
else:
continue
order.append(travelPlace2)
drivetime += shortestTime
print(order)
print(travelPlace2)
shortestTime = 100
travelPlace = travelPlace2
for j in range(len(dataset[travelPlace])):
if list(dataset[travelPlace].values())[j] < shortestTime:
if list(dataset[travelPlace].keys())[j] not in order:
shortestTime = list(dataset[travelPlace].values())[j]
travelPlace2 = list(dataset[travelPlace].keys())[j]
else:
continue
order.append(travelPlace2)
drivetime += shortestTime
print(order)
print(travelPlace2)
shortestTime = 100
travelPlace = travelPlace2
for j in range(len(dataset[travelPlace])):
if list(dataset[travelPlace].values())[j] < shortestTime:
if list(dataset[travelPlace].keys())[j] not in order:
shortestTime = list(dataset[travelPlace].values())[j]
travelPlace2 = list(dataset[travelPlace].keys())[j]
else:
continue
order.append(travelPlace2)
drivetime += shortestTime
print(order)
print(travelPlace2)
shortestTime = 100
travelPlace = travelPlace2
for j in range(len(dataset[travelPlace])):
if list(dataset[travelPlace].values())[j] < shortestTime:
if list(dataset[travelPlace].keys())[j] not in order:
shortestTime = list(dataset[travelPlace].values())[j]
travelPlace2 = list(dataset[travelPlace].keys())[j]
else:
continue
order.append(travelPlace2)
drivetime += shortestTime
print(order)
print(travelPlace2)
print(drivetime)
drivetime += dataset[travelPlace2]['DelNorte']
print(drivetime)
start = 'DelNorte'
data = dataset
fastestroute(start, data)
# 'dataset' is the name of the nested key value pair
drivetime = 0
def fastestroute(start,data):
global drivetime
drivetime = 0
global order
order = []
#CODE,CODE,CODE
order.append(start)
travelPlace = start
for i in range(4):
initialPlace = list(dataset[travelPlace].values()[0])
for j in range(len(dataset[travelPlace])):
while initialPlace in order:
shortestTime = list(dataset[travelPlace].values())[0]
travelPlace = list(dataset[travelPlace].keys())[0]
search = list(dataset[travelPlace].keys())[j]
if search not in order:
if list(dataset[travelPlace].values())[j] < shortestTime:
shortestTime = list(dataset[travelPlace].values())[j]
travelPlace = list(dataset[travelPlace].keys())[j]
order.append(travelPlace)
drivetime += shortestTime
print(order)
print(drivetime)
start = 'DelNorte'
data = dataset
fastestroute(start, data)
# 'dataset' is the name of the nested key value pair
drivetime = 0
def fastestroute(start,data):
global drivetime
drivetime = 0
global order
order = []
#CODE,CODE,CODE
order.append(start)
mv(start)
def mv(travelPlace):
global drivetime
shortestTime = list(dataset[travelPlace].values())[0]
travelPlace = list(dataset[travelPlace].keys())[0]
for j in range(len(dataset[travelPlace])):
search = list(dataset[travelPlace].keys())[j]
if find(search):
if list(dataset[travelPlace].values())[j] < shortestTime:
shortestTime = list(dataset[travelPlace].values())[j]
travelPlace = list(dataset[travelPlace].keys())[j]
order.append(travelPlace)
drivetime += shortestTime
mv(travelPlace)
print(order)
def find(nextPlace):
for i in range(len(order)):
if nextPlace == order[i]:
return False
return True
print(drivetime)
print(order)
#return(drivetime,order)
start = 'DelNorte'
data = dataset
fastestroute(start, data)
# 'dataset' is the name of the nested key value pair
def fastestroute(start,data):
drivetime = 0
order = []
#CODE,CODE,CODE
for i in range(len(dataset)):
place = list(dataset.keys())[i]
shortestTime = list(dataset[place].values())[0]
travelPlace = ""
for j in range(len(dataset[place])):
if list(dataset[place].values())[j] < shortestTime:
shortestTime = list(dataset[place].values())[j]
travelPlace = list(dataset[place].keys())[j]
if travelPlace != "":
order.append(travelPlace)
drivetime += shortestTime
print(drivetime)
print(order)
#return(drivetime,order)
start = 'DelNorte'
data = dataset
fastestroute(start, data)
# 'dataset' is the name of the nested key value pair