1
00:00:00,220 --> 00:00:03,930
Welcome back this is Discrete 
Optimization Local Search part six. 

2
00:00:03,930 --> 00:00:08,250
Okay so what we're going to do today? 
Start talking about this topic of 

3
00:00:08,250 --> 00:00:12,079
escaping local minima. 
And we'll introduce a very important 

4
00:00:12,079 --> 00:00:15,076
notion which is connectivity. 
And talk a little bit about various 

5
00:00:15,076 --> 00:00:18,360
neighborhoods and how they relate to 
this, this notion. 

6
00:00:18,360 --> 00:00:21,770
the big goal here is that we are setting 
the stage for. 

7
00:00:21,770 --> 00:00:25,128
Introducing techniques that will allow us 
to actually find higher-quality solution, 

8
00:00:25,128 --> 00:00:28,256
not just producing, you know, move, that 
are improving all the time, but allowing 

9
00:00:28,256 --> 00:00:33,494
the search to do more interesting things. 
But a requirement, you know, in general, 

10
00:00:33,494 --> 00:00:37,800
is that you need some property of you 
neighborhood to do good things, okay? 

11
00:00:37,800 --> 00:00:41,200
So, remember, you know what we did, that 
the guarantee that we have is we apply, 

12
00:00:41,200 --> 00:00:44,720
you know, greedy moves inside a 
neighborhood. 

13
00:00:44,720 --> 00:00:48,319
Is that when we complete the search we 
are guaranteed that the value of the 

14
00:00:48,319 --> 00:00:52,020
configuration that we find is a local 
minimum. 

15
00:00:52,020 --> 00:00:55,220
Okay, so which basically means that if 
you are that position in that space, if 

16
00:00:55,220 --> 00:00:59,060
you look around there is no place you can 
go which is better. 

17
00:00:59,060 --> 00:01:01,530
That's what it means to be a local 
optimum, okay? 

18
00:01:01,530 --> 00:01:03,720
You can move to a place which is better, 
okay? 

19
00:01:03,720 --> 00:01:06,840
But that doesn't guarantee that this 
place is actually good in the grand 

20
00:01:06,840 --> 00:01:10,145
scheme of things. 
They could, there may be something really 

21
00:01:10,145 --> 00:01:13,620
good somewhere else, and you don't know 
how to get to it, okay? 

22
00:01:13,620 --> 00:01:18,093
So, we have no guarantees for optimality, 
and therefore, in practice escaping these 

23
00:01:18,093 --> 00:01:23,320
local minima of, of poor quality is a 
very important issue. 

24
00:01:23,320 --> 00:01:25,466
And once again, the next lecture will 
show you two really interesting 

25
00:01:25,466 --> 00:01:28,783
techniques to do that. 
What we are doing today is setting the 

26
00:01:28,783 --> 00:01:32,282
stage for that, okay? 
So this is a beautiful picture done by 

27
00:01:32,282 --> 00:01:34,982
Carlton, right? 
So you see this is kind of the 

28
00:01:34,982 --> 00:01:38,320
neighborhood, the entire regions of the 
space, okay? 

29
00:01:38,320 --> 00:01:41,910
So, so, so you see you know, in this 
particular case, you know. 

30
00:01:41,910 --> 00:01:46,030
Basically, this neighborhood is colored 
into you know, cold and hot region. 

31
00:01:46,030 --> 00:01:49,290
And hot means high quality, cold means 
terrible, right? 

32
00:01:49,290 --> 00:01:51,660
And so, local search dots for you a 
point. 

33
00:01:51,660 --> 00:01:53,570
You define the neighborhood of that 
point. 

34
00:01:53,570 --> 00:01:56,706
And then, what we have done so far is 
taken a direction which is improving, you 

35
00:01:56,706 --> 00:02:01,340
know, which is improving the, the move. 
And so we follow this, and then we can 

36
00:02:01,340 --> 00:02:04,540
continue finding a path. 
Oops, and hopefully. 

37
00:02:04,540 --> 00:02:09,690
We, you know, we get to a good region of 
the space, okay? 

