Date of Award
Mathematics, Engineering & Computer Science
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.
Wendt, Theodore, "The Traveling Salesperson Problem: A Look At NP-Completeness and Methods For Finding Solutions" (2002). Mathematics, Engineering and Computer Science Undergraduate Theses. 84.