A Nobel Combinatorial Algorithm towards the TSP
Author(s):
Saptarshi Naskar, Tanmoy Biswas, Susobhan Ghosh, Debashis Roy, Arup Kr. Goswami
Keywords:
Combinatorial Algorithm, Optimal Solution, TSP, Sub-optimal
Abstract
In our problem, if each of the vertices has an edge to every other vertex, we have a complete weighted graph. This graph has numerous Hamiltonian circuits, and we are to pick the one that has the smallest sum of distances (or weights). If there are only two vertices then, the problem is trivial, since only one tour is possible. For the three vertices TSP is also trivial. If all links are present then there are nearly (n!) different tours for n vertices TSP. The size of the search space becomes extremely large for large n, so that an exhaustive search is impracticable. The problem has some direct importance, since quite a lot of practical applications can be reduced to TSP. The TSP has become a standard test bed for combinatorial optimization methods which attempt to find near optimum solution to this NP-Complete problem. Several approximation techniques typically based on deterministic or probabilistic search heuristic have been proposed in the literature, including the classical local search algorithms, simulated annealing, threshold accepting, Tabu-search, elastic nets, neural networks, genetic algorithm, and ant colonies. It also has a theoretical importance in complexity theory, since the TSP is one of the classes of “NP Complete” combinatorial problem. NP-Complete problems have the property that no one has found any really efficient way of solving them for large n. They are also known to be equivalent to each other; if we knew how to solve one kind of NP Complete problem we could solve the lot. Holy Grail is to find a solution algorithm that gives a sub optimal solution in a time that has a polynomial variation with the size n of the problem. If we could find a method whose solution time grows polynomially with n then we can apply it to get sub optimal solution in reasonable time. The best the people have been able to do, however, is to solve it in a time that varies exponentially with n. Such algorithm runs out of puff at a certain level of n, more or less independently of computing power. If computation varies as 2n, say, then a thousand fold increases in computing power will only allow us to add another 10 vertices.
Article Details
Unique Paper ID: 154541

Publication Volume & Issue: Volume 8, Issue 11

Page(s): 540 - 543
Article Preview & Download


Share This Article

Conference Alert

NCSST-2021

AICTE Sponsored National Conference on Smart Systems and Technologies

Last Date: 25th November 2021

SWEC- Management

LATEST INNOVATION’S AND FUTURE TRENDS IN MANAGEMENT

Last Date: 7th November 2021

Latest Publication

Go To Issue



Call For Paper

Volume 10 Issue 1

Last Date for paper submitting for March Issue is 25 June 2023

About Us

IJIRT.org enables door in research by providing high quality research articles in open access market.

Send us any query related to your research on editor@ijirt.org

Social Media

Google Verified Reviews

Contact Details

Telephone:6351679790
Email: editor@ijirt.org
Website: ijirt.org

Policies

Important Links

Browse Rsearch papers