# CS计算机代考程序代写 algorithm Optimisation Methods

Optimisation Methods

Kathleen Steinh ̈ofel and Tomasz Radzik

6CCS3OME

Complexity Classes, TSP, Approximation

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 1 / 26

NP, NP-Complete, and NP-Hard Problems

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 2 / 26

Problems and Complexity Classes

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 3 / 26

P, NP, NP-hard

One of the Millennium Problems: Click here

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 4 / 26

Methods

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 5 / 26

Hamiltonian Cycles

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 6 / 26

HCs in Complete Graphs

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 7 / 26

Classic TSP

The input a complete, weighted graph G(V,E,w), where set V represents the cities to be visited and E represents the edges between cities, the weights on edges given by w are all positive.

Decision problem: Given a target k, is there a tour which visits each city exactly once and has total weight less than k?

Optimisation problem: Determine the tour which visits each city exactly once and has the minimum possible total weight.

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 8 / 26

Branch-and-Bound

Consider the following instance of a TSP with n = 5 cities.

The example is from ”Foundations of Algorithms” by R. Neapolitan and K. Naimipour (see Reading List).

1

2

3

4

5

1

0

14

4

10

20

2

14

0

7

8

7

3

4

5

0

7

16

4

11

7

9

0

2

5

18

7

17

4

0

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 9 / 26

Branch-and-Bound: Example

Branch-and-Bound is an exhaustive method that evaluates partial configurations and discards those which cannot lead to an optimal solution.

The root is the city we start from. Each leaf represents a complete tour. The number of leaves for a n-city instance of TSP:

(n − 1)(n − 2) · · · 2 = (n − 1)!

Forexample: 4!=1·2·3·4=24,15!≈1.3·1012

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 10 / 26

Branch-and-Bound: Notions

Root: There is a path from the initial partial configuration to any configuration.

Internal Node: Partially specified configuration, which can be extended to a number of complete configurations.

Branching: takes as input a partial configuration P (which is not a complete configuration) and produces partial configurations P1,P2,…,Pk which extend P.

Bounding: A bounding procedure computes for a given partial configuration P, a lower bound on the cost of any configuration which can be obtained by extending configuration P.

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 11 / 26

Branch-and-Bound for TSP

For TSP with 1,2,··· ,n cities:

Partial configuration: a sequence of distinct cities starting at city 1. Formally, a sequence of integers ⟨i1, i2, · · · , ik ⟩, with 1 ≤ k ≤ n − 1 and i1 = 1. All i1, i2, · · · , ik being distinct. Example: ⟨1, 3, 2, 7⟩.

Initial Partial Configuration: ⟨1⟩

Branching: For a partial configuration ⟨i1 , i2 , · · · , ik ⟩ output all partial configurations that extend the sequence by one city, which is not included in the partial configuration: ⟨i1,i2,··· ,ik,x⟩ with

x ̸= ij,1 ≤ j ≤ k.

For example, if n = 6 and the input is ⟨1, 3, 4⟩ then the output is ⟨1,3,4,2⟩, ⟨1,3,4,5⟩ and ⟨1,3,4,6⟩

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 12 / 26

Branch-and-Bound for TSP

Bounding: A procedure that computes for a given partial configuration P, a lower bound on the cost of any configuration which can be obtained by extending configuration P.

An example of a bounding procedure for TSP is:

For a P = ⟨i1, i2, · · · , ik ⟩, with k ≤ n − 2, sum the cost of the partial tour and the minimum outgoing edge from cities not already connected in P.

More formally, the procedure calculates a bound via the following sum CLB (P ) = c (i1 , i2 ) + c (i2 , i3 ) + · · · + c (ik −1 , ik )+

min{c(ik,x) : x ̸∈ {i1,i2,··· ,ik}}+

v̸∈{i1,i3,···,ik} min{c(v,x) : x ̸∈ {i2,i3,··· ,ik,v}}.

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 13 / 26

Observation

If the input is the initial partial configuration ⟨1⟩, then sum, over all cities, the minimum cost of a link outgoing from each city:

n

min{c(i, x) : x ∈ {1, 2, · · · , n} − {i}} i=1

This gives a lower bound on the cost of any TSP tour; in particular, a lower bound on the minimum cost of a TSP tour.

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 14 / 26

Back to our Example

In our example, the bounding procedure on ⟨1⟩ = 21.

We have

c (1, 3) + c (2, 3) + c (3, 1) + c (4, 5) + c (5, 4) = 4 + 7 + 4 + 2 + 4 = 21.

Note: This is a lower bound, i.e., any tour of this TSP instance has a cost greater or equal to 21.

1

2

3

4

5

1

0

14

4

10

20

2

14

0

7

8

7

3

4

5

0

7

16

4

11

7

9

0

2

5

18

7

17

4

0

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 15 / 26

Back to our Example

For a partial tour P = ⟨1, 2, 3⟩ our bounding procedure returns 34.

Sum of the cost of C (P ) = c (1, 2) + c (2, 3) = 14 + 7 = 21 and minimum outgoing edge of 3 not going back min{c (3, 4), c (3, 5)} = 7 and minimum outgoing edges of cities not in P again not going back except for 1: min{c(4, 1), c(4, 5)} + min{c(5, 1), c(5, 4)} = 2 + 4 = 6. Therefore, we have 21 + 7 + 6 = 34.

1

2

3

4

5

1

0

14

4

10

20

2

14

0

7

8

7

3

4

5

0

7

16

4

11

7

9

0

2

5

18

7

17

4

0

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 16 / 26

Branch-and-Bound Pseudocode

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 17 / 26

Symmetric TSP with ∆ineq.

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 18 / 26

Christofides’ Algorithm

For the symmetric TSP (∆ineq.) 2-approximation algorithms were known, e.g. Double Tree, Nearest Addition.

In 1976, Christofides published the following algorithm

1 Find the MST T with distance matrix [di,j].

2 Find the nodes of T with odd degree and find the shortest complete match M in the complete graph consisting of these nodes only. Let G be the multigraph with nodes {1, . . . , n} and edges those in T and M.

3 Find an Eulerian walk of G and an embedded tour.

It finds a 1.5-approximate tour.

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 19 / 26

Example

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 20 / 26

Step 1 – MST

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 21 / 26

Step 2a – Odd Degree Nodes

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 22 / 26

Step 2b – Minimum Matching

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 23 / 26

Step 3a – Eulerian Walk

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 24 / 26

Step 3b – Embedded Tour

Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 25 / 26

Proof

Definition (Theorem)

Christofides’ Algorithm is a 1.5-approximation algorithm.

Proof:

MST and matching can be done in polynomial time.

The constructed tour is feasible.

The cost of the produced tour is at most the cost of the Euler tour, which is cost(T) + cost(M).

We know that cost(T) < OPT.
We can show that cost(M) < OPT/2.
Kathleen Steinh ̈ofel (KCL) Lecture 2 CC,TSP,BB 26 / 26