Sera OT??

[Roberto Bonvallet]

Arturo Mardones escribio:
> Tengo q hacer un programa para "resolver" el problema del vendedor
> viajero (con heuristica claro esta)... Y no se q lenguaje utilizar... 

Eso es OT. Para no estar (tan) OT, se me ocurrio programar una
heuristica en Bash; si te decides por alguna shell Unix, esto te puede
ser de ayuda. Puedes usar esta matriz como entrada para probarla con 6
ciudades (copiala en un archivo y se lo pasas al programa)

24 22 23 17 25
   21 33 15 24
      26 24 27
         23 21
            19

He aqui el script:

#!/bin/bash

# Implementación de la heurística Nearest Neighbor 
# para el problema del vendedor viajero
# 20040427 by rbonvall

# uso: tsp -c nro_ciudades -d archivo_distancias

# Si dij es la distancia entre las ciudades i y j,
# archivo_distancias tiene el siguiente formato:
# d12 d13 d14 ... ... d1n
# d23 d24 d25 ... d2n
# .
# :
# d(n-2)(n-1) d(n-2)n
# d(n-1)n

# mensaje de error de uso
uso="Uso: $0 -c nro_ciudades -d archivo_distancias"
# distancia máxima imposible entre ciudades
infinito=999999
# archivo temporal
temp=/tmp/tmp$$
if [ -f $temp ]
then
    rm -f $temp
fi
touch $temp

# parsea argumentos
c_flag=
d_flag=
set -- $(getopt c:d: "$@")
[ $# -lt 1 ] && exit 1  # getopt failed
while [ $# -gt 0 ]
do
    case "$1" in
        -c) 
            nro_ciudades="$2"
            c_flag=1
            shift
        ;;
        -d)
            archivo_distancias="$2"
            if [ -f $archivo_distancias ]
            then
                distancias=$(cat $archivo_distancias)
            else
                echo "No existe el archivo $archivo_distancias"
                exit 1
            fi
            d_flag=1
            shift
        ;;
        *) 
            break
        ;;
    esac
    shift
done
if ! [ $c_flag ] || ! [ $d_flag ]
then
    echo >&2 $uso
    exit 1
fi

inicial=1   # ciudad desde la que se iniciará el ciclo
actual=$inicial  # ciudad en la que va el ciclo

# iteramos hasta que en el archivo de salida estén todas las ciudades
while [ $(wc -l $temp| sed -e 's/^[ ]*//g'| cut -d' ' -f 1) -lt $nro_ciudades ]
do
    echo "Ciudad actual: $actual"
    # agrega ciudad actual al ciclo
    echo $actual >> $temp
    # inicializa mínima distancia y ciudad más cercana
    min_dist=$infinito
    ciudad_mas_cercana=
    # busca vecina más cercana
    for vecina in $(seq $nro_ciudades)
    do
        # determina qué ciudad tiene número menor para 
        # saber cómo buscar la distancia en el archivo
        if [ $vecina -lt $actual ]
        then
            max=$actual
            min=$vecina
        elif [ $vecina -gt $actual ]
        then
            max=$vecina
            min=$actual
        fi
        
        if ! [ "$(grep "$vecina" $temp)" ] # evitamos ciudades ya visitadas
        then
            # calcula la distancia entre la ciudad actual y la vecina
            dist=$(awk "NR == $min { print \$($max - $min) }" < $archivo_distancias)
            echo "Distancia de $actual a $vecina: $dist"
            # determina si esta vecina es la más cercana
            if [ $dist -le $min_dist ]
            then
                min_dist=$dist
                ciudad_mas_cercana=$vecina
            fi
        fi
    done
    echo "Ciudad más cercana a $actual: $ciudad_mas_cercana"

    # nos movemos a la vecina más cercana
    actual=$ciudad_mas_cercana
done

echo "El ciclo es:"
cat $temp
rm $temp
-- 
Roberto Bonvallet