AI: Search Methods for Problem Solving

Professor Deepak Khemani

Department of Computer Science and Engineering
Indian Institute of Technology, Madras
Lecture 01
Finding Optimal TSP Tours

(Refer Slide Time: 00:17)

So, we have been looking at stochastic local search methods, and we did that in the quest
of optimizing the heuristic values and see.

(Refer Slide Time: 00:28)

So, if you do a recap of what we have done so far, we started by path finding in the state
space. So, we said that you are given n Start state and you want to go to a Goal state, and
find the paths to the Goal state. Then, to make search more focused towards the Goal or
more informed, we introduce the notion of heuristic functions so that we could find the
path quickly, essentially.

The reason that we need to do all this is because search spaces tend to grow
exponentially. So, if you had 10 neighbors for the Start node, then for each of those 10,
had another 10 neighbors, then at the next level, they would be 100 candidates, and at the
next level 1,000, and the next level, 10,000 and so on. So, it grows exponentially. And we
have been trying to find ways and means to somehow go towards the Goal faster.

Then, we looked at some algorithms starting with hill climbing, in which what we were
doing was to optimize the value of the heuristic function. So, we converted our original
search problem to an optimization problem where we had looked at various methods for
optimization. So, there is very, it is, the optimization community uses different
terminology.

Sometimes they call, they say evaluation function, sometimes they say objective function.
And, for example genetic algorithms, people say fitness function, but it all, it is all the
same. It is a, it is value that we are trying to optimize, essentially. Now, we come back to
our original problem of searching for solutions, but now we also turn our attention to
searching for optimal solutions.

As we did earlier, we will begin with blind or uninformed search but methods which will
guarantee optimal solutions. And next, we will look at finding optimal solutions quickly,
so which means we will bring in the heuristic function again. And not only do we want to
find the optimal solution, we want to find it as quickly as possible.
(Refer Slide Time: 02:41)

So, what are we doing here? We saw that Breadth First Search find the solution with the
smallest number of moves. So, our quality of solution was measured in the, in the length
of the path. But most of the times when we are working with real problems, all moves are
not of equal costs. There could be different costs. So, now we will introduce the notion of
adding an edge cost to the problem, essentially.

So, if cost of all moves are not the same, an optimal solution may not be the one with the
smallest number of moves. So, for example if you want to go to the railway station and
you have to change two buses, then you can think of this as four moves. Apart from
things like waiting and so on, you get into the bus 1, get off the bus 1 at some point. Then
wait for bus 2, get into that and this thing. So, it is, you can think of it as four moves.

Obviously, there is a shorter solution, which is getting to an auto rickshaw or the taxi and
then get off at the station, which is only two moves. But the first solution is likely to be
cheaper because the cost of every bus ride is going to be cheaper than cost of an auto or a
taxi ride, essentially. So, in that sense, the shortest solutions, the solutions with the least
number of steps may not necessarily be optimal. So, now we will add costs to edges and
look for means to find the least cost solutions.
(Refer Slide Time: 04:14)

The simplest approach would be to use brute force like before. And the following
algorithm is guaranteed to return the optimal solution. The algorithm says, which is
known as the British Museum Procedure, explore the entire search space and return the
optimal solution. Just basically try out everything and then return the optimal solution.

So, algorithm is conceptually simple. It searches the entire search tree, computationally it
is mindlessly expensive, of course. Now Patrick Henry Winston, who was one of the
pioneers of AI, who died a few years ago, he had said that the only way to locate
something in the British Museum is to explore the entire museum, and that is how he
gave this name to this procedure of brute force that look at all possibilities and pick the
best one.

But of course, we have already seen that, we do not want to do something like that. So,
our goal is going to be to search as little of the space as possible while guaranteeing the
optimal solution at the same time.

(Refer Slide Time: 05:26)

We have been following a approach to problem solving, which can be thought of as a

Best First approach to solving problems that given a set of candidates, a search algorithm
has to choose from each candidate is tagged with an estimated cost of the complete
solution. And then we follow this algorithm which says that refine the best looking partial
solution till the best solution is fully refined, essentially.

