Reduced Complexity Divide and Conquer Algorithm for Large Scale TSP /
Hoda Ahmed Darwish
Reduced Complexity Divide and Conquer Algorithm for Large Scale TSP / خوارزم التقسيم والحل منخفض التعقيد لحل مشكلة البائع المتجول ذات الحجم الكبير Hoda A. Darwish , Supervised Ihab Talkhan - Cairo : Hoda Ahmed Darwish , 2014 - 39 P. : charts , facsimiles ; 30cm
Thesis (M.Sc.) - Cairo University - Faculty of Engineering - Department of Computer Engineering
This thesis presents an algorithm to solve the NP-hard Traveling Salesman Problem (TSP) 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. It is based on the idea of utilizing a spatial 2geographical3 Divide and Conquer technique in conjunction with heuristic Nearest Neighbor 2-opt TSP algorithm. At a cost of only 9% lower performance, the algorithm has complexity of O((N/b)2) where N is the number of cities and b is the number of spatial divisions. This is much lower than published results. Specifically it is lower than the reference Lin-Kernighan algorithm which has computational complexity of O (N2.2)making it practical for real applications
Computational Geometry Heuristic Algorithms Traveling Salesman Problem
Reduced Complexity Divide and Conquer Algorithm for Large Scale TSP / خوارزم التقسيم والحل منخفض التعقيد لحل مشكلة البائع المتجول ذات الحجم الكبير Hoda A. Darwish , Supervised Ihab Talkhan - Cairo : Hoda Ahmed Darwish , 2014 - 39 P. : charts , facsimiles ; 30cm
Thesis (M.Sc.) - Cairo University - Faculty of Engineering - Department of Computer Engineering
This thesis presents an algorithm to solve the NP-hard Traveling Salesman Problem (TSP) 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. It is based on the idea of utilizing a spatial 2geographical3 Divide and Conquer technique in conjunction with heuristic Nearest Neighbor 2-opt TSP algorithm. At a cost of only 9% lower performance, the algorithm has complexity of O((N/b)2) where N is the number of cities and b is the number of spatial divisions. This is much lower than published results. Specifically it is lower than the reference Lin-Kernighan algorithm which has computational complexity of O (N2.2)making it practical for real applications
Computational Geometry Heuristic Algorithms Traveling Salesman Problem