0:00

We're now ready to write down the Python code from

the algorithm that we've just discussed, okay?

So the method is called dp which stands for the dynamic programming, of course.

So its input is just a graph, and the first thing is that we store

in the variable m, the number of nodes in our graph.

In the second line, we create a two dimensional table.

So its rows are in the set with integers from 0 to n minus one, okay?

Its columns are in the set with all numbers from 0 to 2 to the n minus 1.

Why is that?

Well, this notation 1 shifted to the m positions.

To the left is exactly 2 to the n.

So what happens in this pile that we create a table like this.

So for example for m equal to 3 ,it is going to look as follows.

So its rows are in the set with 0, 1, and 2.

Its columns are in the set with numbers starting from 0 and

ending with 7, okay?

So initially it is filled in with plus infinity.

In Python, there is a convenient way of using infinity, so

it is just float of inf.

So it is a number which is greater than any other number.

Okay, so initially we have infinities in all the cells of our table.

And how are we going to use this table?

Well, in a position, so this is table T.

In a cell T of ik,

we are going to store the value of the function c of

is where s is the set corresponding to the integer k.

So recalls that s is the set of all elements that have non zero bits

in the decimal, in the binary, I'm sorry, representation of k, okay?

Okay, in the next line we have assigned when we reduce 0 to

the cell T of 01, mainly for this particular cell.

So we put 0 in this cell.

So what does it mean?

This actually just reflects the fact that c of,

2:33

0 and the set consistent of just

the element 0 is equal to 0.

So the set consistent of just an element 0.

So recall that it's the corresponding number is 1.

Because this is just a number whose binary representation

has zeros everywhere except in the zero's position, right?

And this is one in decimal representation.

And this just reflects the fact that if we need to start in

the node 0 and then to visit only the node 0 and no other nodes,

then we do not need to pay anything, so it just equal to 0, okay?

3:23

Then what is happening in the next line is that with range,

sort of all set through all numbers s starting from 0 and

ending with 2 to the n minus 1.

So once again, this is just 2 to the n.

And recall that in Python, the right boundary of the range is excluded, right?

So we range starting from 0 to 2 to the n minus 1, okay?

So at each iteration of this loop,