So, we will continue pursuing this strategy. It is just that the way that we estimate the
cost would change as we go along, essentially. So, the manner in which these estimates
are computed gives rise to different algorithms.
(Refer Slide Time: 06:10)

So, let us look at the traveling salesman problem, which is what we were studying in the
last few sessions, and let us say we have this five cities that you want to cover: Chennai,
Goa, Mumbai, Delhi and Bangalore. And what you have is a distance matrix between any
two cities. So, for example between Chennai and Goa, the distance is 800, essentially,
between Chennai and Bangalore, it is 360, between Mumbai and Delhi, it is 1540 and so
on.

Of course, when you look at the map that I have drawn on the top right, you have a global
perspective, and you can see that roughly speaking, the best tour would be something like
this, essentially. But search algorithms do not have the privilege of looking at the global
perspective. All they have is something like this cost matrix, and then they have to find a
tour, essentially.
(Refer Slide Time: 07:09)

So, let us look at how that can be done. There is an algorithm called Branch & Bound.
Basically, what you do is you create branches and bound them with a cost, essentially.
And this works in what we sometimes call as a refinement space. What do you mean by
refinement space? The initial node in the search space is the set of all possible solutions.
Then, in each step, we partition a set, we pick one set and partition into two smaller sets.

How do we do that? By adding one particular edge to the tour or, or excluding one
particular edge to the tour. So, all tours which have a particular edge, and all tours which
do not have that particular edge. So, we partition the set in this way. And until we pick a
solution that is fully specified. So, if you are left with one solution, then we will
terminate.

So, this follows the strategy that we said that keep refining the, the best candidates till the
best candidate is fully refined. Now, each solution needs to have an estimated cost,
essentially. So, Branch & Bound will refine the solution that has the least estimated cost.
That is going to be our general strategy, essentially. And the process will continue till we
have a complete solution at hand and when no other candidate has a better estimated cost.

So, when we say no other candidate, we mean candidates which are not complete
solutions but may be partial solutions, but they have a higher cost. An optimal solution
can be guaranteed by ensuring that the estimated cost is a lower bound on the actual cost.
So, this is going to be the key to saying that we will always sign the optimal cost is that
you may have partial solutions and we may have costs, estimates of cost of the total
solution including the partial solution.

As long as those estimates are underestimates, which means that the actual cost is higher
than the estimated cost, we will see that we will always guarantee the optimal solution.
So, that is going to be a key criteria in the next few, next couple of algorithms that we
will see.

(Refer Slide Time: 09:17)

We will also see that the higher the estimate, the better it is for performance, essentially.
From the correctness point of view, it does not matter, but from the performance point of
view, the higher the estimate, the better. So, remember that we are talking about lower
bound estimates, that a solution will never be cheaper than it is estimated to be.

So, the estimate is the lower bound on the actual cost. So, thus, if a fully refined solution
is cheaper than the partially refined one, then the latter need not be explored. And that is
where the pruning will come into place, essentially. So, what, what is it we are saying
that a fully defined solution that we have found is cheaper than a partially refined
candidate.
And because the estimate of the partially refined candidate is anyway a lower bounds, its
actual cost will be even higher. So, which is why you can stop refining that partially
refined solution and you can accept the fully refined solution as this final solution. Now,
the simplest lower bound that we can think of is cost equal to 0.

But if you think about this a little bit, you will see that this is not going to do a lot of
pruning because everything, any cost will be higher than that. So, you will end up
exploring the entire space till you find the optimal in this thing. So, the higher the
estimate, the better the pruning, and this is something that you should watch out for. We
will be emphasizing this fact as we go along.

(Refer Slide Time: 10:52)

So, let us apply this to the travelling salesman problem. Let the candidate solutions be
permutations of lists of city names. The initials node in the search space, we have already
set, includes all possible candidates. And then the general idea would be to refine the
cheapest set by specifying a specific segment that include this segment or exclude a
particular segment. And we will see examples.

