header
Local cover image
Local cover image
Image from OpenLibrary

Reduced Complexity Divide and Conquer Algorithm for Large Scale TSP / Hoda A. Darwish , Supervised Ihab Talkhan

By: Contributor(s): Material type: TextTextLanguage: English Publication details: Cairo : Hoda Ahmed Darwish , 2014Description: 39 P. : charts , facsimiles ; 30cmOther title:
  • خوارزم التقسيم والحل منخفض التعقيد لحل مشكلة البائع المتجول ذات الحجم الكبير [Added title page title]
Subject(s): Online resources: Available additional physical forms:
  • Issued also as CD
Dissertation note: Thesis (M.Sc.) - Cairo University - Faculty of Engineering - Department of Computer Engineering Summary: 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/{u221A}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
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Item type Current library Home library Call number Copy number Status Barcode
Thesis Thesis قاعة الرسائل الجامعية - الدور الاول المكتبة المركزبة الجديدة - جامعة القاهرة Cai01.13.06.M.Sc.2014.Ho.R (Browse shelf(Opens below)) Not for loan 01010110063425000
CD - Rom CD - Rom مخـــزن الرســائل الجـــامعية - البدروم المكتبة المركزبة الجديدة - جامعة القاهرة Cai01.13.06.M.Sc.2014.Ho.R (Browse shelf(Opens below)) 63425.CD Not for loan 01020110063425000

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/{u221A}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

Issued also as CD

There are no comments on this title.

to post a comment.

Click on an image to view it in the image viewer

Local cover image