function [ order_best, cost_best ] = tsp_nearest ( x )

%*****************************************************************************80
%
%% tsp_nearest() seeks an optimal round trip by the nearest neighbor method.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    07 July 2026
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    real x(n,*): the coordinates of the cities.
%    A second dimension of 2 is typical, but a 3D problem would also work.
%
%  Output:
%
%    integer order_best(n): the optimal ordering.
%
%    real cost_best: the length of the optimal round trip.
%
  n = size ( x, 1 );
%
%  Initialize:
%    the best cost so far is Infinity;
%    the best tour so far is 1, 2, ..., n.
%
  cost_best = Inf;
  order_best = 1 : n;
%
%  Try starting at city START and moving to the nearest neighbor.
%
  for start = 1 : n

    order = tsp_tour_nearest ( n, x, start );
    cost = tsp_tour_cost ( n, x, order );

    if ( cost < cost_best )
      order_best = order;
      cost_best = cost;
      fprintf ( '  Route from city %d has best cost = %g\n', ...
        start, cost_best );
    end 

  end

  return
end
function cost = tsp_tour_cost ( n, x, order )

%*****************************************************************************80
%
%% tsp_tour_cost() evaluates the cost of a TSP tour.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    14 June 2026
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer n: the number of cities.
%
%    real x(n,:): the city coordinates.
%
%    integer order(n): the order in which the cities are visited.
%
%  Output:
%
%    real cost: the cost of the route.
%
  cost = 0.0;
  i1 = n;
  for i2 = 1 : n
    cost = cost + norm ( x(order(i1),:) - x(order(i2),:) );
    i1 = i2;
  end

  return
end
function order = tsp_tour_nearest ( n, x, start );

%*****************************************************************************80
%
%% tsp_tour_nearest() finds a nearest neighbor route for a given start.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    06 March 2022
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer N, the number of cities.
%
%    real X(N,2): the city coordinates.
%
%    integer START, the starting city.
%
%  Output:
%
%    integer order(N): a route that starts at START.
%
  order = zeros ( n, 1 );
  order(1) = start;
%
%  Create the distance table.
%
  d = zeros ( n, n );
  for i = 1 : n
    for j = 1 : n
      d(i,j) = norm ( x(i,:) - x(j,:) );
    end
  end
%
%  Forbid the null trip.
%
  for i = 1 : n
    d(i,i) = Inf;
  end
%
%  Note that START has been used.
%
  d(:,start) = Inf;
%
%  Find nearest unused city.
%  Go there, and remove it from list of possibles.
%
  from = start;
  for j = 2 : n
    [ ~, to ] = min ( d(from,:) );
    order(j) = to;
    d(:,to) = Inf;
    from = to;
  end
  
  return
end