Which segment to choose? The one with the minimum cost, because we are interested in
minimum cost to us. Adding minimum cost segments will hopefully go towards that. But
we also give need to give some thought to tour cost estimation because we would like
tour costs estimates to be high, as high as possible. We have said that the higher they are,
the, they will be better for me.

So, they should be as high as possible but they should also at the same time be lower
bounds. These two criteria need to be satisfied. So, for tighter estimates, by this we mean
higher estimates, edges that cause three or more segment cycles to be avoided. So,
basically if you include this edge and if you include this edge and if you include the third
edge, then the remaining cities are still to be connected, essentially.

So, even though these edges may be small, the estimate will not be accurate, because all
three cannot be included into the, this thing. We can also exclude an edge that is a third
edge for a node. So, for example, if we have, let us say added these two edges, and we
said that this third edge cannot be added because it is a cycle, we do not even want to add
a third edge here.

And the reason is that in every node, in a, in a tour, there will be only two edges. So, you
will come in from one city and you will go out to the next city. The third edge does not
make sense. So, in our estimates also, we will not include the cost of those edges. So,
when we look at this example, it will become clearer.

But we will see that doing this higher estimates, excluding some edges requires a little bit
more work, and there is eventually going to be a trade-off between the amount of search
that you do and the amount of accuracy that you bring into your estimates.
(Refer Slide Time: 13:23)

So, what should be the lower bound estimates of tours that we are looking at. So,
remember that our strategies is that at the root of the search tree, we have all possible
tours. And then, of course, we may add certain edges. So as we said, based on the
heuristic, we may say that add this edge first because look at towards which, in which
you always go from Chennai to Bangalore because we expect that tour to be a short tour,
essentially.

But how do we get an estimate of this. So, in the root node which contains all possible
tours, the estimate is generated as follows.
(Refer Slide Time: 14:04)

So, this lower bound that we are going to compute now, is going to be the absolute lower
bound for any tour that we have in our set of candidates. And it is, it is computed as
follows, that for each row, add up the smallest two positive entries. So, there are five
rows for Chennai, Goa, Mumbai, Delhi and Bangalore, respectively. And for each row,
we are saying, add the smallest two entries.

So, as you can see in the first row, the smallest entry is 800 and 360. What are we saying?
That the lowest that you can do when you are passing through Chennai is to come from
Goa and go to Bangalore, and that would contribute to the lowest possible cost to the
tour, essentially. So, you do this for every city.

So, this is the simplest way of estimating. It is going to give you an absolute lower bound.
It will not give us high estimates as we said that we do not want to add estimates which
include non-feasible tours. But we will come back to that, essentially. So, the
contribution of Chennai segment should be smallest when it connects to Goa, which is
800 kilometers away, and Bangalore, which is 360 kilometers in the tour.

So, in this manner, we pick the smallest tour costs for each row. And now because what
we have is the sum of, the total number of edges. So, if we have five cities, then the tour
will have five edges. You will go from first city to second, second to third, and third to
fourth and fifth and then back.

Whereas, what we have here are 10 edges because for each city, we have collected two
edges. So, this is for Chennai, this is for Goa, this is for Mumbai, this is for Delhi, and
this is for Bangalore. So, we have 10 edges. And which is why we divide this whole thing
by two to give an estimate of what is the absolute minimum cost of any tour. And that
turns out to be 4,335 kilometers. So, this is just a mechanism to estimate the cost of tour,
and, and to give a lower bound estimate, that it cannot be lower than this.

(Refer Slide Time: 16:36)

Lower bound estimates may not always be good idea because for example, if you were to
do lower bound estimates for this, then for example, you will include these two cities, for
this one, and this city for and these two cities, for this one, and so on and so forth. And
you can see that in this way that we are doing that for every city computes the two closest
cities, the cost of that, these two long edges that you see here, they will never participate
in the lower bound. So, in that sense, they are not necessarily going to be very accurate,
essentially. But it is a way of estimating a lower bound, essentially.
(Refer Slide Time: 17:19)

