The Traveling Salesperson Problem: A Look At NP-Completeness and Methods For Finding Solutions

Loading...
Thumbnail Image
Authors
Wendt, Theodore
Advisor
Holly Zullo
Mark Parker
Joan Stottlemyer
Editor
Date of Issue
2002-04-01
Subject Keywords
Publisher
Citation
Series/Report No.
item.page.identifier
Title
The Traveling Salesperson Problem: A Look At NP-Completeness and Methods For Finding Solutions
Other Titles
Type
thesis
Description
Abstract
Finding an efficient algorithm for solving NP-Complete problems has long been a goal of computer scientists and mathematicians. The purpose of this paper is to examine existing heuristics (approximate algorithms) and to construct original heuristics for solving the Traveling Salesperson Problem, a famous NP-Complete problem. Each heuristic is implemented on a personal computer using C++. The results of the heuristics are then compared against the best known solutions for specific well-studied instances of the problem.
Sponsors
Degree Awarded
Bachelor's
Semester
Spring
Department
Mathematics, Engineering & Computer Science