ITIG

Memoria

Práctica de la
convocatoria de Junio
2014
Metodología de la
programación

Julio Sala Ruiz
ITIG

Actividades
Actividad 1
Se realizará una memoria con los siguientes apartados:- Algoritmo 1:
o Descripción detallada (con palabras) de cómo funciona el algoritmo que calcula el
camino más corto. Redactarlo de forma que cualquier persona ajena a la asignatura
pueda entenderel funcionamiento del mismo.
Se trata de efectuar todos los posibles recorridos que partiendo del supermercado, pasen por
todos los lugares de reparto y vuelvan nuevamente al origen, en cada uno deestos recorridos,
se anotarán los tiempos y así se encontrará el recorrido que menor tiempo lleve. A partir de la
posición de salida trato de ir a todos los demás sitios adyacentes a donde estoy yvoy anotando
por donde paso. Primero miro si el destino es viable y si no ha sido visitado ya para no pasar
más de una vez por el mismo sitio, si es viable lo anoto como usado y miro si es el últimoque
tengo que visitar antes de volver al supermercado. Si es el último anoto la solución, porque ya
tengo un camino completo, si no es solución pruebo a ir a otro sitio desde la posición actual.Cuando no me quedan más posibilidades, desmarco como visitada la posición actual y pruebo
con la siguiente posición a la que pueda ir a partir de la posición anterior a la desmarcada.

o Tipo detécnica que se aplica y justificación.
Se trata de una búsqueda por vuelta atrás o backtracking. Se ha optado por esta técnica
porque examina todas las posibilidades, siendo imposible que se deje ningúncamino por
explorar, lo que asegura encontrar la solución óptima.

o Tipificación y pseudocódigo del algoritmo solución (adecuada según el programa que
se implemente).

CONST n = ...x[0..n-1]:entero
xmin[0..n-1]:entero
usados[0..n-1]:booleano
adyacencia[0..n-1,0..n-1]:entero
min:entero
encontrados:entero

//numero de sitios
//solución, orden de los lugares a visitar
//mejor...