Then comes the refinement process. We said that refinement means that we will include
some particular known segments into the tour. As segments get fixed in the tour, their
known costs are included in the estimate. As this happens, the estimates become more
accurate. Consider, now, the refinement search space.

The route consists of a node representing all solutions. We can partition, as we said
earlier, this set into two. One including a particular arc and the other excluding that
particular arc. These two sets can then be further refined recursively till each node
describes one tour precisely. And at all points, the sets that we are looking at, we would
want to have lower bound estimates of the tour cost for that particular set of tours.

Remember that each node in the search space is a set of tours. So, we apply the heuristic
of choosing the smallest segment. For example, we might say that first choose the
Chennai-Bangalore segment, which is 360 kilometers.
(Refer Slide Time: 18:25)

Now, we want to estimate the cost of those partial solutions. So, as an example,
supposing we had chosen the Chennai-Mumbai segment, essentially. Then, how do we
change the cost of those tours which always include Chennai and Mumbai? Now, if you
remember, in our original computation, which was for all possible tours, these numbers
were different. This was for Chennai. So, we had said that 360 to Bangalore, and 800 to
Goa.

But now we are saying, I want to include, for some reason, the Chennai-Mumbai
segment. How do we revise the estimate of our cost? So, we basically make sure that this
segment which is Chennai-Mumbai, which has the cost of 1,280 kilometers is included
both for Chennai. So, remember this part is for Chennai and this part is for Mumbai. So,
in both those segments, we include this into the estimate by replacing the other more
expensive tour.

So, we, we replace 800 by 1,280 in the Chennai segment, for example, and now, we have
a new revised estimate which is 4,610 kilometers. Now, for some reason, let us say that
we also want to include the Mumbai-Bangalore segment as well, essentially. So, what
have we done? So, if this is Chennai and if Mumbai is somewhere here, we said that
include this, and then we are saying include the Mumbai-Bangalore segment here.
So, the, so this, so, if you can remember the map of India, this is Chennai, this is
Bangalore, and this is Mumbai, and then there was of course Goa, and I think one more
City, Delhi, which is somewhere on the top, essentially. So, we now we are saying
include Chennai Mumbai and also include Mumbai Bangalore. So, now again, we have to
revise the cost, essentially.

This Mumbai-Bangalore, which is the cost of 1,210, must be included for the Mumbai
computation and also for the Bangalore computation, essentially. So, now, the cost has
gone up further, which is 5,240. But we have said that if you do extra work in estimation,
if you do a bit of reasoning to go along with this simple procedure, then at this point, you
might observe that because we have Chennai-Mumbai and Mumbai-Bangalore, we
cannot have the Chennai-Bangalore segment because that would make a sub tour.

And that is not allowed in the tour. So, that is not a valid candidate, essentially. So, from
this estimate that we have, now we must remove the segment of Chennai-Bangalore,
because if you are going to include Chennai-Mumbai and Mumbai-Bangalore, you cannot
have Chennai-Bangalore in the tour.

(Refer Slide Time: 21:22)

And we get a revised estimate, and this is as follows. So, the Bangalore-Chennai segment
costing 360, contributes twice in the above estimate but we cannot have that because we
cannot have a tool like this: start with Chennai, go to Mumbai, go to Bangalore, come
back to Chennai. That is a sub-tour. We have somehow missed out on Delhi there. So, we
must remove that cost and replace it with the next better costs which are 800.

So, remember that this was 360 here, and this was 360 here, which is the Chennai-
Bangalore segment. We have replaced this with better estimates. So, the better estimates,
they become higher and higher, essentially. Of course, remember that this is one
candidate node. Which is this candidate node in the search space? The node which
includes Mumbai-Bangalore and also includes Mumbai-Chennai.

Of course the other candidate tours are there and they will probably be better. So,
eventually we want to show that our algorithm will find the optimal solution. But what
we did just now was to look at how to estimate lower bound costs for any set of
candidates. And also to try to make those estimates higher or more accurate, essentially,
which is what we did by including particular segments and excluding particular segments
here.

