304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
Hamiltonian’s path problem HPP or Traveling salesman problem TSP is a well known NP complete problem. We would try to establish that it is solvable in polynomial time of fifth degree at most. Before that we must state TSP or HPP.
ETSP: Suppose there is a salesperson that has to visit several cities in order to sell business. He has the specified map of all the cities that come in his way. Obviously his problem is to find shortest possible route or the optimal tour that covers all the cities. We assume Euclidean TSP onwards so triangle inequality is satisfied and all the maps are drawn on a 2-D plane.
Obviously we can name all the routes and get the answer instantaneously. But the bone in the dish is not summing the distances from city to city. It is the number of such cases.
For ‘n’ cities total cases turn out to be n! , which is a whopping number even for values of ‘n’ as small as 100.
Therefore even for modest 100-city tour there are 100! cases.
These cases are too large for a deterministic computer to handle. It may take decades for a fastest computer on earth to find optimal tour or shortest possible route for say 1000 cities only.
Actually computers can handle polynomial time processes i.e. where P =Cnk.
319
These Polynomials doesn’t grow that fast if ‘n’ is the variable or size of data.
320
Here ‘n’ = Number of cities or size of data or input.
321
P =Cn10 (say)
322
323
324
325
Doesn’t grows as fast as say P =C.3n
Here latter are called exponential time processes. After them comes NP processes.
Now we will prove
that HPP or ETSP
is
solvable
in polynomial time
using
geometrical &
topological properties of polygons applied on topolo