38
00:02:09,690 --> 00:02:12,190
So that's what we have been doing so far, 
okay? 

39
00:02:12,190 --> 00:02:16,882
Now, the, the landscape of the objective 
function, okay, can be complex like this 

40
00:02:16,882 --> 00:02:20,558
one, right? 
So, so what you see here is the various, 

41
00:02:20,558 --> 00:02:24,550
the quality of the solutions, and we are 
minimizing, okay? 

42
00:02:24,550 --> 00:02:28,520
So this is essentially all a possible 
solution and this is the quality. 

43
00:02:28,520 --> 00:02:32,282
And what you see here is there is various 
local minimarts in that popular place, 

44
00:02:32,282 --> 00:02:35,194
right? 
So this is a local minimart this is also 

45
00:02:35,194 --> 00:02:39,410
a local minimart and you know this one is 
actually pretty interesting. 

46
00:02:39,410 --> 00:02:42,094
This is the global Minimum. 
Okay, so that's the global minimum in 

47
00:02:42,094 --> 00:02:45,110
this particular case. 
So we want to get there but the search 

48
00:02:45,110 --> 00:02:49,270
that we have seen so far are not going to 
get you there, right? 

49
00:02:49,270 --> 00:02:52,900
Now, one of the things that you really 
don't want to happen is this, okay? 

50
00:02:52,900 --> 00:02:56,740
So you can't define your problem, okay, 
in such a way that it's not connected, 

51
00:02:56,740 --> 00:03:01,470
which means that if you start from that 
particular point. 

52
00:03:01,470 --> 00:03:05,161
You can move inside that region right. 
And find a good point in that region 

53
00:03:05,161 --> 00:03:08,248
which is here. 
But you have no way to actually get 

54
00:03:08,248 --> 00:03:10,468
there. 
There is no move that will get you there 

55
00:03:10,468 --> 00:03:13,810
and that's terrible. 
The entire region here which is where the 

56
00:03:13,810 --> 00:03:17,514
good things are is not accessible if you 
start from there. 

57
00:03:17,514 --> 00:03:21,110
Okay, so we don't want that. 
This is not good okay? 

58
00:03:21,110 --> 00:03:24,570
So we have no way of moving from one side 
of the neighbor to the other one. 

59
00:03:24,570 --> 00:03:27,962
And so we want to avoid that and the 
connectivity requirements that I'm going 

60
00:03:27,962 --> 00:03:32,304
to talk about is exactly avoiding this. 
Okay, so this is a definition but 

61
00:03:32,304 --> 00:03:35,684
essentially what it means is that you 
want to be able go from any configuration 

62
00:03:35,684 --> 00:03:40,072
to at least one optimal solution. 
Okay, so in a sense you're going to say 

63
00:03:40,072 --> 00:03:43,608
that neighborhood N, and remember that a 
neighborhood is something which given a 

64
00:03:43,608 --> 00:03:48,940
configuration is going to give you a set 
of configuration where you can go, okay. 

65
00:03:48,940 --> 00:03:52,600
So neighborhood N is going to be 
connected if from every configuration S, 

66
00:03:52,600 --> 00:03:56,588
anywhere, okay? 
So there an optimal solution O that you 

67
00:03:56,588 --> 00:04:00,450
can reach by taking local move and what 
is a local move? 

68
00:04:00,450 --> 00:04:02,930
Well you start from s, OK that state at 
zero. 

69
00:04:02,930 --> 00:04:06,350
Okay, and then you can take a local move 
to go to a s1, then to s1, to s3 and so 

70
00:04:06,350 --> 00:04:09,542
on up to s n which is the optimal 
solution that you are looking for and 

71
00:04:09,542 --> 00:04:16,080
everyone of these configurations can be 
accessed by your local move. 

72
00:04:16,080 --> 00:04:20,960
Which basically means that SI is in the 
neighborhood of SI minus 1, right? 

73
00:04:20,960 --> 00:04:24,535
So this is the definition of 
connectivity, intuitively it's very 

74
00:04:24,535 --> 00:04:27,066
simple. 
It basically means that you can apply 

