viajant1.pas

{ ppc386 -va -vh *.pas }
{ COMIENZO DE DESCRIPCION

  Problema del viajante mediante un algoritmo \'avido 
  versi\'on 1.
  keywords: algoritmos

  FIN DE DESCRIPCION }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----
En cada etapa de un algoritmo avido buscamos la opcion 
localmente optima lo cual, en el Problema del Agente de 
Viajes (PAV), equivale a considerar cada ciudad por turno, 
buscando la distancia mas corta a las ciudades todavia 
no visitadas. 

Para verificar que (i) no se produzca un vertice de grado 
$ g = 3 $ (es decir, debemos entrar y salir de cada ciudad 
solo una vez), y (ii) que no se forme un ciclo parcial con 
las ciudades ya visitadas (excepto al final), procedemos de 
la siguiente manera:

Previo al lazo de busqueda: 

1 construimos una matriz de distancias $ A $ entre todas las 
  ciudades, donde cada elemento $ A_[ij] $ es la distancia 
  desde la ciudad $ i $ hasta la ciudad $ j $, para 
  $ i,j = 1, 2,...,n $, donde $ n $ es el numero de ciudades. 
  Se desprende que esta matriz de distancias: 
  (a) tendra diagonal principal nula, y 
  (b) los elementos $ A_[ij] $ fuera de la diagonal principal, 
       son simetricos;

2 inicializamos un vector de ciudades ya visitadas como falso ;

Ahora:

1 empezamos en alguna fila de la matriz (ciudad) $ p $, y 
  seleccionamos la columna $ j $ con la menor distancia 
  $ A_[pj] $ en esa fila, pero exceptuando: (a) el termino en 
  la diagonal principal $ A_[pp] $ (que es nulo), y (b) las 
  distancias $ A_[pj] $ a las ciudades $ j $ ya visitadas;

2 antes de cerrar el lazo de busqueda, marcamos la ciudad 
  $ p $ como visitada, pasamos a la fila $ j $, y repetimos 
  el proceso hasta agotar las filas disponibles en la matriz;

3 finalmente se cierra el circuito con la ciudad $ p $ de 
  partida.

Por ultimo, este codigo ademas hace un lazo $ p=1,2,..., n $ 
sobre todas las ciudades, dando una solucion para "n" agentes
de viajes que salgan desde cada ciudad. }

{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ $ Id: viajant1.pas 2002/04/05 19:00 jdelia  Exp jdelia    $}

program  viajant1 ;
const
  n = 6   ; {numero de ciudades consideradas}
  o = ' ' ;
type
  xcoord = record
    x, y : real ;
  end ;
  tvecto1 = array [1..n+1]    of char ;
  tvecto2 = array [1..n]      of boolean ;
  tmatriz = array [1..n,1..n] of real  ;
  vcoorde = array [1..n]      of xcoord ;
var
  a         : tmatriz ;
  r         : vcoorde ;
  secuencia : tvecto1 ;
  visitada  : tvecto2 ;
  i, j, k   : integer ;
  dx, dy    : real    ;
  c_p       : char    ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure ERROR (h: string);
begin
  writeln (' error ',h);
  writeln ;
  halt ;
end ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure IMPRIME (h : string ; var a: tmatriz);
var
  i, j : integer ;
begin
  writeln ;
  writeln (h) ;
  writeln ;
  for i := 1 to n do begin
    for j := 1 to  n do  write (o, a [i,j]:10) ; 
    writeln ;
  end ;
  writeln ;
end ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure MATRIZ_DISTANCIA (var a: tmatriz);
var {pre-define las coordenadas cartesianas de las ciudades}
  xi, xj : real ;
  yi, yj : real ;
begin
  r [1].x :=  0  ;  r [1].y := 0  ;
  r [2].x :=  4  ;  r [2].y := 3  ;
  r [3].x :=  1  ;  r [3].y := 7  ;
  r [4].x := 15  ;  r [4].y := 7  ;
  r [5].x := 15  ;  r [5].y := 4  ;
  r [6].x := 18  ;  r [6].y := 0  ;
  for i := 1 to (n) do begin
    xi := r [i].x ;
    yi := r [i].y ;
    for j := 1 to (n) do begin
      xj := r [j].x ;
      yj := r [j].y ;
      dx := (xi - xj) ;
      dy := (yi - yj) ;
      a [i,j] := sqrt ( dx * dx + dy * dy ) ;
    end ;
  end ;
  IMPRIME (' Matriz con las distancias entre ciudades ', a);
end ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
procedure VIAJERO_AVIDO (var a : tmatriz);
var
  grande, menor : real    ;
  distancia     : real    ;
  p, q          : integer ;
begin
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ busca la maxima distancia en la matriz                    }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
  grande := 0 ;
  for i := 1 to  (n)  do begin
  for j := 1 to  (n)  do begin
    if  ( a [i,j] > grande ) then  grande := a [i,j] ;
  end ; {j}
  end ; {i}
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ busca desde cada ciudad posible de partida                }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
  for  p := 1 to (n) do begin
    c_p := chr (p + ord ('A') - 1);
    writeln ;
    writeln (' ciudad de partida ; c_p = ', c_p);
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ re-inicia marcas                                          }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
    for i := 1 to (n) do begin
      visitada  [i] := false ;
      secuencia [i] := o ;
    end ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ empieza la busqueda en la ciudad (fila) de partida "p"    }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
    distancia := 0 ;
    i := p ; { primera fila (ciudad) a revisar }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ busca en las columnas disponibles (ciudades no-visitadas) }
{ de la matriz "A", la columna "q" con la menor distancia   }
{ en la fila "i" (que es la solucion localmente optima).    }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
    for k := 1 to (n - 1) do begin
      menor := grande ;
      q := 0 ;
      for j := 1 to (n) do begin
        if  ( j <> i ) and ( not visitada [j] ) and 
            ( a [i,j] < menor  ) then begin
            q := j ;
            menor := a [i,j] ;
        end ; {if}
      end ; {j}
      if ( q < 1 ) then ERROR (' (viajante): q < 1 ');
      if ( q > n ) then ERROR (' (viajante): q > n ');
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ marca la ciudad (columna) "i" como visitada, recuerda el  }
{ camino seguido, almacena distancia, y pasa a la siguiente }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
      visitada  [i] := true ;
      secuencia [k] := chr (i + ord ('A') - 1);
      distancia := distancia + a [i,q] ;
      i := q ;
    end ; {k}
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ cierra el camino con la ciudad de partida "p"             } 
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
    visitada  [i]   := true ;
    secuencia [n]   := chr (i + ord ('A') - 1);
    secuencia [n+1] := chr (p + ord ('A') - 1);
    distancia := distancia + a [i,q] ;
    distancia := distancia + a [i,p] ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ impresion                                                 }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
     writeln (' distancia total ; d = ', distancia: 4:4 );
    for i := 1 to (n + 1) do begin
      writeln (' secuencia ; s = ',  secuencia [i]);
    end ; {i}
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
{ fin lazo de partir en cada ciudad                         }
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
  end ; {p}
  writeln ;
end ;
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}
begin
  MATRIZ_DISTANCIA (a) ;
  VIAJERO_AVIDO    (a) ;
end .
{-----+-----+-----+-----+-----+-----+-----+-----+-----+-----}