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.