75
00:04:27,066 --> 00:04:30,010
local move from any configuration to get 
to the optimum. 

76
00:04:30,010 --> 00:04:32,400
It doesn't mean that you will get there 
right? 

77
00:04:32,400 --> 00:04:36,010
It must means that there is a path, okay? 
Afterwards we need to find that path. 

78
00:04:36,010 --> 00:04:41,490
But what we know is that for sure there 
is one path to an optimum solution, okay? 

79
00:04:41,490 --> 00:04:44,962
Now, connectivity doesn't guarantee 
optimality as I just tell, told you, 

80
00:04:44,962 --> 00:04:48,098
right? 
Because so far, our local search has been 

81
00:04:48,098 --> 00:04:51,207
greedy, okay? 
So, what happens when you are greedy, 

82
00:04:51,207 --> 00:04:53,469
okay? 
When you are greedy, let's say this is 

83
00:04:53,469 --> 00:04:55,948
the starting point. 
When you are there, you're going to prove 

84
00:04:55,948 --> 00:04:59,660
you're not going to, you're going to take 
move that are basically improving, okay? 

85
00:04:59,660 --> 00:05:03,470
So, if you take move, that are improving, 
you're going to get to this local minima. 

86
00:05:03,470 --> 00:05:06,179
Okay, so you think, another point over 
there, beautiful point, you go down, 

87
00:05:06,179 --> 00:05:09,560
drop, that's where you get. 
You don't get here, right. 

88
00:05:09,560 --> 00:05:12,540
Because if you try to improve all the 
time, you're not going to get there. 

89
00:05:12,540 --> 00:05:15,900
You will have to go up the hill and then 
go down, right? 

90
00:05:15,900 --> 00:05:18,130
Which is not something that we have been 
able to do so far. 

91
00:05:18,130 --> 00:05:20,734
And obviously, you know, you have all 
these points here that are basically 

92
00:05:20,734 --> 00:05:25,050
bringing, oops, I want to show you that, 
because they are so beautiful, right. 

93
00:05:25,050 --> 00:05:28,263
So that are going to all these places, 
but they don't get to the global, to the 

94
00:05:28,263 --> 00:05:32,420
global optimum. 
Okay, so in a sense, connectivity doesn't 

95
00:05:32,420 --> 00:05:37,520
guarantee optimality, but it's still a 
very good property to have. 

96
00:05:37,520 --> 00:05:40,340
Because once we entry some of the 
techniques that we'll see, you know, in 

97
00:05:40,340 --> 00:05:43,583
the next lecture, you know, in connected 
neighbourhoods you may have more hope and 

98
00:05:43,583 --> 00:05:49,520
actually in some cases guarantees to get. 
two of the actual optimal solution. 

99
00:05:49,520 --> 00:05:54,002
So, what you see here is graph coloring. 
Remember, we had this beautiful problem 

100
00:05:54,002 --> 00:05:58,097
where you would color these, all these 
vertices, such that two adjacent nodes 

101
00:05:58,097 --> 00:06:03,870
were colored by had to colored by a 
different color. 

102
00:06:03,870 --> 00:06:07,350
Okay so and the neighborhood that we 
chose was very simple, right? 

103
00:06:07,350 --> 00:06:11,026
It was changing the color of a note. 
And usually that neighborhood is 

104
00:06:11,026 --> 00:06:14,354
connected, and I'm going to give you a 
simple algorithm, and this is actually 

105
00:06:14,354 --> 00:06:17,734
very interesting because we are heating 
like hell, but this is what you do when 

106
00:06:17,734 --> 00:06:22,240
you want a sure that something is 
connected, right? 

107
00:06:22,240 --> 00:06:24,680
So what you have to do is you start from 
the configuration. 

108
00:06:24,680 --> 00:06:29,230
And you have to show a path, you know, 
that indicates that you know, that brings 

109
00:06:29,230 --> 00:06:35,140
you to the optimal solution. 
But, we can do a really nice assumption. 

110
00:06:35,140 --> 00:06:38,227
We can actually postulate that we know 
the optimal solution, so if I know the 

111
00:06:38,227 --> 00:06:41,608
optimal solution and I'm in a particular 
configuration, I can design a very simple 

