Homework 3.17 - 3.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
- Typically, it is good if something can be achieved in polynomial time, because it meand that if one operation takes one second, x operations take x seconds
- on the other hand exponential efficiency would mean that each operation takes more time than the previous, like a program that would calculate a factorial
- Polynomial efficiency can nave varying levels, like n^2, n^3, n^4, and so on
- Exponential efficiency is linke 2^x, 3^x, or 4^x
- A heuristic approach is to sacrifice a 100% guarantee of a correct answer to save on time and complexity
- heuristic approaches can be helpful in cases where a 100% correct solution isn't necessary
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(array)-1
if value < array[min] or value > array[max]:
return False
while min < max:
mid = (min+max)//2
if array[mid] > value:
max = mid
elif array[mid] < value:
min = mid
elif array[mid] == value:
return True
if max == min+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 = {
'Del Norte':{
'Westview':15,
'MtCarmel':20,
'Poway':35,
'RanchoBernardo':50
},
'Westview':{
'Del Norte':15,
'MtCarmel':35,
'Poway':25,
'RanchoBernardo': 45
},
'MtCarmel':{
'Westview':35,
'Del Norte':20,
'Poway':40,
'RanchoBernardo':30
},
'Poway':{
'Westview':25,
'MtCarmel':40,
'Del Norte':35,
'RanchoBernardo':15
},
'RanchoBernardo':{
'Westview':45,
'MtCarmel':30,
'Poway':15,
'Del Norte':50
}
}
start = 'Del Norte'
schools = {'Del Norte':0,'Westview':1,'MtCarmel':2,'Poway':3,'RanchoBernardo':4}
order = [['Del Norte',0,[False,False,False,False,False],["Del Norte"]]]
bestdist = 100000000000000
bestlist = []
while len(order) > 0:
curr = order.pop()
curr[2][schools[curr[0]]] = True
if curr[2] == [True,True,True,True,True]:
if bestdist > curr[1]+dataset[curr[0]]['Del Norte']:
bestdist = curr[1]+dataset[curr[0]]['Del Norte']
bestlist = curr[3]
continue
for i in dataset[curr[0]].keys():
if curr[2][schools[i]] == False:
newlist = []
for j in curr[2]:
newlist.append(j)
newls = []
for j in curr[3]:
newls.append(j)
newls.append(i)
newcurr = [i,curr[1]+dataset[curr[0]][i],newlist,newls]
order.append(newcurr)
print("The shortest route from Del Norte stopping at each city and returning is " + str(bestdist))
print("The cities on the route in order are:")
for i in bestlist:
print(i)
print("Del Norte")