0:36

It will be convenient for us to assume that the vertices

Â of our graph are numbered with 1, 2, and so on, n.

Â And that the start of the cycle, and also the end of our cycle, is at vertex 1.

Â To give a third example, as usual consider the following graph with five vertices.

Â Already for this small graph it is not so easy to find an optimal cycle.

Â There is, for example, a cycle going from 1 to 2 to 3 to 4 to 5, and

Â going back to 1.

Â Its length, its total length is 15.

Â There is another cycle whose length is 11 and

Â the optimal cycle in this case has length 9.

Â It is shown here on the slide.

Â So know that a brute force search algorithm just goes

Â through all possible (n-1)!

Â cycles.

Â Why (n-1)!?

Â Well, because initially we start at vertex 1.

Â From vertex 1, there are (n-1) choices where to go next.

Â For all of this (n-1) vertices, there are (n-2) choices where to go next, right?

Â (n-2) because we cannot go back to 1 and so on.

Â So it is (n-1) times (n-2) times (n-3) and so on.

Â This gives us (n-1) factorial and this is the running time of an algorithm

Â which is (n-1) factorial, or roughly n factorial, is extremely bad.

Â It is an extremely small, it is even worse than 2 to the n, even slower.

Â So already for n equal to 10 it is already unfeasible,

Â not to say about n equal to 100, for example.

Â So our goal in this lecture is to design an algorithm

Â whose running time is roughly n squared * 2 to the n.

Â It is, of course, an exponential algorithm.

Â But it is at least much better than going through all possible candidate solutions.

Â It is at least better than n factorial.

Â In particular, If we can see the following fraction,

Â n factorial, Divided by 2 to the n times n squared.

Â Then already for n = 100 this fraction

Â is about 10 to the 120.

Â So which means, that already for n equal to 100,

Â the algorithm that we're going to design is going to be 10 to the 100

Â roughly times faster than a brute force search solution.

Â As we've mentioned already, we're going to apply the dynamic programming technique

Â to design a faster than a brute force algorithm for this problem.

Â 3:20

Since we are going to use dynamic programming, this means that instead of

Â solving one large problem, we are going to solve a collection of smaller problems.

Â Usually subproblems that we are going to solve

Â represent just some partial solutions, right?

Â And what is a good partial solution in case we are looking for

Â cycle that visits each vertex exactly once?

Â Well, this is some initial part of a cycle, right?

Â So, when we have some initial part we need to try to extend it somehow, and

Â what information do we need to be able to extend it?

Â Well, at least we need to know the last vertex of this initial part of this cycle.

Â And we also need to know the set of all series or the set of all

Â 4:06

vertices that we already visited, right?

Â So we know, we know the last vertex of our path and

Â we know the vertices that were already visited.

Â And then we can consider all possible extensions of this path and

Â select the best one.

Â This way we will eventually construct an optimal cycle.

Â So let's formalize this idea.

Â For a subset of vertices S containing some vertex i and

Â also the vertex 1, we denote by C(S,i) the length of

Â the shortest path that starts at the vertex 1, ends at a vertex i.

Â And visits all vertices from the set S exactly once,

Â so namely C(S,i) is the length.

Â If I show this path that looks like this, it goes from the vertex one to

Â the vertex side and all the vertices that it visits are from the set S.

Â 5:04

And also it visits all of it's vertices exactly once.

Â In particular, we assign C of the set containing just Vertex 1,

Â and Vertex 1 = 0, because this is just an empty box, right?

Â And for any other S that contains, that is of size of at least 1,

Â we assign C(S, 1) to be equal to +infinity because

Â a path cannot end in the vertex in the vertex 1, okay?

Â Then we need to find a recurrence relation expressing

Â C of Si through solutions for smaller problems.

Â For this considers the following thing, so we need to go from vertex 1 to

Â vertex i and visit all the vertices from the set S and

Â we would like to find a shortest possible such path.

Â Consider the second to last vertex on this path, so this is about vertex j.

Â So the last step in an optimal path which we're going to form is from j to i.

Â What can we say about the following parse?

Â So first of all of of course,

Â it must also be a shortest possible path from the vertex 1 to vertex j.

Â But also we know exactly the set of vertices that it visits.

Â It visits the vertices S minus the vertex i, right.

Â So this exactly all vertices except for the last one.

Â So this allows us to express that is a solution for

Â 7:27