we are going to compute c( (i,s) for

a set s which is specified by small s,

by small variable s, okay?

So first of all, we need to compute it only when the size of s

is greater than 1 and only when s itself contains the element 0, okay?

And this says exactly what we checked in this line.

So this expression actually computes the sum

of all the bit of the numbers, okay?

So we write down s in binary, and

then again we use this matrix in order to compute the sun of all its bits.

So we range the variable j

here is used to range through all possible bit positions in s.

So j ranges from 0 to n minus 1.

For each particular j, we do the following.

We just shift s to j positions to the right.

Mainly we can forget the last position.

So after this shift to the right, the j bit

becomes the least significant bit of the resulting number, okay?

Then what this separation does, so this is a bitwise end or

bitwise conjunction with 1.

It actually computes the bitwise conjunction with a number with

the number 1.

So what happens is that we take the number s which looks

5:37

Well, at least, for example, and assume that this one is the j's position.

Then when we shifted to j positions to the right, when we apply this sum, okay?

So what we get is a number like 101.

So this number, these bits disappear.

The j's position is now the least significant bit, okay?

And then we can choose a bitwise end with the following number.

It is just 1 so it is just 001.

And when we compute the bitwise n, we essentially replace all the bits with 0,

except for the last one, so what we get is 001.

So all the bits here are going to be equal to 0.

And the only bit that has chances to be non-zero is the last one.

So this actually just checks whether the j bit of s is equal to 1.

This is exactly what we need.

And then we compute the sum of all such bits over all possible bit positions.

So we just compute the size of the set s capital, right, okay?

So at this point we will check this condition and

then we also check whether 0 is present in that.

So for this we'll just check whether

s bitwise n with 1 is equal to 1.

So we just check whether the last bit of s is equal to 1.

So if the sum is smaller than 1 or if 0 is not in s, we just continue.

We are not interested in such a subset s, right?

7:24

If on the other hand, the size of s is smaller than,

is greater than 1, I'm sorry, normally if 0 is present in s, we continue.

Then we arrange them in another for loop, i ranges from 1 to 10.

So we are not interested in i equal to 0 and for

this reason, the range here is from 1 to 10.

Then first we check if i is not present in s, here if i is not present And

that's, we just continue, we're not interested in such sets, right?

Recall that where i should belong to s, then we start another for loop.

So here j ranges from 0 to n minus 1.

And the n we check, and so we do not need to do anything in

j=1 Or if j is not present and that's right.

So we just continue the for loop in this case.

So when we reach this position,

we know that s is a set satisfying these two properties.

So s is a set of size at least 1, side is at i and

is an as 0 is an as and j is not equal to 5.

So j is a good candidate to be the second to last node

on an optimal plus that starts at 0 ends at i and

visits all the nodes from the cell s.

And at this point we just try to improve the current values toward Tis, okay?

Namely, we check whether this this expression is smaller than

the current value of Tis.

And if it is smaller, then we store it in Tis.

And recall that this is known as c (j) and s- i right?

Because this is t of j and

this is exactly s with the element i removed from the set s.

And what we need to add to this expression is the weight of the edge

from i to j, okay?

9:39

Namely, for directed graphs, actually, we need to add an edge from j to i.

So at this point we assume that our graph is undirected.

Okay, so this way we fill in all the table.

We've replaced some of the plus infinities with actual values and now we graph.

And then what remains to be done is to return the actual result.

And the result in this case can be computed as follows, so

this is just the last line of our code.

So recall that our function c of ys,

it always computes as the length of some part.

Starts in a node 0, ends in a high and visited all the nodes.

So first of all, we need to reset all the nodes.

And the second thing is that we need to return back to the initial values.

So we check all the various t (i) where i ranges

through all possible values from 1 to n.

So i ranges through all possible n vertices of our cycle.

And here we use the set that contains all the elements.

We need a number which has 1 at every position, okay?

And to compute such a number, we just take 2 to the n and subtract 1.

This is exactly the number which has 1 at 0 position,

1 at first position, 1 at second position and so on.

So this is just a number whose binary representation is the following one, okay?

So we check all such values and for every such part,

we add just the last weight of the edge from 0 to i, okay?

So once again, this is a path, this is an optimal weight of a path that starts at 0,

visits all the nodes at the n and then at the node, I'm sorry,

and then we need to add one more edge going from i to 0.

And this is exactly what is done here at the last step, okay?

So this is the main message picture but

this just reflects the fact that this is a non trivial algorithm.

And also, its implementation here uses some non standard probably not so

standard tricks.

But let me finally summarize, so the running time of this algorithm is n

squared times 2 to the n because we actually have three nested loops.

The outer loop ranges through all sort of small s

going from 0 to 2 to the n minus 1.

So for this reason, we have 2 to the n term.

Then i ranges from one to n and j ranges from,

also from 0 to n, and that's why we have n squared term.

So it is my much better than factorial,

so n squared to the n grows slower than n factorial.

So sometimes this approach is better than range and bond, but sometimes range and

bond is better than dynamic programming.

So 2 to the n, and

this approach is definitely faster than going through all possible permutations

because going through all possible permutations is n factorial.

But still unfortunately, this approach is too slow already for n = 20.

Okay, so this approach just allows us to solve and practice instances

consisting of, say, 15 nodes depending on the actual implementation.

So while going through all permutations is too slow over the full 4 equal to 15,

this one is okay for n equal to, say, 15 or 14, okay?

So this is faster than n factorial, but for practical applications,

this is unfortunately still too slow.

So in practice, much more often, the branching bond

technique is used with some smart usage of heuristics.