Sera OT??

[Horst von Brand]

Roberto Bonvallet <rbonvall en inf.utfsm.cl> dijo:
> 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

Esa es mi clase preferida de demente!

> 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

mktemp(1)

> 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)

                  distancias=$(< $archivo_distancias)

(Mas eficiente, segun bash(1))

>             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

Ahora falta en ex(1)... emacs LISP es demasiado simple ;-)
-- 
Dr. Horst H. von Brand                   User #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513