PRACTICA 1 PREDA UNED 2013-2014

Contenido
DESCRIPCIÓN DEL ALGORITMO UTILIZADO Y SU ADECUACIÓN AL PROBLEMA ........................... 3
DEMOSTRACIÓN DE OPTIMALIDAD .............................................................................................. 4
ANÁLISIS DEL COSTE COMPUTACIONAL........................................................................................ 5
ESTUDIO DE OTRAS ALTERNATIVAS Y COMPARATIVA.................................................................. 5
DESCRIPCIÓN DE LOS CASOS DE PRUEBA REALIZADOS ................................................................ 5
DESCRIPCIÓN DE LOS TIPOS Y ESTRUCTURAS DE DATOS UTILIZADOS ......................................... 7
DIAGRAMA DE CLASES.................................................................................................................. 8
CÓDIGO FUENTE............................................................................................................................ 9
Clase express ............................................................................................................................. 9
Clase AlgoritmoVoraz.............................................................................................................. 11
Clase LeerFichero .................................................................................................................... 12
Clase GrabarFichero ................................................................................................................ 13

2

DESCRIPCIÓN DEL ALGORITMO UTILIZADO Y SU ADECUACIÓN AL
PROBLEMA
Nosencontramos ante un problema de optimización y para su resolución utilizaremos,
tal como se indica en el enunciado de la práctica, un algoritmo voraz.
De entre las características y elementos que pueden intervenir en un algoritmo voraz,
se pueden identificar en este problema los siguientes:
x
x
x

x
x

x
x

Resolución de un problema de forma óptima. El problema consiste en repostar emenor número de veces en un trayecto dado.
Conjunto inicial de candidatos. El número de gasolineras existentes en el trayecto. En
el enunciado las denomina “G”.
Conjunto de candidatos seleccionados. Este conjunto inicialmente está vacío,
conteniendo después de la resolución del problema, las gasolineras en las que se ha de
repostar, es decir la solución óptima.
Solución. La solución sealcanza cuando se llega al destino, habiendo repostado según
se indica en la función selección.
Factible. Esto se cumple si la distancia entre las gasolineras es menor o igual que n
(según el enunciado “n” es el número de kilómetros que puede realizar si repostar el
vehículo).
Función selección. Esta función consistirá en recorrer el mayor número de kilómetros
sin repostar el vehículo.
Funciónobjetivo. Esta función no aparece explícita en el algoritmo

Después de analizar los elementos del esquema voraz aplicables a nuestro problema,
podemos decir que nuestra estrategia ha de consistir en recorrer el mayor número de
kilómetros sin repostar y conseguir el objetivo de repostar el menor número de veces posible.
En la página 95 del texto base de la asignatura aparece el siguientealgoritmo voraz en
pseudocódigo que implementa la solución al problema planteado.
1 tipo Vector=matriz [0…G-1] booleano
2 fun MensajeríaExpress (DG:Vector [1…G-1] natural, n, G:natural): Vector
3
var
4
solución:Vector
5
fvar
6
para i=1 hasta G-1 hacer
7
solución[i]mfalso
8
fpara
9
im0
10
contKmm0
11
repetir
12
repetir
13
imi+1
14
contKmmcontKm+DG[i]
15
hasta (contKm>n o(i=G-1))
3

16
17
18
19
20
21
22
23

si contKm>n entones
imi-1
solución[i]mcierto
contKmmo
fsi
hasta i=G-1
dev solución[ ]
ffun

A continuación se describe que hace este algoritmo:
o
o

o

En la línea 4 se declara el conjunto de candidatos, como vector, el cual entre las líneas
6 y 8 se inicializa todo como falso.
Entre las líneas 11 y 21 nos encontraos con una...