Optimization: principles and algorithms, by Michel Bierlaire
run2703nearestNeighbor.m
Go to the documentation of this file.
1 %> \file
2 %> Runs example 27.3 of \cite Bier15-book, solving the problem using the greedy heuristic (Algorithm 27.1)
3
4 %> @ingroup Running
5 %> @author Michel Bierlaire
6 %> @date Tue Apr 14 11:36:53 2015
7 %> @ingroup chap27
8
9 coord = [3.9168352575438883 9.137342270173304;
10 1.1699050319257487 18.455418341069745;
11 9.721881077629464 28.346794704912273;
12 7.390077284252903 39.41399505514082;
13 10.330134350013772 8.872575373705086;
14 17.54844435443345 12.555248083372415;
15 13.973337600200706 27.293670391120408;
16 10.780367650957938 32.30890310240921;
17 27.537494117722936 3.405255742784993;
18 22.109051040277585 13.629868632672725;
19 22.104604981898312 24.4082789143701;
20 22.642443138528456 39.900926037817364;
21 30.483507633842855 3.3699397182036805;
22 39.342134080320214 14.52455206463652;
23 37.63893123807275 21.751973125910553;
24 30.059401007763743 32.48285416836698;
25 ];
26
27 [n two] = size(coord) ;
28 dist = zeros(n,n) ;
29
30 for i=1:n
31  for j=1:n
32  if (i != j)
33  dist(i,j) = sqrt((coord(i,1) - coord(j,1))**2 + (coord(i,2) - coord(j,2))**2) ;
34  endif
35  endfor
36 endfor
37
38 tour = tspNearestNeighbor(dist)
39 printf("Tour length: %f\n",tspTourLength(tour,dist)) ;
function tspTourLength(in tour, in dist)
Calculate the length of a tour for the TSP.
function tspNearestNeighbor(in dist)
Compute an halmitonian path using the nearest neighbor heuristic.