So, tighter estimates, as we have said, should mean more pruning, essentially. Why is
that? Because if you have a partial candidate and you think that it is more expensive, then
you are not going to pursue that, essentially. And you will think that it is more expensive
if its estimate is higher. See, as long as it is a lower bound, the higher the estimates, the
better.
(Refer Slide Time: 23:13)
So, we look at Branch & Bound on the example problem that we have looked at this five
city problems and see how it works. So, we start...

Student: Sir, one doubt. When we were pre, without the inclusion of pre choosing the
cities, when we were calculating the lower bound...

Professor: That is for all possible tours.

Student: Yes. So, there also we have to check for sub-tours, right? If they are being
included. We have to exclude them.

Professor: Yeah, that is what we showed. That if we do not do that computation, then we
will do. But if we now look at segments, so, see here, what is a, what is the this thing, we
have, you are saying from Chennai, the lowest you can do is 800 to Goa and 360 to this
thing. Then from Goa what are we saying? 800 to Chennai and 570 to Bangalore. So,
already, Bangalore has figured twice. That is what you are saying.

From Mumbai, what do we say? 590 to Goa, and 1,210 to Bangalore. So, again, this has
figured. But that is what we would like to do if you are doing more reasoning, that as we
said, that a city should not have three edges coming out of it in the estimate also. So, if
we do that we will get more accurate tours, more like accurate estimates.
So, basically there is going to be a trade-off between how much time you spend doing the
estimate and how much pruning that gives you, essentially. So, it is going to be a trade-
off. Yes, as you said, we can do better estimates than this 4,335 because we cannot have
three edges going into Bangalore as is there in the estimate.

What are the other edges? It is 1,450 to, from Delhi and again, now we have three edges
going to Goa, essentially. And from Bangalore, of course, we have this one and this one,
essentially. So, Goa is figuring four times, essentially. So, clearly, this is not a accurate
estimate, but it is definitely a lower bound. It cannot become lower than that, essentially.

And lower bound estimates, we are interested in, because they will guarantee that when
you pick a solution, it is not going to be worse than the partial candidates. Remember that
this is a partial candidate. There is nothing we have said that. Any, all possible tours,
what is the lower bound. So, an, more accurate lower bound would be to take into fact
that you cannot count Goa four times or Bangalore three times.

In fact, Delhi has not even figured in the computations. That is because Delhi is the city
which is far away, and it kind of is consistent with this. So, just imagine that that this was
Delhi, and all these other cities were not there. Then all those long edges going to Delhi
have not been included in the lower bound estimate.

So, let us simulate our algorithm. Now we have an idea of what the algorithm is that we
start with the set of all possible candidates which we will call as S0, and then we will
either include an edge or exclude an edge, essentially. So, initially, we say include the
Chennai-Bangalore edge. That is represented by this labels CB. And this says not CB. So,
Chennai-Bangalore is included and Chennai-Bangalore is excluded, essentially.

So, if you include Chennai-Bangalore, you can expect that the value will not change
because anyway Chennai-Bangalore figures in the lower bound estimate. But when you
exclude it, all the tours which do not have Chennai-Bangalore, now have a lower bound
estimate of 5,220. And you should try this out in this exercise.
(Refer Slide Time: 27:00)

Then, we add this, we define this tour, which so, what does this represent? This
represents the tours which include Chennai-Bangalore. Now, we are saying, all these
tours will partition into two sets, one which includes Bangalore-Goa, and the one which
excludes Bangalore-Goa. And if you do a little bit of this calculations, so I may or may
not have done this extra reasoning here, but you can see that now we, at this point we
have three candidate in the search space.

This four 4575 represents tours which includes Chennai-Bangalore and Bangalore-Goa.
4770 includes tours which includes Chennai-Bangalore but excludes Bangalore-Goa. And
5220 represents tours which excludes Chennai-Bangalore. So, we have these three nodes.
Which is the smallest one? The smallest one is this one. So, we will refine that. That is
going to be our strategy. We find the best looking candidate till it is fully refined.
(Refer Slide Time: 28:07)

