ENGRI 1101 Prelim #1

TSP input

• N locations

• Travel cost d(i, j) >= 0 between each ordered pair of locations i and j

TSP Output

A tour, which is an ordered list of the locations. Each location should be visited once on the tour and then we must return to the starting location at the end.

TSP Objective

Minimize the total cost of the tour, which is the sum of travel costs between consecutive locations on the tour.

Having a ____ isn’t relevant for the TSP input/output!

home city

TSP total cost/path notation

See notebook!

We don’t know an efficient way of finding an optimal solution to the TSP for every possible input which means we must use…

Heuristics

Heuristics

Algorithms that are fast and return a solution always, but not guaranteed to be optimal

Nearest Neighbor

• Travel to the nearest city you haven’t visited

• Repeat until you’ve visited every city and then return to your starting city

Nearest Insertion

• Start with a small tour

• Choose a city closest to any city already in your tour

• Choose a position for that city wherever it adds the least extra distance

Farthest Insertion

• Same insertion process, for each unvisited city, find its distance to the nearest city already in the tour

• Choose the city with the largest distance and insert it wherever it adds the least extra distance

Which heuristics are usually the best and worst performing in the TSP?

Best: Farthest insertion

Worst: Nearest neighbor

Lower bound

• Count how many times you have to transition from city to city = n cities

• Use the n smallest costs to set a lower bound

What is a directed graph?

Set of nodes, set of arcs ~ G = (V, A)

• Nodes = points

• Arcs = Connections between points

In directed graphs, arcs represent a…

one-way street (only travel one direction)

Node sets have what type of order and use _____

Unordered and use curly braces

In the shortest path problem (SPP), cost and length are ____ words.

interchangable

In SPP cost is represented as…

l(i, j) = cost

A path in SPP from node s (the starting point) from node t (the endpoint) in a directed graph is…

a sequence of arcs

SPP Input

• Directed graph G = (V, A) with length l(i, j) >= 0 on each arc (i, j) in A

• Source node s in V

• Destination node t in V

SPP output

s-t path in G, which is an ordered set of arcs. The first arc in the path should start at s, the final arc ends at t, and adjacent arcs are contiguous

SPP objective

Minimize the total path length, which is the sun of lengths of edges in the path

SPP variant

Shortest path tree: find shortest paths from the source node s to every node in the graph

Dijkstra’s algorithm

1. Give the starting node distance 0 and all others infinity

2. Pick the unfinished node with the smallest total distance from the start

3. Calculate distance to chosen node + edge to neighbor. If that eats the neighbors current distance, update its distance

4. Mark the chosen node finished

5. Repeat until all nodes are finished!

6. Output: A shortest path tree, which is a solution to the shortest path problem

Verifying the SPP solution

1. For every arc(i, j) calculate: l(i, j)* = l(i, j) + best(i) - best(j)

2. For each (i, j) in A, check that l(i, j)* >= 0

3. For each arc (i, j) in the path, check that l(i, j)* = 0

4. If this all is true you have computed a correct shortest path!

Undirected graph

Direction doesn’t matter for edges

MSP input

undirected graph G = (V, E) which cost c(i, j) >= 0 on each edge {i, j} in E, this graph should be connected

MSP output

A subset of edges T. The edges in T must form a spanning tree, meaning that they connect the graph and include no cycles

MSP objective

Minimize total cost of T ~ sun of the costs of its edges

Kruskal’s algorithm

1. Add the cheapest edge

2. Keep adding cheap edges without making a cycle (the edges added don’t have to connect with each other)

Prim’s algorithm

1. Start at any node

2. Choose the cheapest node already connected to any point of the tree

3. Repeat step 2 without making a cycle until finished

If an MSP input has n nodes, than an optimal solution has exactly…

n-1 edges

MSP lower bound

Add cost of the n-1 cheapest edges in the graph

Maximum Flow Problem (MF) input

• Directed graph G = (V, A) with a capacity c(i, j) > 0 on each arc(i, j) in A

• Source node s in V

• Destination node t in V

MF output

A flow f which is a value f(i, j) for each arc(i, j) in A:

• Non-negativity

• Doesn’t exceed capacity

• For nodes that aren’t s or t, the total flow coming into i should egual the total flow leaving i

MF objective

Maximize the flow value, which is the total flow leaving node s

Weird & symbol meaning

Absolute min flow you can add along a path

Ford-Fulkerson algorithm

1. Make residual graph

2. Find augmenting path (s to t path in residual graph)

3. Find bottleneck(&) and update flow

4. Rebuild residual graph + repeat!

Easy upper bound for MF

Sum of capacities leaving s

Finding minimum cut

1. Start at s

2. All reachable nodes are put in S

3. Unreachable nodes in T, including t

4. Add capacities of the arrows from S to T (which finds the min cut capacity/the max flow!!!)

What even is a cut?

A cut in a max-flow network is a way to split all the nodes into two groups.