112
00:06:41,608 --> 00:06:46,190
algorithm to get to the optimal solution. 
What do I know? 

113
00:06:46,190 --> 00:06:50,034
I look at every note and if that note 
okay, doesn't have the right value that 

114
00:06:50,034 --> 00:06:54,064
means that it's value is different from 
the value in the configuration simply 

115
00:06:54,064 --> 00:07:00,440
assign it's value which each value which 
is in the optimal solution. 

116
00:07:00,440 --> 00:07:04,529
So I do that for all the notes okay, 
this, they are all legal, right? 

117
00:07:04,529 --> 00:07:07,610
And then essentially I get to the 
ultimate solution. 

118
00:07:07,610 --> 00:07:10,461
So, this is very easy, right? 
So, but all the connectivity groove are 

119
00:07:10,461 --> 00:07:13,184
like that. 
So, you, you suppose that, you basically 

120
00:07:13,184 --> 00:07:17,140
assume that you have the objective, the 
optimal solution. 

121
00:07:17,140 --> 00:07:19,020
And then you have a particular 
configuration. 

122
00:07:19,020 --> 00:07:22,870
And you show you can actually get there. 
No, this is a very simple one, right? 

123
00:07:22,870 --> 00:07:26,698
Some of them are very complicated, okay, 
but this gives you the essence of these 

124
00:07:26,698 --> 00:07:30,600
kinds of proofs, okay? 
Now, remember car sequencing, okay? 

125
00:07:30,600 --> 00:07:33,142
So car sequencing once again we were 
scheduling these cars on the assembly 

126
00:07:33,142 --> 00:07:35,680
line. 
The production unit that is to put these 

127
00:07:35,680 --> 00:07:37,760
options while the cars were moving, 
right? 

128
00:07:37,760 --> 00:07:40,932
And we had to satisfy the capacity 
constraints on this production unit to 

129
00:07:40,932 --> 00:07:46,010
make sure that we could put the options. 
On the cars, right? 

130
00:07:46,010 --> 00:07:49,260
So, what we designed was this beautiful 
neighborhood, right? 

131
00:07:49,260 --> 00:07:53,450
where we would basically look at the cars 
and swap them, okay? 

132
00:07:53,450 --> 00:07:55,730
And here you see the options of the 
various car, okay? 

133
00:07:55,730 --> 00:08:00,800
So we have a swap neighborhood And this 
swap neighborhood is connected, okay? 

134
00:08:00,800 --> 00:08:05,096
And why, let's look at the algorithm. 
So actually, let's go back and look at 

135
00:08:05,096 --> 00:08:08,400
the sequence right? 
So we can take this sequence and look at 

136
00:08:08,400 --> 00:08:13,430
the values and either you have the right 
type of car there or you don't, okay? 

137
00:08:13,430 --> 00:08:15,940
If you don't have the right type of car, 
what are you going to do? 

138
00:08:15,940 --> 00:08:19,350
Well, there is your type of car somewhere 
inside the sequence. 

139
00:08:19,350 --> 00:08:22,340
You can swap them, and now what do you 
have? 

140
00:08:22,340 --> 00:08:25,670
Well, the first slot is right. 
You move to the next one, okay? 

141
00:08:25,670 --> 00:08:28,450
The next one you say, well, you look. 
Is it right, or not? 

142
00:08:28,450 --> 00:08:30,380
Is it the value that you have in the 
optimum solution? 

143
00:08:30,380 --> 00:08:34,152
If it is fine, you move to the third one. 
If it's not, you look for the right type 

144
00:08:34,152 --> 00:08:36,940
of car, and you solve these two thing, 
okay? 

145
00:08:36,940 --> 00:08:40,460
And so you can continue doing that, and 
that's how you show connectivity, okay? 

146
00:08:40,460 --> 00:08:42,340
So, once again, that's what you see 
there. 

147
00:08:42,340 --> 00:08:45,838
You have an algorithm which iterates from 
you know, the first to the last load of 

148
00:08:45,838 --> 00:08:50,076
the assembly line. 
Then you look essentially it's the value 