So, that is what happens in the next step. When we, so what do we have here? We have
come down this path, included Chennai-Bangalore, included Bangalore-Goa, and now we
are saying, we will either add the Goa-Mumbai segment or we will exclude the Goa-
Mumbai segment. Now, what happens is once you decide this, in both the cases, there are
no more choices left, essentially. So, if you look at the, this thing on the left here. You
have included three segments. What is that? Bangalore-Chennai, Bangalore-Goa, and
now Goa-Mumbai.

Where can you go from Mumbai? You cannot go to Bangalore because that would make,
make a shorter tour. You cannot, so the only choice left for you is to go to Delhi from
there, essentially, and then from Delhi, the only place left is Chennai. So, by the time you
have fixed those three segments, the Bangalore-Chennai, the Bangalore-Goa and the
Goa-Mumbai segment, your tour is fixed. So, now it is a fully refined solution. And this
cost is the actual costs of that tour, essentially.

Likewise if you exclude Goa-Mumbai, so, this dashed edge here, is saying that you are
excluding that, essentially. Then, if you are going to exclude that, where can you go from
Mumbai? You cannot come back to Bangalore. So, the only place left is Delhi. So, from
Mumbai, you go to Delhi and Mumbai, you are going to Chennai. And this Mumbai-Goa
is not allowed, anyway. So, from Delhi, you will go to Goa.
So, just think about this and you will see that this is, this, these choices of including
Chennai-Bangalore, including Bangalore-Goa and excluding Goa-Mumbai also makes it
a fully refined tour, which is shown in the blue color here, essentially. So, we have found
two tours, now, essentially. These are complete. But they are not the smallest value. What
is the smallest value? The smallest value is this node sitting here, essentially. It has 4770,
essentially.

So, the algorithm is going to say that till you pick a fully refined node, keep searching,
essentially. So, we now refine this node. What does this node represent? This node
represents Chennai-Bangalore and not of Bangalore-Goa. You go from Chennai to
Bangalore but from Bangalore, you do not go to Goa, and that appears to be a cheaper
node. So, let us refine that by adding one more edge.

(Refer Slide Time: 30:53)

So, let us say we add the Goa-Mumbai edge to this candidate also. And then we get these
two candidates. This remains 4770 because that was already included in the earlier tour.
But if you exclude Goa-Mumbai, then it goes up to this thing. So, of course, these are not
fully refined. As you can see, there may be other possibilities. All you have said in this
tour is that you are going to go from Bangalore to Chennai and you are going to go from
Mumbai to Goa.
So from Goa, you could still go to Delhi or you could still go to Bangalore. All those
possibilities still exist. Of course we have said that we are not going to Bangalore, but
from Goa, you could also go to Chennai, for example. Both tours would be valid to us.
So, these are not complete as of now. These are still partial solutions. What are the
values? Again, this seems to be the best one. So, we will refine that.

(Refer Slide Time: 31:53)

And what we get is that we add two segments, one is Goa-Delhi, and the other is to
exclude Goa-Delhi, essentially. Now, you can see that the left one, what is the left one?
The left one says that you include Chennai-Bangalore, you exclude Bangalore-Goa, you
include Goa-Mumbai, and you include Goa-Delhi. It is still not a completely refined tour
because we can have at least two tours, which will have these three segments, and which
excludes one segment, essentially.

But the second tour in which we are excluding Goa-Delhi, becomes completely refined.
And those are the only choices left, essentially. So, we have now found one more tour.
What is this tour? This tour says that you go from Chennai to Bangalore, from Bangalore
to Delhi, from Delhi to Mumbai, from Mumbai to Goa, and Goa, you come back to
Chennai. And its cost is 47, 5,724, essentially.
At this point, search will have to shift its attention to 5220. So, you can see that if this
estimate had been higher than one of these full tours, then we would not have refined it.
But the given estimate is 5220, so it is looking the best, so we need to refine that.
Because that could be actually a cheaper tour. So, of the three tours that we have found,
three complete tours, one is of a cost of 5250, one is the cost of 5830 and the third is of a
cost of 5724. And this one says that the lower bound is 5220. So, it could still be cheaper
than any of those three. So, we need to refine that.

