Sections 17-18
Vocabulary
- Problem: a general description of a task that can or cannot be solved algorithmically
- Decision Problem: A problem with a yes or no answer
- Organization Problem: a problem with a goal of finding the best answer
- Instance: a problem with a specific input
- Efficiency: amount of computing needed to solve a problem
- Polynomial Efficiency (Good): more work takes a proportional amount of time (1 job is +2 time)
- Exponential Efficiency (Bad): more work takes an exponential amount more time (1 job is 2x time)
- Heuristic Approach: When optimal solutions are inefficient, look for a possibly optimal solution that is more efficient
- Decidable Problem: A decision problem that has a clear solution that will always make a correct output
- Undecidable Problem: A decision problem with no solution that is not gaurenteed to produce the correct output
Notes
- Different code that all completes the same task can have different amounts of times to run
- This amount of run time shows varyihg levles of polynomical efficiency
- Sometimes requirements that have to be met are very complex, and ideally it would be good to meet all of those requirements perfectly
- However, it may be hard or take too long to meet those perfectly, a Heuristic approach is when we sacrifice optimal solutions to improve efficiency and easy of programming, by using solutions that are "good enough" to have a satisfactory outcome
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):
exists = False
while exists == False:
for i in range(len(array)):
if value == array[i]:
exists = True
else:
return exists
return exists
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')
- Decreased to ~ 0.5 seconds
- I found that using an else statement instead of elif in line 11 dramatically cut down the time.
- This is because with the previous elif statement, it actually had to check if the statement requirements were met. This takes time.
- On the other hand, with the else statement, it doesn't need to check for anything further than the inital if statement, which takes a lot less time.
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):
upper = (len(array)-1)
lower = 0
while upper > lower:
middle = (lower+upper)//2
if middle == value:
return True
elif middle > value:
upper = middle - 1
else:
lower = middle + 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')
- Decreased to ~ 0.4 seconds
- This is the binary search method that we were suggested to implement in class
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
}
}
My thought process for this was to make a route based on the shortest time of each location. So for example at each stop, you would see which would be the next closest and go to there.
# start from the "start" school, recursively go to the next school, until all schools have been passed and reach start0
def findBestRoute(start, schools, route, total_time):
global min_total_time, best_route, route_count, start0
for loc, time in schools[start].items():
if loc not in route:
saved_route = route.copy() # do not use saved_route = route, that is not list copy!!
saved_total_time = total_time
route.append(loc)
total_time += time
# start from the loc, recursively go to the next school, until all schools have been passed and reach start0
findBestRoute(loc, schools, route, total_time)
# resume
route = saved_route
total_time = saved_total_time
if total_time > min_total_time: # time is already too long, no need further check
return
if len(route) == 5 and loc == start0:
route_count += 1
route.append(loc)
#print(route_count, route, total_time)
if total_time < min_total_time:
best_route=route.copy()
min_total_time=total_time
return
min_total_time=10000
start0 = 'DelNorte'
route=[start0]
best_route = []
total_time = 0
route_count = 0
findBestRoute(start0, dataset, route, total_time)
#print ("Total checked route # is "+str(route_count))
print("Best Route:", best_route)
print("Drive Time:", min_total_time, "minutes")