We are almost ready to implement the corresponding dynamic problem,

Â an algorithm so the only technical things

Â is the order in which we are going to solve our SAT problems.

Â This order should satisfy the following simple property.

Â When computing a value the value of C(S, i),

Â we already need the values of all the subproblems.

Â It depends on to be computed, right.

Â All such values are of the following form.

Â It is C(S- {i}, j), okay, so

Â in particular S- i always have size less than the set S.

Â So if we just go through all sub sets in order of increase in size

Â then we are safe.

Â This gives us the following algorithm.

Â So given a graph we first initialize C of ({1},1) to be equal to zero.

Â So this just reflects the fact that if we need to find an optimal path,

Â that starts at vertex 1, visits just the vertex 1, and ends at vertex 1,

Â then this is just an empty path, right?

Â We just say at the vertex 1, so it is equal to 0.

Â Then, we go through all possible sets of vertices denoted by S,

Â and we do this in order of increasing size.

Â So we gradually increase the parameter small s from 2 to n and

Â for all subsets s of size s we do the following.

Â First of all we assign the value +infinity to C of (S,1).

Â Because we need to visit each vertex exactly once.

Â So we just mean that this is an invisible path, it is equal to +infinity.

Â We start at vertex one so we should not end at vertex one, okay?

Â Then for all i that lie in the set S,

Â we need to compute, we need to compute the value of C(S,i).

Â For this we can see there's all possible candidates to

Â be the second to last vertex on an optimal pass.

Â So this is done here, The second to last vertex should

Â 9:46

among the current value and the following value.

Â So this actually says that we first visit all the vertices except for

Â the vertex i and then end in the vertex j.

Â And then we append the edge from j to i.

Â So the total length is increased by

Â the length of this over this last edge.

Â Finally we need to return the best such possible path and

Â we do it by just finding the minimum of the following expression.

Â That is an optimal cycle that starts

Â in the vertex i and ends in vertex 1, I'm sorry.

Â And end in the vertex 1.

Â And is the following, it first visits all

Â the vertices in the graph and then ends in the vertex i.

Â And all these values are stored in

Â the following cells in our table, right?

Â So since we don't the last values in this cycle,

Â we just select the minimum and we also end the last edge inside your cycle.

Â So finally, we compute the result using this expression.

Â There is one technical remark left.

Â In the algorithm we need to somehow iterate over all subsets of our n cities.

Â This can be done as follows, there is a natural one-to-one correspondence between

Â integers from 0 to 2 to the n- 1 and

Â subsets of the set containing integers from zero to n minus one.

Â So, when implementing this algorithm, it is more convenient to consider

Â integers from 0 to n minus 1 instead of integers from 1 to m.

Â Namely this correspondence is defined as follows.

Â If you have an integer k from the following range namely

Â an integer which is at least zero and at most 2 to the n- 1.

Â Then the corresponding set is defined by the positions

Â where this integer has once in binary representation.

Â This is probably easier to show by an example, so

Â consider the following example.

Â Here we consider subsets of three elements of 0, 1, and 2.

Â And for this we consider all integers from 0 to 7.

Â So the binary representation of 0 is 000, right?

Â So this corresponds to an empty set.

Â The binary representation of 1 is 001.

Â So we have 1 in the least significant bit, 0 in the, in the next bit.

Â And 0 in the, in the most significant bit.

Â So this corresponds to just subset containing just an element 0.

Â Or, for example, 3 is represented in binary as As 011.

Â So it has 1 in the least significant bit, and 1 in the next bit.

Â So this corresponds to the subset {0,1}, right?

Â So this way, instead of using c(s,i),

Â we can use just c(k,i), right?

Â Where k is an integer from zero to the n minus 1.

Â The last iterations that we need to do this with

Â is that we need To exclude the element j from the set S.

Â That is, since we are going to represent the set S as an integer,

Â we need to find the corresponding integer.

Â So what does it mean to extract S from the set.

Â This means actually to flip the j-th bit

Â of the corresponding integer from zero to one.

Â And this in turn means, that we are going just to compute the bitwise parity of our

Â current number k, and the number where we have just one in the jth position, right?

Â So we compute the parity of these two numbers,

Â let me probably write it as follows.

Â So assume that this is our number k, and this is the position g where we have 1.

Â And what we need to get is the following, right?

Â So this corresponds to S, and this is S minus the element j.

Â It looks like it follows.

Â