(Refer Slide Time: 33:37)

And when we do that, we find that we still have a tour here whose cost is still 5220
because it has included the Bangalore-Goa segment, which was anyway part of that
estimate. So, 5220 has not changed. So, we need to refine that next.
(Refer Slide Time: 33:58)

And then, when we do that, we add the Goa-Mumbai segment or exclude the Goa-
Mumbai segment. In either case, the cost has become higher than some of the tours that
we have found. So, at this point, what is the next node that our algorithm will pick? It
will pick this node. Why is that? Because that is the lowest estimated cost in this case of a
fully refined candidate. It is also the actual cost.

And the algorithm says that when you pick a fully refined node, then you can terminate.
And when can you pick a fully refined node? When its estimated cost is lower than all the
other causes. So, the algorithm will terminate by picking up this tour. What is this tour?
You are saying that you go from Chennai to Bangalore. From Bangalore, you go to Goa.

From Goa, you go to Mumbai. And then from Mumbai, you go to Delhi, and come back
to Chennai, which is what we had said, looked like a tour, or at least visually when we
were inspecting it. We had said that the tour looks like this, essentially. And this is,
besides, this is a tour that this algorithm has found, essentially.
(Refer Slide Time: 35:15)

So, that is a final search space. Branch & Bound terminates with an optimal tool when the
lower bound estimates of other tours exceed a fully refined tour. So, the fully refined tour
is 5250, and all other numbers that you see on the screen are higher, essentially. It has
located longer tours earlier, as we have seen the nodes in blue, but it has ignored them,
essentially. It has only picked the best tour at this point.

So, that should give us an idea of how Branch & Bound works. We will...

Student: Sir, one doubt. Sir, in case we had an optimum tour, which contained that naught
sign, so how would we read the graph, how would we read the optimum tour. We can
directly that, from...

Professor: The naught sign simply says that do not, do not include that segment. But
when you have a fully refined tour, then we know exactly all the five segments which
must be included. So, for example if you look at the second node, here, it has a negative
segment, which is, do not include this Mumbai-Goa segment. But that is not part of the
tour. The part of the tour is that from Chennai to Bangalore, Bangalore to Goa, Goa to
Delhi, Delhi to Mumbai and then back to Chennai. When the tour is fully refined, we
know exactly which segments are there, essentially.
Student: I mean if we are writing this programmatically, we will create a tree, and if we
have this Phi 830 as our answer, if we just consider that...

Professor: Yeah, but see, I have said, I have kind of jumped a little bit here in the sense
that after you have added, what are the two, we have added only two segments. One is
this Bangalore-Chennai segment, which is here, and the other is the Bangalore-Goa
segment. And then we have said exclude the Goa-Mumbai segment. That is the third
decision we have made.

We have said that, now, what I have said here, is that once you exclude that, you do not
have any choices left. If you had expanded the three, you would have only one choice at
every stage, essentially. And, and in the sense that at this point the set of candidates
includes only one candidate.

So, maybe when you are writing a program, you need to do this little bit of extra
reasoning. Otherwise, you will have to explore that. But we can see that this is what is
going to happen here.

(Refer Slide Time: 37:45)

So, there is a trade-off between search and accurate estimation. The higher the estimated
cost of nodes on open, the later will their turn come. Meanwhile, it is possible that if a
solution node, and by this we mean a completely solved node, with a lower actual cost is
picked, then the algorithm will terminate.

And all those nodes which are higher estimated costs on open, they will never be picked,
essentially, because we have found a fully refined node, which has a lower actual cost.
So, this kind of reinforces the fact that the higher the estimates, the more will the pruning
be. So, those nodes will never get this thing.

This is because the nodes are open have a lower bound estimate. So, we have already said
that our estimates should always be lower bound. So, all those partially refined nodes can
never be better than the fully refined node that we have picked, essentially. And their
actual cost will be higher because the estimates are lower bound estimates.

(Refer Slide Time: 38:55)

So, we will now come back to State Space Search, and see how Branch & Bound
operates in that space.