149
00:08:50,076 --> 00:08:53,793
for the configuration s, you know, s i is 
the same as the value of that part, of 

150
00:08:53,793 --> 00:08:59,440
the slot you know, of position i in the 
ultimate solution that's o i. 

151
00:08:59,440 --> 00:09:03,833
If they are different, what you do is you 
look for a particular config. 

152
00:09:03,833 --> 00:09:07,538
[SOUND] A particular configuration 
inside, a particle type of car inside the 

153
00:09:07,538 --> 00:09:11,186
sequence S, you know, and, and further 
away, obviously, which is of the type, 

154
00:09:11,186 --> 00:09:16,570
the same time as the value which is 
inside the automobile solution. 

155
00:09:16,570 --> 00:09:19,142
And you swap these two things. 
And you continue like that, and 

156
00:09:19,142 --> 00:09:21,872
obviously, you know that you will find 
one, right, because it's in the optimum 

157
00:09:21,872 --> 00:09:25,201
solution. 
And therefore, you, you solve all these 

158
00:09:25,201 --> 00:09:28,080
things and you get an observable solution 
at the end. 

159
00:09:28,080 --> 00:09:31,984
So what I'm showing you here is a very, 
is essentially that by, by, by doing 

160
00:09:31,984 --> 00:09:38,040
swaps, you will always get to the optimal 
solution by a sequence of move. 

161
00:09:38,040 --> 00:09:41,062
Now once again, I want to repeat this. 
It doesn't mean that your algorithm is 

162
00:09:41,062 --> 00:09:44,470
going to find that sequence, right? 
Because we are always trying to find 

163
00:09:44,470 --> 00:09:47,980
improving moves and things like this. 
We would have to do other things. 

164
00:09:47,980 --> 00:09:51,584
So in practice, some of these steps here 
huh, may be degrading tremendously the 

165
00:09:51,584 --> 00:09:54,978
quality of your solution. 
At that's what is the challenge in local 

166
00:09:54,978 --> 00:09:57,905
search, right? 
So, let me, let me look at something 

167
00:09:57,905 --> 00:10:00,160
which is a little bit more complex, 
right. 

168
00:10:00,160 --> 00:10:02,540
So this is the traveling salesman 
problem. 

169
00:10:02,540 --> 00:10:07,750
Remember We had all these cities that we 
had to visit exactly once, okay. 

170
00:10:07,750 --> 00:10:11,820
And trying to minimze the total distance. 
And we introduce this simple 

171
00:10:11,820 --> 00:10:15,494
neighborhood, that's one of the simplest 
that [UNKNOWN] 2-OPT. 

172
00:10:15,494 --> 00:10:20,254
Now remember 2-OPT was basically taking 
two edges and replacing them by two other 

173
00:10:20,254 --> 00:10:23,516
edges. 
And the question that you may be asking 

174
00:10:23,516 --> 00:10:27,110
yourself, that is this neighborhood 
connected, okay? 

175
00:10:27,110 --> 00:10:31,352
So, very simple question. 
Because it has only two possible answer, 

176
00:10:31,352 --> 00:10:33,030
right? 
Yes or no? 

177
00:10:33,030 --> 00:10:35,610
So, think about it. 
Is it connected or not? 

178
00:10:36,810 --> 00:10:39,590
So, to actually find that out, so look at 
this thing, okay? 

179
00:10:39,590 --> 00:10:43,500
So, look at this particular tour. 
Is there another way to view this? 

180
00:10:43,500 --> 00:10:46,425
Well first let's, let's start numbering 
these guys so we have all the vertices 

181
00:10:46,425 --> 00:10:50,670
and the name of these vertices. 
Okay, and know a two, you see the two. 

182
00:10:50,670 --> 00:10:54,254
You know, starting from one, moving to 
five, then to nine, then to ten, then to 

183
00:10:54,254 --> 00:10:58,482
six, three and so on. 
Okay, so when you look at this tool, this 

184
00:10:58,482 --> 00:11:02,790
tool is really like a sequence, right? 
So you see the sequence here. 

