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 84
- Downloads 0
Translation of the Mutation Operator from Genetic Algorithms to Evolutionary Ontologies
Recently introduced, evolutionary ontologies rep-resent a new concept as a combination of genetic algorithms and ontologies. We have defined a new framework comprising a set of parameters required for any evolutionary al...
Credit Card Fraud Detection using Deep Learning based on Auto-Encoder and Restricted Boltzmann Machine
Frauds have no constant patterns. They always change their behavior; so, we need to use an unsupervised learning. Fraudsters learn about new technology that allows them to execute frauds through online transactions. Frau...
Internet Orchestra of Things: A Different Perspective on the Internet of Things
The Internet of Things (IoT) is defined as a global network that links together living and/or non-living entities, such as people, animals, software, physical objects or devices. These entities can interact with each oth...
The Methodology for Ontology Development in Lesson Plan Domain
Ontology has been recognized as a knowledge representation mechanism that supports a semantic web application. The semantic web application that supports lesson plan construction is crucial for teachers to deal with the...
A Simple Strategy to Start Domain Ontology from Scratch
Aiming the usage of Domain Ontology as an educational tool for neophyte students and focusing in a fast and easy way to start Domain Ontology from scratch, the semantics are set aside to identify contexts of concep...