Tillämpad Matematik i programmering

Explore

Övningar till 7 feb

Matris
Matris

There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.

Example 1:

Input:

n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]

src = 0, dst = 2, k = 1

Output: 200

Explanation:

The graph looks like this:

⁠

The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

1. Steps to Solve Problems

Matrix can be expanded to a graph related problem. The steps are:

(1) building a graph where the index are the node number, and the graph[i] would be a list of elements (could be other_node or a tuple or a list (other_node, weight)).

(2) Second step is to decompose the problem into subproblems.

(3) where each subproblem could be resolved by Dynamic Programming (BFS or DFS). Note: There might need some minor changes to adopt the standard algorithms.

(4) After this, we need to further thinking about how to improve the efficiency (time and space). Normally, the condition that might lead near ending of the graph algorithm.

(5) Explain the difference of the time complexity and the space complexity to the interviewers

According to this order, the above example is resolved with the following python code:

import sys

class Solution(object):

def findCheapestPrice(self, n, flights, src, dst, K):

"""

:type n: int

:type flights: List[List[int]]

:type src: int

:type dst: int

:type K: int

:rtype: int

"""

#(1). Construct Graph

#one dimension with elements to be list

graph = [[] for _ in xrange(n)]

for s,e,w in flights:

graph[s].append((e,w))

#(2) Graph Algorithm

q= [(src,0)] #stop and price

count = 0

min_price= sys.maxint #record the minimum price so far

while q:

next_stops = []

for cur, acc_price in q: #same level

for end,price in graph[cur]:

#conditional satisfied, save the price

if end==dst:

min_price = min(min_price, acc_price+price)

#(4) Cut down the complexity

#Instead of directly add the next stop, we only add those stops that have less accumulated price

if min_price>acc_price+price:

next_stops.append((end,acc_price+price) )

#(4) Instead of directly add the next stop, we only add those stops that have

if count==K:

if min_price<sys.maxint:

return min_price

else:

return -1

q=next_stops[:]

count+=1

# this is important too

if count<=K:

if min_price<sys.maxint:

return min_price

else:

return -1

Another example focusing about python code: 399. Evaluate Division

2. Graph Algorithms

(a) Represent Graph

Adjacency list: [[1,2,3],[3,1],[4,6,1]], node 0 connects to 1,2,3, node 1 connect to 3,1, node 2 connects to 4,6,1

graph = [[] for _ in xrange(nodes)]

Adjacency matrices:

graph = [[0 for _ in xrange(cols)] for _ in xrange(rows)] #normally, rows=cols

If you need a “name” for each node, and before the graph is complete, you do not know how many nodes you might get, use dictionary, for example, we are given a list of edges[[“a”,”c”],[b,c],[b,e]….]

from collections import defaultdict

d = defaultdict(set) # structure initialization

# add an edge (remember to add to both vertices!) for ver1, ver2 in edges:

d[ver1].add(ver2)graph = { "a" : ["c"],

"b" : ["c", "e"],

"c" : ["a", "b", "d", "e"],

"d" : ["c"],

"e" : ["c", "b"],

"f" : []

}

If we need weights for each edge, use dictionary from the default dictionary to represent:

graph= collections.defaultdict(dict)

for (num, den), val in zip(equations, values):

graph[num][num] = graph[den][den] = 1.0

graph[num][den] = val

graph[den][num] = 1 / val

#defaultdict(<type 'dict'>, {u'a': {u'a': 1.0, u'b': 2.0}, u'c': {u'c': 1.0, u'b': 0.3333333333333333}, u'b': {u'a': 0.5, u'c': 3.0, u'b': 1.0}})

Function to generate the list of all edges:

def generate_edges(graph):

edges = []

for node in graph:

for neighbour in graph[node]:

edges.append((node, neighbour)) return edgesprint(generate_edges(graph))

(b) Breadth-First-Search (BFS)

#implement using a queue

def BFS(root):

q = [root]

root.visited = 1

while q:

n=q.pop()

visit(n) #finish visit

for node in n.adjacent:

if not node.visited:

node.visited = 1 #start to visit

q.insert(0,node)# a mutant for trees to visit it level by level

def BFS(root):

q = [root]

root.visited = 1

level = 0

while q:

n=q.pop()

visit(n) #finish visit

for node in n.adjacent:

if not node.visited:

node.visited = 1 #start to visit

q.insert(0,node)

Or we use the library Queue:

Example of how to wait for enqueued tasks to be completed:

def worker():

while True:

item = q.get()

do_work(item)

q.task_done()q = Queue()

for i in range(num_worker_threads):

t = Thread(target=worker)

t.daemon = True

t.start()for item in source():

q.put(item)q.join()

#Recursive

def DFS(root):

#END Condition

if not root:

return

visit(root)

for node in root.adjacent:

if not node.visited:

DFS(node)#Iterative, implemented using a stack

def DFS_iter():

root.visited = 1

stack = []

stack.append(root)

while stack:

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.

MatrisMatris

1. Steps to Solve Problems

2. Graph Algorithms

(a) Represent Graph

(b) Breadth-First-Search (BFS)

© Depth-First-Search (DFS)

Matris
Matris