Homework 3.17 - 3.18
Vocabulary
- Problem: A general descriptionof a task that can't be solved algorithmically
- Decision Problem: A problem with a yes or no answer
- Organization Problem: A problem about finding the best anser
- Instance: A problem with a specific input
- Efficiency: Amount of computing needed for a input
- Polynomial Efficiency (Good): More work takes a proportional amount of time
- Exponential Efficiency (Bad): More work takes an exponential amount of time
- Heuristic Approach: When the optimal is inefficient, look for a possibly optimal solution with better efficiency
- Decidable Problem: A problem with a clear answer
- Undecidable Problem: A problem with no solution not been guaranteed to produce the correct the correct output
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):
#--------------------
return value in array
"""
Binary Solution (less efficient):
copy=array.copy()
copy.sort()
low=0
high=len(array)-1
while low<=high:
mid = (low+high)//2
if copy[mid]<value:
low=mid+1
else:
high=mid
return copy[mid]==value"""
#--------------------
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 = {
'Del Norte':{
'Westview':15,
'MtCarmel':20,
'Poway':35,
'RanchoBernado':50
},
'Westview':{
'Del Norte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernado': 45
},
'MtCarmel':{
'Westview':35,
'Del Norte':20,
'Poway':40,
'RanchoBernado':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'Del Norte':35,
'RanchoBernado':15
},
'RanchoBernado':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'Del Norte':50
}
}
import time
def fastestroutefast(start,last,time,order): # The algorithm returns a fast route quickly
global dataset
if len(order)>=len(dataset):
return time+dataset[start]["Del Norte"], order+["Del Norte"]
nextStop=["",2147483647]
for i in dataset[start]: # go to the closest school
if order.count(i)==0 and i!=last:
if nextStop[1]>dataset[start][i]:
nextStop[0]=i
nextStop[1]=dataset[start][i]
return fastestroutefast(nextStop[0],start,time+nextStop[1],order+[nextStop[0]])
def fastestroutebest(start,last,time,order): # The algorithm that returns the fastest route
global dataset
ansTime=2147483647
ansOrder=[]
tempTime=0
tempOrder=[]
if len(order)>=len(dataset) and start!="Del Norte":
return time, order+["Del Norte"] # return the time it took to get this school and order
for i in dataset[start]: # go to the every school
if order.count(i)==0 and i!=last:
tempTime,tempOrder=fastestroutebest(i,start,time+dataset[start][i],order+[i])
if ansTime>tempTime:
ansTime=tempTime
ansOrder=tempOrder
return ansTime,ansOrder
# Look for a solution, recoding time with time module
startTime=time.time()
fast=fastestroutefast("Del Norte","",0,["Del Norte"])
endTime=time.time()
print(fast,endTime-startTime)# huristic approach saves time
startTime=time.time()
best=fastestroutebest("Del Norte","",0,["Del Norte"])
endTime=time.time()
print(best,endTime-startTime)