The Traveling Salesman Problem
THE TRAVELING SALESMAN PROBLEM
by Corinne Brucato B.A., Sonoma State University, 2010 M.S., University of Pittsburgh, 2013
Submitted to the Graduate Faculty of the Department of Mathematics in partial fulfillment
of the requirements for the degree of Master of Sciences
University of Pittsburgh 2013
UNIVERSITY OF PITTSBURGH MATHEMATICS DEPARTMENT
This thesis was presented by
Corinne Brucato It was defended on
April 16, 2013 and approved by Dr. Jeffrey Paul Wheeler, University of Pittsburgh, Mathematics Dr. Beverly Michael, University of Pittsburgh, Mathematics Dr. Catalin Trenchea, University of Pittsburgh, Mathematics Dr. Anna Vainchtein, University of Pittsburgh, Mathematics Thesis Advisor: Dr. Jeffrey Paul Wheeler, University of Pittsburgh, Mathematics
ii
Copyright c by Corinne Brucato 2013
iii
THE TRAVELING SALESMAN PROBLEM Corinne Brucato, M.S.
University of Pittsburgh, 2013 Although a global solution for the Traveling Salesman Problem does not yet exist, there are algorithms for an existing local solution. There are also necessary and sufficient conditions to determine if a possible solution does exist when one is not given a complete graph. This paper gives an introduction to the Traveling Salesman Problem that includes current research. Additionally, the algorithms are used to find a route traveling through twenty US colleges. As well, we use the Geometric Algorithm to assign scouts for the Pittsburgh Pirates.
iv
TABLE OF CONTENTS
1.0 THE PROBLEM STATED . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2.0 SOME BASIC GRAPH THEORY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2.2 Advanced Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.0 THE HISTORY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.0 COMPLEXITY CLASSES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5.0 SOME KNOWN ALGORITHMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.1 Nearest-Neighbor Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.2 Closest Insertion Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 5.3 Geometric Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 6.0 EXISTENCE OF HAMILTONIAN PATHS AND CYCLES . . . . . . . . . . . . . . . . 28 6.1 Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.2 Not Complete Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 7.0 APPLICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 7.1 Colleges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7.1.1 Nearest Neighbor and Closest Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . 35 7.1.2 Geometric Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 7.2 Pittsburgh Pirates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 8.0 CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 INDEX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
v
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- an introduction to design thinking process guide
- community problem solving introduction
- excel practice test 10 sample excel assessment test
- 8 14 problems waveguides rutgers university
- 30 behavioral interview questions
- cs221 practice midterm stanford university
- quant fm and data science interview compilation
- the interview as a selection device problems and
- the traveling salesman problem
- how to prepare yourself for an interview with google