Homework 3.17 - 3.18
Vocabulary
- Problem: A task that could be solved algorithmically or logically
- Decision Problem: A problem that demands a boolean yes or no answer
- Organization Problem: A problem that demands a "best" or "optimal" answer
- Instance: A problem with a specific input
- Efficiency: amount of time, space, or resources it takes to solve a problem.
- Polynomial Efficiency (Good): More work takes a proportional amount of time and resources to complete.
- Exponential Efficiency (Bad): More work takes an exponential amount of time to compelete.
- Heuristic Approach: When optimal solutions are inefficient, look for an even more optimal solution
- Decidable Problem: A decision solution that always gives the right answer
- Undecidable Problem: A decision problem with no solution that is guaranteed to give the right answer
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):
#--------------------
# We use binary Search here :)
lo = 0
hi = len(array)-1
while lo <= hi:
mid = (lo+hi)//2
if mid == value:
return True
elif mid > value:
hi = mid - 1
else:
lo = 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
}
}
dataset_graph = [
[0,15,20,35,50],
[15,0,35,25,45],
[20,35,0,40,30],
[35,25,40,0,15],
[50,45,30,15,0]
]
def fastestroute(start,data):
drivetime = 0
order = [start]
curr = start
while len(order) < 5:
min_dist = 60
for key in data[curr]:
if data[curr][key] < min_dist and key not in order:
next = key
min_dist = data[curr][key]
order.append(next)
curr = next
drivetime+=min_dist
drivetime+=data[curr][start]
order.append(start)
#CODE,CODE,CODE
return(drivetime,order)
start = 'DelNorte'
print(fastestroute(start, dataset))
# 'dataset' is the name of the nested key value pair
Optimal Approach
From one look at the problem, we can deduce that it is likely testing graph theory. The data in the data set dictionary could be converted into an undirected weighted graph, where each position is linked to the other with a weighted path, where the weight is the assigned distance. We can then attempt to find the MST (Mean Spanning Tree) of the graph through a BFS approach
from collections import defaultdict
import sys
class undirectedWeightedGraph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[None for i in range(self.V)] for i in range(self.V)]
def addVertice(self, s , d, weight):
self.graph[s].append((d,weight))
def printGraph(self):
print("Location\tEdges")
for i in range(self.V):
temp = [str(k) for k in self.graph[i]]
print(str(i) + "\t\t" + " ".join(temp))
def shortestPathLength(graph):
if len(graph) == 1:
return 0
n = len(graph)
ending_mask = (1 << n) - 1
queue = [(node, 1 << node) for node in range(n)]
seen = set(queue)
steps = 0
while queue:
next_queue = []
for i in range(len(queue)):
node, mask = queue[i]
for neighbor in graph[node]:
next_mask = mask | (1 << neighbor)
if next_mask == ending_mask:
return 1 + steps
if (neighbor, next_mask) not in seen:
seen.add((neighbor, next_mask))
next_queue.append((neighbor, next_mask))
steps += 1
queue = next_queue
locations = undirectedWeightedGraph(5)
locations.graph = dataset_graph
locations.printGraph()
print(shortestPathLength(locations.graph))
Now that we have created a graph for our schools, we can move on to using djikstra's algorithm to find the most optimal path