Hamiltonian cycle and TSP: A backtracking approach
Journal Title: International Journal on Computer Science and Engineering - Year 2011, Vol 3, Issue 4
Abstract
Backtracking is one of the strategies to reduce the complexity of a problem. Backtracking mainly useful when there is a no solution by going forward in that direction so we required backtracking from it to reduce the complexity and save the time. Backtracking has ability to give same result in far fewer attempts than the exhaustive or brute force method trials. This paper gives the recursive algorithm for Hamiltonian cycle and TSP (travelling salesman problem) based on the backtracking approach. If at any stage it is detected that the particular input or combination will not lead to an optimal solution than we can discard and a new input can be selected.
Authors and Affiliations
Dipak Patel , Nishant Doshi , Shakti Patel , Dishant Soni
Keywords
Related Articles
- EP ID EP119093
- DOI -
- Views 113
- Downloads 0
A Scheduling Approach with Processor and Network Heterogeneity for Grid Environment
Processor heterogeneity is an important issue in grid environment. In this paper, a list based task scheduling algorithm, called “critical path scheduling with t-level” (CPST) for grid computing system is proposed. There...
CHOICES ON DESIGNING GF (P) ELLIPTIC CURVE COPROCESSOR BENEFITING FROM MAPPING HOMOGENEOUS CURVES IN PARALLEL MULTIPLICATIONS
Modular inversion operation is known to be the most time consuming operation in ECC field arithmetic computations. In addition, Many ECC designs that use projective coordinates over GF (p) have not considered different f...
Role Oriented Test Case Generation for Agent Based System
Agent Oriented Software Engineering (AOSE) is a rapidly developing area of research. Current research and development primarily focuses on the analysis, design and implementation of agent based software whereas testing i...
Comparison between k-nn and svm method for speech emotion recognition
Human - Computer intelligent interaction (HCII) is an emerging field of science aimed at providing natural ways for humans to use computer as aids. Machine intelligence needs to include emotional intelligence it is argue...
iImplementation of AMBA AHB protocol for high capacity memory management using VHDL
Microprocessor performance has improved rapidly these years. In contrast memory latencies and bandwidths have improved little. The result is that the memory access time is the bottleneck which limits the system performan...