Reduced Complexity Divide and Conquer Algorithm for Large Scale TSPs
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2014, Vol 5, Issue 1
Abstract
The Traveling Salesman Problem (TSP) is the problem of finding the shortest path passing through all given cities while only passing by each city once and finishing at the same starting city. This problem has NP-hard complexity making it extremely impractical to get the most optimal path even for problems as small as 20 cities since the number of permutations becomes too high. Many heuristic methods have been devised to reach “good” solutions in reasonable time. In this paper, we present the idea of utilizing a spatial “geographical” Divide and Conquer technique in conjunction with heuristic TSP algorithms specifically the Nearest Neighbor 2-opt algorithm. We have found that the proposed algorithm has lower complexity than algorithms published in the literature. This comes at a lower accuracy expense of around 9%. It is our belief that the presented approach will be welcomed to the community especially for large problems where a reasonable solution could be reached in a fraction of the time.
Authors and Affiliations
Hoda Darwish, Ihab Talkhan
Keywords
Related Articles
- EP ID EP88339
- DOI 10.14569/IJACSA.2014.050110
- Views 94
- Downloads 0
Modelling of Thermal Storage in Damaged Composite Structures using Time Displaced Gradient Field Technique (TDGF)
This paper presents a new approach to composite surface characterization using Gradient Field time displacement. The new technique employs calculation of thermally charged regions within a composite structure as a result...
Research on Energy Saving Method for IDC CRAC System based on Prediction of Temperature
Amid the information era, energy consumption of IDC Computer Room Air Conditioning (CRAC) system is becoming increasingly serious. Thus there is growing concern over energy saving and consumption reduction. Based on the...
A Trapezoidal Cross-Section Stacked Gate FinFET with Gate Extension for Improved Gate Control
An improved trapezoidal pile gate bulk FinFET device is implemented with an extension in the gate for enhancing the performance. The novelty in the design is trapezoidal cross-section FinFET with stacked metal gate along...
Large Scale Graph Matching(LSGM): Techniques, Tools, Applications and Challenges
Large Scale Graph Matching (LSGM) is one of the fundamental problems in Graph theory and it has applications in many areas such as Computer Vision, Machine Learning, Pattern Recognition and Big Data Analytics (Data Scien...
Secure Deletion of Data from SSD
The deletion of data from storage is an important component on data security. The deletion of entire disc or special files is well-known on hard drives, but this is quite different on SSDs, because they have a different...