189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
· 2. NP- NP means type of problems which are solvable in polynomial time by a non- deterministic Turing machine only. Symbol NP stands for ‘Non-deterministic Polynomial’.
· 3. NP-Hard - A problem is said to be NP-Hard if an algorithm for solving it could be transformed to solving any other NP problem.
· 4. NP- Complete- A problem which is both NP and NP-Hard is called NP complete problem.
· 5. Triangle Inequality- According to the triangle inequality sum of two sides of a triangle is greater than the third side. In almost all cases of Euclidean TSP the triangle is satisfied.
· 6. Local optimal tour: A tour may be termed as a local optimal tour if it is the optimal tour w.r.t. to the points existing on the network. This tour may or may not be the optimal tour.
· 7. Optimal branch: The optimal branch may be defined as the nearest branch chosen according to the lowest sum rule or ‘a+b-c rule.’
205
· 8.a+b-c rule: Refer page 12
206
207
208
· 9. Interior local improvements: Local improvements are said to be interior local improvements if we change only the relative positions of points without constructing a virtual segment.
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
· 10. Exterior local improvements: If we change position of points by creating a virtual segment we get a external local improvement. Note that once this improvement is introduced we cannot return to our starting point by simply reversing the steps as reversal of a virtual segment is not defined as it is arbitrary.