Constructive heuristics[edit]
Nearest Neighbour algorithm for a TSP with 7 cities. The solution changes as the starting point is changed
The nearest neighbour (NN) algorithm (a greedy algorithm) lets the salesperson choose the nearest unvisited city as his next move. This algorithm quickly yields an effectively short route. For N cities randomly distributed on a plane, the algorithm on average yields a path 25% longer than the shortest possible path.[17] However, there exist many specially arranged city distributions which make the NN algorithm give the worst route (Gutin, Yeo, and Zverovich, 2002). This is true for both asymmetric and symmetric TSPs (Gutin and Yeo, 2007). Rosenkrantz et al. [1977] showed that the NN algorithm has the approximation factor
Θ ( log | V | ) {\displaystyle \Theta (\log |V|)}
for instances satisfying the triangle inequality. A variation of NN algorithm, called Nearest Fragment (NF) operator, which connects a group (fragment) of nearest unvisited cities, can find shorter route with successive iterations.[18] The NF operator can also be applied on an initial solution obtained by NN algorithm for further improvement in an elitist model, where only better solutions are accepted.
The bitonic tour of a set of points is the minimum-perimeter monotone polygon that has the points as its vertices; it can be computed efficiently by dynamic programming.
Another constructive heuristic, Match Twice and Stitch (MTS) (Kahng, Reda 2004 [19]), performs two sequential matchings, where the second matching is executed after deleting all the edges of the first matching, to yield a set of cycles. The cycles are then stitched to produce the final tour.
Traveling Salesman Problem - Nearest Neighbor
Finds a near-optimal solution to a TSP using Nearest Neighbor (NN)
TSP_NN Traveling Salesman Problem (TSP) Nearest Neighbor (NN) Algorithm
The Nearest Neighbor algorithm produces different results depending on
which city is selected as the starting point. This function determines
the Nearest Neighbor routes for multiple starting points and returns
the best of those routes
Summary:
1. A single salesman travels to each of the cities and completes the
route by returning to the city he started from
2. Each city is visited by the salesman exactly once
Input:
USERCONFIG (structure) with zero or more of the following fields:
- XY (float) is an Nx2 matrix of city locations, where N is the number of cities
- DMAT (float) is an NxN matrix of point to point distances/costs
- POPSIZE (scalar integer) is the size of the population (should be <= N)
- SHOWPROG (scalar logical) shows the GA progress if true
- SHOWRESULT (scalar logical) shows the GA results if true
- SHOWWAITBAR (scalar logical) shows a waitbar if true
Input Notes:
1. Rather than passing in a structure containing these fields, any/all of
these inputs can be passed in as parameter/value pairs in any order instead.
2. Field/parameter names are case insensitive but must match exactly otherwise.
Output:
RESULTSTRUCT (structure) with the following fields:
(in addition to a record of the algorithm configuration)
- OPTROUTE (integer array) is the best route found by the algorithm
- MINDIST (scalar float) is the cost of the best route
Usage:
tsp_nn
-or-
tsp_nn(userConfig)
-or-
resultStruct = tsp_nn;
-or-
resultStruct = tsp_nn(userConfig);
-or-
[...] = tsp_nn('Param1',Value1,'Param2',Value2, ...);
Example:
% Let the function create an example problem to solve
tsp_nn;
Example:
% Request the output structure from the solver
resultStruct = tsp_nn;
Example:
% Pass a random set of user-defined XY points to the solver
userConfig = struct('xy',10*rand(50,2));
resultStruct = tsp_nn(userConfig);
Example:
% Pass a more interesting set of XY points to the solver
n = 100;
phi = (sqrt(5)-1)/2;
theta = 2*pi*phi*(0:n-1);
rho = (1:n).^phi;
[x,y] = pol2cart(th�
评论0