185
00:11:02,790 --> 00:11:07,040
You know, one, five, nine, ten, three and 
so on, okay? 

186
00:11:07,040 --> 00:11:11,180
So basically the two here can be viewed 
as a sequence Right? 

187
00:11:11,180 --> 00:11:15,668
Now remember, what you know, two opt does 
is removing two edges and replacing it by 

188
00:11:15,668 --> 00:11:19,880
two other edges that you see over there, 
right? 

189
00:11:19,880 --> 00:11:23,845
So I have a sequence here and you know, 
what is going to be my sequence for this 

190
00:11:23,845 --> 00:11:28,042
thing, okay? 
So, essentially, what you know is that in 

191
00:11:28,042 --> 00:11:32,734
this two, right, so you were basically 
going to to, to, to six and, and six was 

192
00:11:32,734 --> 00:11:38,110
going to three, right? 
So what we going to do is remove this and 

193
00:11:38,110 --> 00:11:42,199
replace it by an edge to seven. 
And then we going to revert essentially 

194
00:11:42,199 --> 00:11:45,390
all these edges that you see on that 
right side. 

195
00:11:45,390 --> 00:11:48,620
And then connect that with an edge going 
from three to two. 

196
00:11:48,620 --> 00:11:51,200
So, we are basically taking these things, 
okay? 

197
00:11:51,200 --> 00:11:56,310
So, the edges that we are removing in the 
edges going from six to three, okay? 

198
00:11:56,310 --> 00:11:59,326
So this is the edge that you see 
somewhere here okay, and then we have to 

199
00:11:59,326 --> 00:12:03,130
revert that so we are basically reverting 
the sequence. 

200
00:12:03,130 --> 00:12:06,810
So what you really get here is that 
particular sequence there. 

201
00:12:06,810 --> 00:12:10,629
So you see you see the original sequence 
over there and you see the sequence which 

202
00:12:10,629 --> 00:12:14,334
is here, which is essentially the same 
sequence we have here except for we have 

203
00:12:14,334 --> 00:12:19,480
revert All the, the ordering. 
We, we basically reverse that particular 

204
00:12:19,480 --> 00:12:22,340
sequence, right? 
And that's what you see over there, okay? 

205
00:12:22,340 --> 00:12:26,183
So essentially what I'm telling you is 
that 2-opt can be view on sequence and 

206
00:12:26,183 --> 00:12:32,230
you isolate a sub-sequence here and what 
you do is you basically reverse it. 

207
00:12:32,230 --> 00:12:35,190
But keep it the same position, but 
reverse it, okay? 

208
00:12:35,190 --> 00:12:38,510
Now, instead of moving from six to three, 
you move to six to seven. 

209
00:12:38,510 --> 00:12:41,240
And then to 11 and eight and four and so 
on. 

210
00:12:41,240 --> 00:12:43,190
And that's what you see over there, 
right? 

211
00:12:43,190 --> 00:12:48,069
So essentially, what you do is you select 
a six sequence, and you reverse it, okay? 

212
00:12:48,069 --> 00:12:51,555
Now, I'm asking you the question. 
Is this neighborhood connected or not? 

213
00:12:51,555 --> 00:12:56,460
Okay, well, we can use a very simple 
algorithm again, right? 

214
00:12:56,460 --> 00:12:59,596
If we know the ultimate solution, okay, 
and we can posulte that we know it, and 

215
00:12:59,596 --> 00:13:03,150
we have a configuration right now, what 
are we going to do? 

216
00:13:03,150 --> 00:13:06,050
Now, assume that, for instance, this guy 
is the optimum solution, okay? 

217
00:13:06,050 --> 00:13:07,895
Which is probably not the case, but never 
mind. 

218
00:13:07,895 --> 00:13:11,738
Okay, but if we look at this thing, what 
we're going to say, okay, so you know, we 

219
00:13:11,738 --> 00:13:17,950
have 1, 5, 9, 10, 6 and this is the same 
in this supposedly alternate solution. 

220
00:13:17,950 --> 00:13:20,640
But then we see here that there is a 
different between these two guys, right? 

