MATH 101 Lecture Notes - Lecture 3: K-Nearest Neighbors Algorithm, Travelling Salesman Problem
Document Summary
The nearest neighbor method is a method to approximate solutions to the traveling salesperson problem. The optimal solution can be approximated using the following steps: model the problem with a complete, weighted graph, identify the vertex that serves as the starting point, from the starting point, choose an edge with the smallest weight. Move along this edge to the second vertex: from the second vertex, choose the edge with the smallest weight that does not lead to a vertex already visited. A sales director who lives in city a is required to fly to regional offices in cities b,c,d, and: the weighted graph gives the one-way airfares. Use the nearest neighbor method to find an approximate solution. Step 1: e 128, d 147, c 114, b 180. Step 2: b 116, e 115, d 169. Use the nearest neighbor algorithm to find the city that would be visited third.