221
00:13:20,640 --> 00:13:23,344
There is a difference, okay? 
So there is one that is starting at 

222
00:13:23,344 --> 00:13:26,476
three, okay. 
This subsequence is starting with three 

223
00:13:26,476 --> 00:13:29,870
and that one is starting at seven, okay? 
So, what do we do? 

224
00:13:29,870 --> 00:13:32,440
Well, we say okay, so I'm going to select 
a move by what? 

225
00:13:32,440 --> 00:13:35,360
Well, I want a seven, right? 
So, this is what I want, okay? 

226
00:13:35,360 --> 00:13:38,220
And I have a three, so I'm going to look 
until I find a seven and then I'm 

227
00:13:38,220 --> 00:13:41,080
going to apply a two opt and that 2-OPT 
is basically going to revert that 

228
00:13:41,080 --> 00:13:46,500
sequence, okay? 
And I will obtain this [INAUDIBLE], okay? 

229
00:13:46,500 --> 00:13:50,800
And what is nice about this now is that I 
can move to the next element. 

230
00:13:50,800 --> 00:13:54,550
So this is all correct, okay? 
And then I can move inside a sequence and 

231
00:13:54,550 --> 00:13:58,840
try to do the same kind of things for the 
subsequent vertices. 

232
00:13:58,840 --> 00:14:02,378
So in a sense what I just told you is 
that I have a very simple algorithm, 

233
00:14:02,378 --> 00:14:05,844
okay? 
Which goes to the various elements of the 

234
00:14:05,844 --> 00:14:09,938
sequence very much like I did for the 
consequence example. 

235
00:14:09,938 --> 00:14:13,151
Any particular value in the two, I'm 
considering now is they're not the same 

236
00:14:13,151 --> 00:14:18,303
as the value in the optimum solution. 
I find the sequence starting at I, which 

237
00:14:18,303 --> 00:14:22,268
basically ends with the value in the 
optimal solution With the city inside the 

238
00:14:22,268 --> 00:14:26,500
optimal solution, right? 
So I have a subsequence, no? 

239
00:14:26,500 --> 00:14:28,660
And what do I do? 
[NOISE], I reverse it, okay? 

240
00:14:28,660 --> 00:14:31,544
And that's what you see over there. 
So I go up to si, I take the sequence 

241
00:14:31,544 --> 00:14:34,883
which brings me to the particular point 
that I wanted, I reverse it so I start 

242
00:14:34,883 --> 00:14:40,280
with that guy, which is no correct. 
I have all the sequence which is there, 

243
00:14:40,280 --> 00:14:42,910
and I have my new sequence which is 
correct. 

244
00:14:42,910 --> 00:14:47,480
Not only up to a si-, not only up to s i 
minus 1, but now also to s i, okay? 

245
00:14:47,480 --> 00:14:53,150
And I continue doing that, until I find 
until I get to the optimum solution. 

246
00:14:53,150 --> 00:14:57,434
So once again, very simple algorithm, to 
move from a particular configuration to 

247
00:14:57,434 --> 00:15:01,690
an optimum solution, okay? 
Now, you know, unless you, I'm going to 

248
00:15:01,690 --> 00:15:06,258
leave you with an interesting homework. 
Remember the TPP, the traveling [UNKNOWN] 

249
00:15:06,258 --> 00:15:09,024
problem, okay? 
So I will show you this beautiful 

250
00:15:09,024 --> 00:15:12,716
neighborhood, right, with five moves, sub 
homes, sub teams, sub rounds, sub partial 

251
00:15:12,716 --> 00:15:17,570
teams, sub partial home, okay? 
The question for your homework. 

252
00:15:17,570 --> 00:15:20,380
Is essentially, is this neighborhood 
connected? 

253
00:15:20,380 --> 00:15:24,600
And you, if you find the answer, okay, 
call me. 

254
00:15:24,600 --> 00:15:28,260
You can call me if you find the answer. 
I'm very interested in knowing if you 

255
00:15:28,260 --> 00:15:32,090
actually can find the answer to this 
particular problem. 

256
00:15:32,090 --> 00:15:34,250
Thank you very much, see you next time.