Alumna: Alicia Snchez

Centro: UNED-Las Rozas (Madrid)

Ejercicios resueltos de programacin 3

Tema 6. Algoritmos voraces.




























Ejercicios tema 6 Curso 2007-08 Pgina 2 de 55

En estos ejercicios se incluyen tanto las cuestiones como los problemas de exmenes, por lo
que lo distinguiremos en tres partes. Aprovechamos para poner el ndice donde estarn estas
partes, por ser muy extenso el documento:
1. Introduccin terica . 3
2. Cuestiones de exmenes 5
3. Problemas de exmenes solucionados 36
4. Problemas de exmenes sin solucin o planteados .. 51































Ejercicios tema 6 Curso 2007-08 Pgina 3 de 55

Introduccin terica:
Antes de resolver estas cuestiones y problemas recordaremos la teora ms general de los
algoritmos voraces, como hemos hecho en temas anteriores, ya que nos sern muy tiles para
resolverlos.
Empezaremos a ver los algoritmos voraces, ya que son los ms fciles de ver.
Resultan fciles de inventar e implementar y cuando funcionan son muy
eficientes. Sin embargo, hay muchos problemas que no se pueden resolver usando el
enfoque voraz.
Los algoritmos voraces se utilizan tpicamente para resolver problemas de
optimizacin. Por ejemplo, la bsqueda de la recta ms corta para ir desde un nodo a
otro a travs de una red de trabajo o la bsqueda del mejor orden para ejecutar un
conjunto de tareas en una computadora.
Un algoritmo voraz nunca reconsidera su decisin, sea cual fuere la situacin que
pudiera surgir ms adelante.

Generalmente, los algoritmos voraces y los problemas que stos resuelven se
caracterizan por la mayora de propiedades siguientes:
- Son adecuadas para problemas de optimizacin, tal y como vimos en el
ejemplo anterior.
- Para construir la solucin de nuestro problema disponemos de un conjunto
(o lista) de candidatos. Por ejemplo, para el caso de las monedas, los
candidatos son las monedas disponibles, para construir una ruta los
candidatos son las aristas de un grafo, etc. A medida que avanza el algoritmo
tendremos estos conjuntos:
- Candidatos considerados y seleccionados.
- Candidatos considerados y rechazados.

Las funciones empleadas ms destacadas de este esquema son:
1. Funcin de solucin: Comprueba si un cierto conjunto de candidatos
constituye una solucin de nuestro problema, ignorando si es o no ptima por
el momento. Puede que exista o no solucin.
2. Funcin factible: Comprueba si el candidato es compatible con la solucin
parcial construida hasta el momento; esto es, si existe una solucin
incluyendo dicha solucin parcial y el citado candidato.
3. Funcin de seleccin: Indica en cualquier momento cul es el ms
prometedor de los candidatos restantes, que no han sido seleccionados ni
rechazados. Es la ms importante de todas.
4. Funcin objetivo: Da el valor de la solucin que hemos hallado: el nmero
de monedas utilizadas para dar la vuelta, la longitud de la ruta calculada, etc.
Est funcin no aparece explcitamente en el algoritmo voraz.

Para resolver nuestro problema, buscamos un conjunto de candidatos que
constituyan una solucin y que optimice (maximice o minimice, segn los casos) el
valor de la funcin objetivo. Los algoritmos voraces avanzan paso a paso:

Ejercicios tema 6 Curso 2007-08 Pgina 4 de 55

- Inicialmente, el conjunto de elementos seleccionados est vaco y el de
solucin tambin lo est.
- En cada paso, se considera aadir a este conjunto el mejor candidato sin
considerar los restantes, estando guiada nuestra seleccin por la funcin de
seleccin. Se nos darn estos casos:
1. Si el conjunto ampliado de candidatos seleccionados ya no fuera
factible (no podemos completar el conjunto de solucin parcial dado
por el momento), rechazamos el candidato considerado por el
momento y no lo volvemos a considerar.
2. Si el conjunto aumentado sigue siendo factible, entonces aadimos el
candidato actual al conjunto de candidatos seleccionados. Cada vez
que se ampla el conjunto de candidatos seleccionados comprobamos
si este constituye una solucin para nuestro problema. Se quedar en
ese conjunto para siempre.
Cuando el algoritmo voraz funciona correctamente, la primera solucin que se
encuentra es la ptima.
El esquema voraz es el siguiente:
funcion voraz (C: Conjunto): conjunto
{ C es el conjunto de candidatos }
S { Construimos la solucin en el conjunto S }
mientras C 0 y solucin (S) hacer
x sclcccionor (C)
C C\ {x}
si factible (S {x}) entonces S S {x}
si solucin (S) entonces devolver S
si no devolver no hay solucin
La funcin de seleccin suele estar relacionada con la funcin objetivo. Por ejemplo,
si estamos intentando maximizar nuestros beneficios, es probable que seleccionemos
aquel candidato restante que posea mayor valor individual. En ocasiones, puede
haber varias funciones de seleccin plausibles.













Ejercicios tema 6 Curso 2007-08 Pgina 5 de 55

1 parte. Cuestiones de exmenes:
Febrero 2000-1 (ejercicio 3)
Enunciado: Qu variante del problema de la mochila admite solucin voraz, y por qu? Qu
variante no admite solucin voraz? Poner un ejemplo del segundo caso en el que la solucin
voraz no nos lleve a la solucin voraz.
Respuesta:
El problema de la mochila se puede enunciar de esta manera:
Maximizar x

n
=1
con la restriccin x

w
n
=1

Teniendo en cuenta que los objetos son ilimitados y que cada uno tiene asociado un valor
positivo y un peso positivo. Queremos llevar la mochila respetando la limitacin de la mochila
W. Veremos las variantes del problema en cuestin a continuacin.
La variante de la mochila que admite solucin voraz es la variante donde podemos fragmentar
los objetos, siendo el nmero de objetos ilimitado. Esta variante admite solucin voraz porque
encontramos una funcin de seleccin que nos permite escoger un candidato a cada paso, de
forma que obtengamos una solucin ptima. Dicha funcin consiste en escoger los objetos
por orden decreciente (de mayor a menor) segn su relacin valor/peso, lo que nos lleva a una
solucin ptima.
La variante de la mochila que no admite solucin voraz es aqulla en la que no se nos permite
fragmentar los objetos, aunque sea ilimitado como antes. Para ello, pondremos un
contraejemplo, que no llega a solucin ptima. Tenemos que la mochila tiene un peso mximo
de w =10, por lo que el valor y peso de los distintos objetos ser:
i 1 2
v
i
8 5
w
i
6 5

i
w
i
1.33 1
Segn el algoritmo voraz escogeremos los objetos por orden decreciente en funcin de la
relacin valor/peso. Sin embargo, como en esta ocasin no podemos fragmentar los objetos, al
introducir el objeto 1 de peso 6, siendo menor que 10, ya no podremos introducir ms.
Habramos llegado a solucin ptima si escogemos dos objetos nmero 2, que llenaran la
mochila y tendra valor 10 sin sobrepasar el peso mximo de la mochila (w =10).
Vemos en este contraejemplo que pese a seguir la funcin de seleccin del algoritmo voraz en
esta segunda variante no llegamos a solucin ptima, por lo que deducimos que la primera
variante llega siempre a solucin ptima, por poder fraccionarse los objetos.

Septiembre 2000-reserva (ejercicio 2)
Enunciado: Los algoritmos de Prim y Kruskal calculan, de distintas formas, el rbol de
recubrimiento mnimo de un grafo. Cul de los dos es ms eficiente para un grado de alta
densidad de aristas?
Respuesta: El algoritmo de Kruskal tiene un coste algortmico 0(o log(n)), siendo a el
nmero de aristas, mientras que el de Prim tiene coste de 0(n
2
), independientemente del
nmero de aristas.


Ejercicios tema 6 Curso 2007-08 Pgina 6 de 55

Si la densidad del grafo es alta (grafo denso) a tiende a
n(n-2)
2
, por lo que el coste del
algoritmo de Kruskal es 0(n
2
log(n)), quedando igual el coste del algoritmo de Prim: 0(n
2
).
Si la densidad del grafo es baja (grafo disperso) a tiende a n, por lo que el coste del algoritmo
de Kruskal sera 0(n log(n)), quedndose el de Prim: 0(n
2
).
En el ejercicio se nos pregunta sobre la comparacin de costes en grafo denso, por lo que
sera, en este caso, ms eficiente el de Prim con coste 0(n
2
) en comparacin con el de Kruskal
0(n
2
log(n)).
Como aadido decir que si se compararan los costes para los grafos dispersos, el ms eficiente
sera el de Kruskal con coste 0(n log(n)) en comparacin con el de Prim 0(n
2
).
Por ltimo, si implementamos el algoritmo de Prim usando montculos invertidos (o de
mnimos) tendra coste algortmico de 0(o log(n)), igualndose al de Kruskal.

Febrero 2001-2 (ejercicio 1)
Enunciado: Mostrar mediante un ejemplo que el algoritmo de Dijkstra no siempre encuentra el
camino mnimo si existe una distancia negativa.
Respuesta: Recordemos que el algoritmo de Dijkstra devuelve los caminos mnimos desde el
origen hasta cada uno de los dems nodos. El pseudocdigo es el siguiente:
funcion Dijkstra (L[1..n, 1..n]): matriz[2..n]
matriz D[2..n]
{ Iniciacin }
C {2, 3,.., n} { S =N/ C slo existe implcitamente }
para i 2 hasta n hacer [i] I[1,i]
{ Bucle voraz }
repetir n 2 veces
: algn elemento de C que minimiza [:]
C C\ {:} { e implcitamente S S {:} }
para cada w C hacer
[w] min([w],[w] +I[:,w]);
devolver D
Haremos dos ejemplos distintos para verificar que no encontrara camino mnimo si existe una
distancia negativa. El primero de ellos es un ejemplo puesto por el autor, mientras que el
segundo es el del propio ejercicio. Pasamos a verlos:











Ejercicios tema 6 Curso 2007-08 Pgina 7 de 55

1
er
ejemplo: Se nos da este grafo:

1 1


-1
Siguiendo el algoritmo de Dijkstra empezando por el nodo a, tendremos:
Paso v C D P
b c
Inicializacin - {b,c} [1,1] [o,o]
1 b {c} [1,0] [o,b]

Observamos que para ir del nodo a al c tendremos dos caminos el directo con coste 1 y tal y
como hemos visto antes pasando a travs del nodo b, con coste 0. Por tanto, vemos que es
imposible que exista un camino con coste 0, por lo que no podemos encontrar el camino
mnimo con aristas de distancias negativas (adems de ser fsicamente imposible tener
distancia negativa).

2 ejemplo: Se nos da este grafo:

2 4

1
5

-9
1


Siguiendo paso a paso el algoritmo de Dijkstra tendremos:
Paso v C D P
2 3 4 5 6
Inicializacin - {2,3,4,5,6} [2,4,,,] [1,1,,,]
1 2 {3,4,5,6} [2,4,3,,] [1,1,2,,]
2 4 {3,5,6} [2,4,3,,] [1,1,2,,]
3 3 {5,6} [2,4,3,9,] [1,1,2,3,]
4 5 {6} [2,4,3,9,0] [1,1,2,3,5]

Observamos que el coste hasta llegar al nodo 6 es 0, siendo de nuevo imposible, porque no es
posible llegar a un nodo con coste 0, siendo el resto positivos. Con este nuevo ejemplo, se
observa que no llega a hallar los caminos mnimos nunca usando el algoritmo de Dijkstra.


a
b c
1
2 3
6
5 4

Ejercicios tema 6 Curso 2007-08 Pgina 8 de 55

Septiembre 2001 (ejercicio 1)
Enunciado: Comenta de qu formas se puede mejorar la eficiencia del algoritmo de Dijkstra el
uso de estructuras de datos adecuada.
Respuesta: Con esta respuesta completaremos la teora dada en el resumen del tema (pag.
227 del libro de teora). Utilizando una matriz de adyacencia y matrices para representar el
algoritmo, el coste es 0(n
2
), teniendo en cuenta estas operaciones:
- Inicializar la matriz de adyacencia: 0(n).
- Bucle del algoritmo voraz: 0(n
2
).
Si resulta que el nmero de aristas a es mayor que el de nodos al cuadrado (o >n
2
), resulta
apropiado utilizar una lista de adyacencia, evitando examinar entradas innecesarias (donde no
existan aristas), ahorrando as tiempo en el bucle ms interno del algoritmo.

Por otro lado, podemos utilizar un montculo invertido (la raz es el elemento menor) para
representar el camino mnimo que se ir generando (que llamaremos D), esto hace que buscar
un nodo que minimice el coste conlleve estas operaciones:
Inicializar el montculo: 0(n).
Eliminar la raz del montculo: 0(log(n)).
Igualmente, las operaciones empleadas en el bucle ms interno del algoritmo reducirn su
coste, situndose en 0(log(n)).
Si se produce la eliminacin de la raz del montculo (el bucle se ejecuta n 2 veces) y hay que
flotar un mximo de a nodos (siendo a el nmero de aristas) obtenemos un tiempo total de
0((o +n) log(n)).
Si el grafo es conexo, es decir, o n 1, el tiempo total es 0(n log(n)).
Si el grafo es denso ser preferible la implementacin con matrices, si es disperso es mejor la
implementacin con montculos.
NOTA DEL AUTOR: Se observa en este ejercicio una incongruencia en los enunciados, en uno
pide esto mismo y en otro dice: halla el grado de expansin mnimo del grafo de la figura
mediante el algoritmo de Kruskal. Detalla cada paso. No s cul es el correcto.

Septiembre 2001 (ejercicio 2)
Enunciado: Explica porqu una estructura de montculo suele ser adecuada para representar el
conjunto de candidatos de un algoritmo voraz.
Respuesta: En un algoritmo voraz iremos escogiendo el candidato ms apropiado a cada paso
para hallar la solucin segn el valor de la funcin de seleccin. Para agilizar esa seleccin
podemos tener dichos candidatos almacenados en un montculo de mnimos, de forma que el
valor sea el mnimo en la raz. De este modo, la seleccin del candidato consistir en ir
escogiendo la cima de dicho montculo y actualizarlo cuando as proceda, operaciones stas
que resultan ms eficientes en los montculos que en otros tipos de estructuras de datos.






Ejercicios tema 6 Curso 2007-08 Pgina 9 de 55

Septiembre 2001 (ejercicio 3)
Enunciado: Explica en qu consiste un problema de planificacin con plazo fijo. Por un ejemplo
con n =4 y resulvelo aplicando el algoritmo correspondiente.
Respuesta: Un problema de planificacin con plazo fijo consiste en lo siguiente:
Tenemos que ejecutar un conjunto de n tareas, cada una de las cuales requiere un tiempo
unitario. En cualquier instante I =1,2,podemos ejecutar nicamente una tarea. La tarea i
nos produce unos beneficios g

>0 slo en el caso en que sea ejecutada en un instante

anterior a J

.
En resumen:
n: Nmero de tareas de tiempo unitario. Por ejemplo, una hora, das,
I =1,2,,n En cada instante solo podemos realizar una tarea.
g
|
: Beneficio asociado a la tarea i.
d
|
: Plazo mximo de la tarea i.
El problema consiste en maximizar el beneficio total.

Como aadido al ejercicio del autor, pondremos este ejemplo con n =4 (se resuelve igual que
el del libro en la pgina 241 quitando las dos ltimas tareas, pero sirve):
i 1 2 3 4
g

20 15 10 7
J

3 1 1 3
Hemos ordenado previamente por orden decreciente de ganancias.
Los pasos son los siguientes:
Inicialmente: p =min(n,mox(J

)) =min(4,3) =3.
Por tanto, como mximo tendremos una planificacin de 3 tareas:




Primer intento: J
1
=3. Se asigna la tarea 1 a la posicin 3.
F(K) =3, F(I) =F(K) 1 =2. Fusionamos K con L






Segundo intento: J
2
=1. Se asigna la tarea 2 a la posicin 1.
F(K) =1, F(I) =F(K) 1=0. Fusionamos K con L





0 1 3 2
0 1
3
2
0
1
3
2

Ejercicios tema 6 Curso 2007-08 Pgina 10 de 55


Tercer intento: J
3
=1. No hay posiciones libres disponibles porque el valor de F es 0.

Cuarto intento: J
4
=3. Se asigna la tarea 4 a la posicin 3.
F(K) =1, F(I) =F(K) 1=0. Fusionamos K con L








La secuencia ptima es la 2, 4, 1 con valor 42.

Febrero 2002-1 (ejercicio 1)
Enunciado: Describir la estrategia de seleccin voraz para el problema de planificacin con
plazo fijo. Aplicarla a la resolucin del siguiente ejemplo detallando cada paso:
i 1 2 3 4 5 6
J

4 3 1 1 2 2
g

10 30 20 30 50 20
Respuesta: Este ejercicio est hecho completamente por el autor (alumna), as que no aseguro
que est correcto. Emplearemos la estrategia voraz para este tipo de problemas, en la que
tomaremos por orden decreciente de ganancias.
El primer paso es ordenar por orden decreciente de ganancias las tareas, donde aadimos una
nueva fila o

, que indicar la nueva ordenacin de las tareas:

i 1 2 3 4 5 6
o

5 2 4 6 3 1
J

2 3 1 2 1 4
g

50 30 30 20 20 10
Emplearemos la tcnica en la que resolveremos ms rpidamente el problema. Para ello,
usaremos estructura de particin y haremos lo siguiente:

Inicialmente: p =min(n,mox(J

)) =min(6,4) =4.
Por tanto, como mximo tendremos una planificacin de 4 tareas:







0
1
3
2
0 1 3 2 4

Ejercicios tema 6 Curso 2007-08 Pgina 11 de 55

Primer intento: J
1
=2. Se asigna la tarea 1 a la posicin 2.
F(K) =2, F(I) =F(K) 1=1. Fusionamos K con L






Segundo intento: J
2
=3. Se asigna la tarea 2 a la posicin 3.
F(K) =3, F(I) =F(K) 1=2. Fusionamos K con L








Tercer intento: J
3
=1. Se asigna la tarea 3 a la posicin 1.
F(K) =1, F(I) =F(K) 1=0. Fusionamos K con L










Cuarto intento: J
4
=2. No hay posiciones libres disponibles.
Quinto intento: J
5
=1. No hay posiciones libres disponibles.
sexto intento: J
6
=4. Se asigna la tarea 6 a la posicin 4.
F(K) =4, F(I) =F(K) 1=3. Fusionamos K con L. Nos fijamos que al fusionar K con L
cambiamos el puntero de la particin 4 al nodo 0, porque sera el rtulo de la particin con la
que se fusiona.







0 1 3
2
4
0 1
3
2
4
0
1
3
2
4
0
1
3
2
4

Ejercicios tema 6 Curso 2007-08 Pgina 12 de 55

Septiembre 2002 (ejercicio 2)
Enunciado: Aplicar el algoritmo de Dijkstra al grafo dirigido representado por la siguiente
matriz de adyacencia:






Tomando el nodo 1 como origen. Encuentra los caminos mnimos? Si la respuesta es negativa,
cules seran los verdaderos caminos mnimos y porque no la encuentra el algoritmo de
Dijkstra? Qu pasara si se invirtiese el sentido de la arista que une el nodo 3 con el 2?
Respuesta: Daremos una solucin por el autor. Segn la matriz de adyacencia el grafo, en este
caso, dirigido ser:


50 100 10 30
5

20 -30

10
Realizaremos estos pasos para hallar los caminos mnimos, empleando para ello el algoritmo
de Dijkstra:
Paso v C D P
2 3 4 5
Inicializacin - {2,3,4,5} [50,30,100,10] [1,1,1,1]
1 5 {2,3,4} [50,30,20,10] [1,1,5,1]
2 4 {2,3} [40,30,20,10] [4,1,5,1]
3 3 {2} [20,30,0,10] [3,1,3,1]

Tras aplicar el algoritmo de Dijkstra observamos que la distancia al nodo 4 es 0, cuando vemos
en el grafico hay distancias positivas en el resto de aristas, por tanto, es imposible que
encuentre caminos mnimos el algoritmo (incluso fsicamente distancias negativas lo es
igualmente). Tenemos en cuenta que la arista que une del nodo 3 al 4 es negativa (30),
siendo ste el que causa estos problemas.
Por ello, a la primera pregunta podremos responder que no encuentra caminos mnimos. Los
verdaderos caminos mnimos seran los que no pasan a travs del nodo 4, es decir, en el ltimo
paso puesto sera los que pasan a travs del nodo 1, vamos las aristas ({1,3},{1,5})
(apreciacin del autor).


1 2 3 4 5
1 - 50 30 100 10
2 - - - - -
3 - 5 - -30 -
4 - 20 - - -
5 - - - 10 -
1
2 3
4 5

Ejercicios tema 6 Curso 2007-08 Pgina 13 de 55

En la segunda pregunta, si se invirtiese el sentido de la arista que une el nodo 3 con el 2
quedara el grafo como sigue:


50 100 10 30
5

20 -30

10

No habra ningn cambio de costes entre aristas. Quedara igual el algoritmo de Dijkstra
(apreciacin del alumno).

Febrero 2003-1 (ejercicio 1)
Enunciado: Para qu se pueden utilizar montculos en el algoritmo de Kruskal? Qu mejoras
introduce en trminos de complejidad?
Respuesta: Recordamos que el algoritmo de Kruskal era aqul en el que queramos hallar un
rbol de recubrimiento mnimo (con n 1 aristas) de un grafo dado, para ello necesitbamos
ordenar de modo creciente los costes de las distintas aristas, seleccionndolas sin importar
que sean conexos hasta llegar a dicho rbol con todas las componentes conexas.
Emplearemos montculos invertidos o de mnimos (la raz es el menor elemento) para ordenar
las aristas de menor coste. El coste de esta implementacin usando montculos ser:
- Inicializacin: 0(o)
- Bucle repetir hasta que las n 1 aristas formen rbol de recubrimiento mnimo
ser: 0(o log(n)), siendo a el nmero de aristas.
Por tanto, tendremos que el coste del algoritmo ser ms ventajoso usando montculos
cuando el grafo es disperso, es decir, cuando a tiende a n, siendo el coste 0(n log(n)). En
tales casos, el algoritmo original desperdicia el tiempo ordenando estas aristas intiles, aunque
asintticamente tenga el mismo coste.










1
2 3
4 5

Ejercicios tema 6 Curso 2007-08 Pgina 14 de 55

Febrero 2003-1 (ejercicio 2)
Enunciado: Dado el grafo de la figura, aplicar el algoritmo de Dijkstra para hallar los caminos
ms cortos desde el nodo 1 hasta cada uno de los dems nodos, indicando en cada paso nodos
seleccionados, nodos no seleccionados, vector de distancias y vector de nodos precedentes.

20
7 15 5 7

7 5

Respuesta: Vemos en el grafo que las aristas son no dirigidas, recordemos que aunque el
algoritmo de Dijkstra est diseado para aristas dirigidas, stas equivalen a:


Aplicaremos estos mismos conceptos para aplicar el algoritmo de Dijkstra en el grafo anterior,
tomando el nodo 1 como nodo origen:
Paso v C D P
2 3 4 5
Inicializacin - {2,3,4,5} [20,,5,7] [1,,1,1]
1 4 {2,3,5} [20,12,5,7] [1,4,1,1]
2 5 {2,3} [20,12,5,7] [1,4,1,1]
3 3 {2} [19,30,0,10] [3,4,1,1]

NOTA: Se ha modificado la solucin original, ya que pienso que el vector de nodos precedentes
de la inicializacin es [1,,1,1], al no poder llegar al nodo 3 a directamente desde el origen
(nodo 1).

Febrero 2003-2 (ejercicio 2) (igual a ejercicio 3 de Septiembre 2006-reserva)
Enunciado: Puede un grafo tener dos rboles de recubrimiento mnimo diferentes? En caso
afirmativo, poner un ejemplo. En caso negativo, justificar la respuesta.
Respuesta:
Podemos decir que un grafo s que puede tener dos rboles de recubrimiento mnimo
diferentes.
Siendo 0 =N,A un grafo conexo en donde N es el conjunto de nodos y A es el de aristas.
Suponiendo que cada arista posee una longitud no negativa, encontrar un rbol de
recubrimiento mnimo consiste en hallar un subconjunto T de las aristas de G tal que
utilizando solamente las aristas de T, todos los nodos deben quedar conectados y adems la
suma de las longitudes de las aristas de T debe ser tan pequea como sea posible.




2
3 5 4
1
a b

Ejercicios tema 6 Curso 2007-08 Pgina 15 de 55

Un ejemplo de eso podra ser este grafo:


1 1 1


1 1 1



Tendremos dos rboles de recubrimiento mnimo:











Febrero 2003-2 (ejercicio 3)
Enunciado: Aplicar el algoritmo de planificacin con plazo fijo para las actividades o

maximizando el beneficio g

en el plazo J

. Detallar todos los pasos con claridad.

i 1 2 3 4 5 6 7 8
g

20 10 7 15 25 15 5 30
J

4 5 1 1 3 3 1 2
Respuesta:
Empezaremos por ordenar la matriz de costes y plazos por orden decreciente de ganancias,
por ser lo que queremos maximizar, incluyendo la nueva fila como vimos antes. Quedara as:
i 1 2 3 4 5 6 7 8
o

8 5 1 4 6 2 3 7
g

30 25 20 15 15 10 7 5
J

2 2 4 1 3 5 1 1
Para resolverlo hemos cogido el algoritmo rpido, en el que tomaremos una estructura de
particin e iramos fusionndolas con las tareas. La solucin dada con punteros es ma
personal, salvo que el orden de las tareas se ha respetado con respecto al de la solucin (oficial
2 3
5
4
1
2 3 5
4
1
3 2 5
4
1

Ejercicios tema 6 Curso 2007-08 Pgina 16 de 55

u oficiosa). En la dada del ejercicio lo resuelven como conjuntos disjuntos, aadiendo la
tarea cuando entra en la planificacin. Veremos paso a paso este algoritmo:
Inicialmente: p =min(n,mox(J

)) =min(8,5) =5.
Tendremos como mximo una planificacin de 5 tareas, siendo conjuntos distintos:


Como aadido pondremos la matriz j, donde reflejaramos la planificacin parcial paso a paso
de las tareas con respecto a los plazos, que sera:
1 2 3 4 5
j[]

En la solucin de este ejercicio nos aaden tambin los rtulos, pero recordemos que se
considera el rtulo el menor de los elementos. Por eso y para agilizar el ejercicio evitamos
ponerlo.
Primer intento: J
1
=2. Se asigna la tarea 1 a la posicin 2.
F(K) =2, F(I) =F(K) 1=1. Fusionamos K con L





1 2 3 4 5
j[]

Segundo intento: J
2
=2. Se asigna la tarea 2 a la posicin 2.
F(K) =2, F(I) =F(K) 1=1. Fusionamos K con L







1 2 3 4 5
j[]





0 0 0 0 0
0 1 0 0 0
2 1 0 0 0
0 1 3 2 4 5
0 1 3
2
4 5
0
1
3
2
4 5

Ejercicios tema 6 Curso 2007-08 Pgina 17 de 55

Tercer intento: J
3
=4. Se asigna la tarea 3 a la posicin 4.
F(K) =4, F(I) =F(K) 1=3. Fusionamos K con L







1 2 3 4 5
j[]

Cuarto intento: J
4
=1. Se rechaza la tarea, porque no hay posiciones libres disponibles.


Quinto intento: J
5
=3. Se asigna la tarea 4 a la posicin 3.
F(K) =3, F(I) =F(K) 1=2. Fusionamos K con L







1 2 3 4 5
j[]

NOTA DEL AUTOR: Esta solucin no est en la dada por la respuesta, pero lo aadiremos, en
este caso nos basaremos en el algoritmo pgina 241 del libro. Es decir, al fusionarse dos
conjuntos se fusionaran los rtulos, que en este caso el del 012 es 0 y el del 34 es 3,
por lo que apuntara al nodo 0. Es insignificante esta apreciacin, ya que el orden de ejecucin
de tareas queda igual pero entiendo que es lo suyo el hacerlo bien. No s si estar equivocada,
es una apreciacin ma personal.






2 1 0 3 0
2 1 5 3 0
0
1
3
2
4
5
0
1 3
2
4
5

Ejercicios tema 6 Curso 2007-08 Pgina 18 de 55

Sexto intento: J
6
=5. Se asigna la tarea 4 a la posicin 3.
F(K) =5, F(I) =F(K) 1=4. Fusionamos K con L







1 2 3 4 5
j[]

NOTA: Pasara algo similar al intento anterior, por lo que seguiramos nuestra filosofa. En la
solucin (insisto, no s si es oficial) que se ve en otros exmenes el puntero del nodo 5
apuntara a 4. No estoy realmente segura, pero creo que es lo suyo.

Sptimo y octavo intento: Se rechazan las tareas, por no haber posiciones libres.
Queda decir que las tareas que salen en la solucin son las ordenadas, con lo que habra que
hacer el cambio con respecto a o

, que seran las tareas reales. Segn dicha solucin el orden

de ejecucin de las tareas sera: o
5
,o
8
,o
6
,o
1
,o
2
, que realmente seran el orden de las tareas
tras hacer el cambio tras ordenar las tareas (para eso hay que ver la tabla de arriba).

Septiembre 2003 (ejercicio 3)
Enunciado: Explicar de qu manera se puede implementar mediante un esquema voraz el
conocido problema de la bsqueda del camino ms corto hacia la salida a un laberinto descrito
por la matriz rectangular de casillas de tipos libre y ocupada, y otras dos de tipo entrada y
salida. Compararlo en trminos de costes con otras soluciones.
Respuesta: En nuestra implementacin usando algoritmos voraces, cada casilla se corresponde
con un nodo. Casillas libres adyacentes tendran aristas dirigidas en ambas direcciones. El peso
sera unitario para cada arista. Las casillas de tipo ocupada no tienen aristas origen ni destino.
Quedara grficamente algo as, teniendo en cuenta que las aristas en ambas direcciones
equivalen a aristas no dirigidas y que no representamos el coste de cada una por ser unitario
(aadido del autor):
n



n
Casilla ocupada

2 1 5 3 6
0
1 3
2 4
5

Ejercicios tema 6 Curso 2007-08 Pgina 19 de 55

El resto de la respuesta es la dada en el ejercicio. De esta manera, un algoritmo de Dijkstra
puede hallar el camino ms corto de un nodo llegada a todos los dems, incluyendo el nodo
salida.
En trminos de coste, sin embargo, es necesario tener en cuenta que si el laberinto es un
cuadrado de lado n, como hemos dibujado previamente, el grafo tendr : =n
2
nodos y
alrededor de o =4 n
2
aristas (no puedo explicar con detalle de donde salen estos valores,
har acto de fe). En el anlisis del coste, la resolucin de Dijkstra si v (nmero de nodos del
grafo) es lo suficientemente grande hace cierta la expresin o :
2
y, por tanto, podemos
aproximarnos al coste 0((o +:) log(:)).

Septiembre 2003-reserva (ejercicio 2)
Enunciado: Con el criterio de tomar primero la moneda de mayor valor que sea menor o igual
que el cambio que queda por devolver, existe un algoritmo voraz para el problema de
devolver cambio con el menor nmero de monedas en cualquier sistema monetario?
Justifique su respuesta.
Respuesta: Solucin propuesta por el autor. No, no existe un algoritmo voraz para el problema
de devolver cambio con el menor nmero de monedas, debido al sistema monetario que
escogeremos, tal y como nos dicen en el enunciado. Para comprobar esto tendramos el
siguiente contraejemplo (est en el libro de ejercicios):
Se nos dan monedas de 30, 24, 12, 6, 3 y 1 unidades monetarias.
Tendremos que escoger el mnimo nmero de monedas que sumen 48, para ello aplicando
este algoritmo voraz cogeramos 1 de 30, 1 de 12 y 1 de 6 unidades monetarias. Si hubiramos
cogido 2 de 24 habramos conseguido la solucin ptima, por lo que se descarta que se pueda
resolver estos tipos de problemas en cualquier sistema monetario empleando algoritmos
voraces, en cualquier caso y siendo de optimizacin seran de ramificacin y poda.

Febrero 2004-1 (ejercicio 3)
Enunciado: Resolver mediante el algoritmo de Kruskal el rbol de expansin mnimo del grafo
definido por la siguiente matriz de adyacencia:






Respuesta: Esta solucin es dada por el autor. Vemos las siguientes caractersticas de la matriz
de adyacencia no dadas en el enunciado:
- Al ser un algoritmo de Kruskal suponemos que el grafo tiene aristas no dirigidas, lo que
significa que la matriz es simtrica.
- Por eso, existen smbolos , cuyo significado es que ya nos lo han dado antes en la
mitad superior de la matriz, es decir, por ser matriz simtrica.
- Por ltimo, el smbolo indica que no existe conexin entre aristas.
1 2 3 4 5
1 - 4 5 9
2 - - 6 1
3 - - - 3 1
4 - - - -
5 - - - - -

Ejercicios tema 6 Curso 2007-08 Pgina 20 de 55

Como en ejercicios anteriores tomaremos las filas como origen y las columnas como destino,
aunque siendo grafo no dirigido nos dar igual, por el momento (en los dirigidos de antes no
era as). El grafo sera:


4 5
9
6
1
3 1


Tendremos estos pasos:
1. Ordenamos las aristas de menor a mayor valor:
Nodo Coste
{3,5} 1
{2,5} 1
{3,4} 3
{1,2} 4
{1,3} 5
{2,3} 6
{1,5} 9

2. Una vez ordenadas las aristas, pasamos a resolverlo por el algoritmo de Kruskal, que como
no nos piden ms, ponemos estos campos:
Paso Arista seleccionada Componentes conexas
Inicializacin - {1},{2},{3},{4},{5}
1 {3,5} {1},{2},{3,5},{4}
2 {2,5} {1},{2,3,5},{4}
3 {3,4} {1},{2,3,4,5}
4 {1,2} {1,2,3,4,5}

Proceso terminado, ya no queda ninguna componente no conexa.








1
2 3
4 5

Ejercicios tema 6 Curso 2007-08 Pgina 21 de 55

Para que se vea de modo mejor resaltaremos las aristas que forman el rbol de recubrimiento
mnimo (ser el primer y ltimo ejercicio en el que lo hagamos):


4 5
9
6
1
3 1

Observamos que quedan unidas todas las aristas y que forman un conjunto conexo. Esto
tratbamos de demostrar.

Febrero 2004-2 (ejercicio 2)
Enunciado: Aplica el algoritmo de Kruskal al siguiente grafo indicando claramente en cada paso
que arista se selecciona, la evolucin de las componentes conexas y la evolucin de la solucin.

5 6

1
2 4 3 4

2 8
Respuesta: Como en el ejercicio anterior, el primer paso es ordenar las aristas de menor a
mayor valor:
|{2,3},{2,4},{4,5},{3,5},{3,6},{2,5},{1,2},{1,3},{5,6}|
NOTA: Por ser coherente con los ejercicios anteriores nuestro convenio para las aristas entre
nodos es usar llaves, pero en la solucin oficial (u oficiosa, lo desconozco) usan parntesis. No
va a significar un cambio en el algoritmo, slo a nivel de significado. Seguimos, por tanto, la
notacin del libro, dada en los apuntes.
Arista Componentes
Paso seleccionada conexas Solucin
Inicializacin - {1},{2},{3},{4},{5},{6}
1 {2,3} {1},{2,3},{4},{5},{6} |{2,3}|
2 {2,4} {1},{2,3,4},{5},{6} |{2,3},{2,4}|
3 {4,5} {1},{2,3,4,5},{6} |{2,3},{2,4},{4,5}|
4 {3,5} Rechazada, por estar en el mismo conjunto
5 {3,6} {1},{2,3,4,5,6} |{2,3},{2,4},{4,5},{3,6}|
6 {2,5} Rechazada, por estar en el mismo conjunto
7 {1,2} {1,2,3,4,5,6} |{2,3},{2,4},{4,5},{3,6},{1,2}|
Proceso terminado. No queda ninguna componente no conexa.
1
2 3
4 5
1
2 3
4 5 6

Ejercicios tema 6 Curso 2007-08 Pgina 22 de 55

NOTA DEL AUTOR: Vemos que en la solucin que se nos da al ordenar el vector se pone antes
la arista {4,5} y {2,4}. Observamos, que al intercambiarlos la solucin no cambia en absoluto.


Septiembre 2004 (ejercicio 3)
Enunciado: En qu se diferencian los algoritmos de Prim y de Kruskal? Discute tanto los
algoritmos como su complejidad en los casos peores de cada caso.
Respuesta: Los algoritmos de Prim y Kruskal se asemejan en que ambos crean rboles de
recubrimiento mnimo, aunque difieren en la funcin de seleccin de las aristas. Mientras que
el algoritmo de Primselecciona un nodo y construye un rbol a partir de l, seleccionando en
cada etapa la arista ms corta posible que pueda extender el rbol hasta un nodo adicional, el
de Kruskal escoge las aristas de menor a mayor coste sin importar si estn conexas o no.
El coste del algoritmo de Prim es 0(n
2
), mientras que el de Kruskal es 0(o log(n)), siendo a
el nmero de aristas. Distinguiremos estos casos para este ltimo:
- Si el grafo es disperso (a tiende a n), el coste del algoritmo es 0(n log(n)).
- Si el grafo es denso (a tiende a n
2
), el coste es 0(n
2
log(n)).
Es mejor, por tanto, el coste cuando el grafo es disperso en el algoritmo de Kruskal que en el
de Prim. En los grafos densos pasara al revs.
NOTA DEL AUTOR: Estos ejercicios se hacen igual. Se amplia, en este caso, la solucin dada con
respecto a la del ejercicio.

Septiembre 2004-reserva (ejercicio 1)
Enunciado: Defina que es un rbol de recubrimiento mnimo, explica alguno de los algoritmos
propuestos en la asignatura para hallarlos, explicando paso a paso un ejemplo.
Respuesta: La solucin est hecha completamente por un alumno.
Un rbol de recubrimiento mnimo es un subgrafo que contiene a todos los vrtices, que es
conexo y que el coste de total de sus aristas sea mnimo, ocupando n 1 aristas.
Entre los algoritmos que hay para hallarlos encontramos dos, el de Kruskal y el de Prim. Ambos
dos llegan a crear un rbol de recubrimiento mnimo, pero difieren en la funcin de seleccin
de las aristas y el modo de cogerlos.
Veremos, por tanto, el algoritmo de Kruskal con un ejemplo:

1 2
3 4 5 6
7

Ordenamos las aristas de menor a mayor coste:
|{1,2},{2,3},{1,4},{2,4},{2,5},{3,5},{4,5}|



1 2 3
4 5

Ejercicios tema 6 Curso 2007-08 Pgina 23 de 55

Los pasos nos quedaran as:
Arista Componentes
Paso seleccionada conexas Solucin
Inicializacin - {1},{2},{3},{4},{5}
1 {1,2} {1,2},{3},{4},{5} |{1,2}|
2 {2,3} {1,2,3},{4},{5} |{1,2},{2,3}|
3 {1,4} {1,2,3,4},{5} |{1,2},{2,3},{1,4}|
4 {2,4} Rechazada, por estar en el mismo conjunto
5 {2,5} {1,2,3,4,5} |{1,2},{2,3},{1,4},{2,5}|

Finaliza el problema, ya que existe una nica componente conexa.

Septiembre 2004-reserva (ejercicio 3)
Enunciado: Se dispone de n productos diferentes, infraccionables y en cantidades ilimitadas.
Cada tipo de producto tiene asociado un peso y un beneficio concreto. Deseamos cargar un
camin, que puede transportar un peso mximo PMAX, maximizando el beneficio de los
productos transportados por ste. Sera posible un algoritmo voraz a este planteamiento?
Responde razonadamente y plantear un ejemplo que justifique la respuesta.
Respuesta:
No, no es posible ningn algoritmo cuya funcin de seleccin llegue a encontrar solucin
ptima, por ser infraccionables los objetos. Pondremos un contraejemplo:
Se nos da estos productos con PHAX =100
i 1 2
:

150 100
w

51 50

i
w
i
2,9 2

Tomaremos los objetos por orden decreciente de relacin

i
w
i
y vemos que al coger el primer
objeto segn est funcin de seleccin, tenemos que cogeremos 1 objeto i =1, resultando:
w =51.
: =150.
Al no poder entrar ya ms objetos en la mochila, vemos que ya sera la solucin mejor. Aun as,
encontramos otra solucin ms ptima, que sera:
w =100.
: =200.
En este caso, seleccionamos dos objetos i =2 y vemos que el valor es mayor que en el caso
antes. Por tanto, no encontramos solucin ptima usando algoritmos voraces.

NOTA: Vemos que en el enunciado nos hablan de beneficios, pero al ser un problema de la
mochila, lo resolveremos como valor, que para este caso es similar. De nuevo, est resuelto
por el autor completamente el ejercicio.


Ejercicios tema 6 Curso 2007-08 Pgina 24 de 55

Febrero 2005-1 (ejercicio 1)
Enunciado: Se dispone de ficheros
1
,
2
,,
n
con tamaos l
1
,l
2
,,l
n
y de un disquete con
una capacidad total de almacenamiento J <l
1
+l
2
++ l
n

a) Suponiendo que se desea maximizar el nmero de ficheros almacenados y que se hace uso
de un planteamiento voraz basado en la seleccin de ficheros de menor a mayor tamao,
el algoritmo propuesto siempre obtendra la solucin ptima? En caso afirmativo,
demostrar la optimalidad y en caso negativo, ponga un contraejemplo.
b) En caso de que quisiramos ocupar la mayor cantidad de espacio en el disquete
independientemente del nmero de ficheros almacenados, una estrategia voraz basada
en la seleccin de mayor a menor tamao obtendra en todos los casos la solucin ptima?
En caso afirmativo, demostrar la optimalidad y en caso negativo, ponga un contraejemplo.
Respuesta:
a) El algoritmo voraz si obtendra la solucin ptima, es decir, un disquete con el mayor
nmero posible de ficheros.
Para la demostracin, tendramos lo siguiente:
Supongamos que los programas se encuentran inicialmente ordenados de menor a mayor
tamao, vamos a hacer la demostracin de optimalidad de la solucin comparando una
solucin ptima con una obtenida por el algoritmo voraz. Si ambas soluciones no fueran
iguales, iremos transformando la solucin ptima de partida, de forma que contine
siendo ptima, pero asemejndola cada vez con la obtenida por el algoritmo voraz. Si
consiguiramos igualar ambas soluciones en un nmero finito de pasos podremos afirmar
que la solucin obtenida es ptima (de modo nemotcnico es el mtodo dado en teora de
reduccin de diferencias).
Notacin: Una solucin cualquiera viene representada por Z =(z
1
,z
2
,,z
n
) donde
z
1
=0 implica que el fichero

no ha sido seleccionado como parte de la solucin. De

este modo, z

n
=1
indicar el nmero de ficheros seleccionados como solucin al
problema.
Siendo X la solucin devuelta por la estrategia voraz e Y la solucin al problema.
Supongamos que la estrategia voraz selecciona los k primeros ficheros (con 1 k n),
recordemos que los ficheros se encuentran inicialmente ordenados de menor a mayor
tamao. El fichero k +1 es rechazado, puesto que ya no es posible incluir un solo fichero
ms. De este modo, la solucin X ser (x
1
,x
2
,,x
k
,,x
n
) donde i {1..k}.x

=1 y
i {k +1..n}.x

=0.
Comenzando a comparar X con Y de izquierda a derecha, supongamos que ] 1 sea la
primera posicin donde x
]
y
]
. En este caso, obligatoriamente ] k, ya que en caso
contrario la solucin ptima incluira todos los ficheros escogidos por la estrategia voraz y
alguno ms, lo que se contradice con el hecho de que los ficheros del k +1 al n se
rechazan por la estrategia voraz porque no caben.
Este modo, x
]
y
]
, implica que y

=0, por lo que y

=] 1
]
=1
, que es menor que el
nmero de ficheros seleccionados por nuestra estrategia voraz como solucin al problema
x

]
=1
=]. Como suponemos que Y es una solucin ptima y

n
=1
n
=1
=k, esto
significa que existe un l >k ] (siendo l el tamao) tal que y
I
=1, es decir, existe un
fichero posterior para compensar el que no se ha escogido antes. Por la orden impuesta a
los ficheros, sabemos que l
]
l

, es decir, que si
I
cabe en el disco, podemos poner
]
sin
sobrepasar la capacidad total. Realizando este cambio en la solucin ptima Y, obtenemos
otra solucin Y en la cual y
]
=1=x

, y
]
=0 para el resto y
]
=y

. Esta nueva
solucin es ms parecida a X, y tiene el mismo nmero de ficheros que Y, por lo que sigue

Ejercicios tema 6 Curso 2007-08 Pgina 25 de 55

siendo ptima. Repitiendo este proceso, podemos ir igualando los ficheros en la solucin
ptima a los de la solucin voraz X, hasta alcanzar la posicin k.
b) El algoritmo voraz no obtendra la solucin ptima en todos los casos.
Contraejemplo: Supongamos la siguiente lista de ficheros con tamaos asociados:
Fichero F
1
F
2
F
3

Tamao 40 30 15
Supongamos que la capacidad del disquete es de 45 (este contraejemplo es parecido al
hecho anteriormente en el ejercicio 1 de Septiembre 2004-reserva).
Aplicando la estrategia voraz propuesta, es decir, escoger el fichero con mayor tamao
nicamente podramos almacenar el fichero F
1
, ocupando 40 de los 45 de capacidad que
tiene el disquete. Sin embargo, si hubiramos seleccionado los ficheros F
2
y F
3
hubiera
sido posible maximizar el espacio ocupado en el disco.

Febrero 2005-1 (ejercicio 2)
Enunciado: Exponga y explique el algoritmo ms eficiente que conozca para realizar una
planificacin de tareas de plazo fijo maximizando el beneficio.
Dada la tabla adjunta de tareas con sus beneficios (g

) y caducidades (J

), aplique paso a paso

el algoritmo propuesto, suponiendo que se desea realizar una planificacin con tiempo t =5
i 1 2 3 4 5 6 7 8 9
g

30 10 2 11 10 9 2 56 33
J

5 3 2 2 1 2 7 5 4
Respuesta: El ejercicio est hecho de manera ms didctica, aunque respetando la solucin.
Dividiremos este ejercicio en dos apartados:


















Ejercicios tema 6 Curso 2007-08 Pgina 26 de 55

a) El algoritmo ms apropiado es el algoritmo secuencia2, que sera el algoritmo denominado
rpido y el que emplearemos en este ejercicio:
funcion secuencia2 (J[1..n]): k, matriz [1..k]
matriz j, F[0..n]
{ Iniciacin }
p =min(n,mox{J[i]|1 i n});
para i 0 hasta p hacer ][i] 0
F[i] i
Iniciar el conjunto {i}
{ Bucle voraz }
para i 1 hasta n hacer { Orden decreciente de g }
k buscor(min(p,J[i]))
m F[k]
si m 0 entonces
][m] i;
l buscor(m 1)
F[k] F[l]
{ El conjunto resultante tiene la etiqueta k o l }
fusionar (k,l)
{ Slo queda comprimir la solucin }
k 0
para i 1 hasta p hacer
si ][i] >0 entonces k k +1
][k] ][i]
devolver k,][1..k]

El algoritmo ser el siguiente:
i. Iniciacin: Toda posicin 0,1,2,,p est en un conjunto diferente y F([i]) =i,
0 i p.

p =min(n,mox(J

)).
Mayor de los plazos
Nmero de tareas
La posicin 0 sirve para ver cuando la planificacin est llena.
ii. Adicin de una tarea con plazo d; se busca un conjunto que contenga a d; sea K este
conjunto. Si F(K) =0 se rechaza la tarea, en caso contrario:
- Se asigna la nueva tarea a la posicin F(K).
- Se busca el conjunto que contenga F(K) 1. Llamemos L a este conjunto (no
puede ser igual a K).
- Se fusionan K y L. El valor de F para este nuevo conjunto es el valor viejo de
F(I).





Ejercicios tema 6 Curso 2007-08 Pgina 27 de 55

b) Como en ejercicios anteriores seguiremos estos pasos:
Como primer paso, ordenamos la tabla propuesta por orden decreciente de beneficios
como sigue:
i 1 2 3 4 5 6 7 8 9
o

8 9 1 4 5 2 6 3 7
g

56 33 30 11 10 10 9 2 2
J

5 4 4 2 1 3 2 2 7
Veremos paso a paso el algoritmo como sigue:
Inicialmente: p =min(n,mox(J

)) =min(9,5) =7. En este caso concreto queremos

planificar las 5 primeras tareas, segn nos dicen en el enunciado, por lo que p se reduce a 5
(p =5).


Ponemos de nuevo la matriz de resultados, donde reflejaramos la planificacin parcial de
las tareas con respecto a los plazos (las tareas reales), que sera:
1 2 3 4 5
res[]

En la solucin de este ejercicio nos aaden tambin los rtulos, pero recordemos que se
considera el rtulo el menor de los elementos. Por eso y para agilizar el ejercicio evitamos
ponerlo.
Vamos escogiendo cada una de las tareas por el orden antes puesto e incluyndolos en su
correspondiente de particin. Esta operacin implica fusionar las estructuras en la cual se
ha incluido la tarea con la estructura de particin inmediatamente inferior. Escogeremos,
en este caso (como en anteriores), las tareas ordenadas siguiendo i de la tabla, para luego
tomar las tareas empleando o

.
Primer intento: J
1
=5. Se asigna la tarea 1 a la posicin 5.
F(K) =5, F(I) =F(K) 1=4. Fusionamos K con L



1 2 3 4 5
res[]







Segundo intento: J
2
=4. Se asigna la tarea 2 a la posicin 4.
0 0 0 0 0
0 0 0 0 1
5
0 1 3 2 4
5
0 1 3 2 4

Ejercicios tema 6 Curso 2007-08 Pgina 28 de 55

F(K) =4, F(I) =F(K) 1=3. Fusionamos K con L





1 2 3 4 5
res[]

Tercer intento: J
3
=4. Se asigna la tarea 3 a la posicin 4.
F(K) =4, F(I) =F(K) 1=3. Fusionamos K con L








1 2 3 4 5
res[]

Cuarto intento: J
4
=2. Se asigna la tarea 4 a la posicin 2.
F(K) =2, F(I) =F(K) 1=1. Fusionamos K con L











1 2 3 4 5
res[]





0 0 0 2 1
0 0 3 2 1
0 4 3 2 1
0 1 3 2
4
5
3
4
5
2 0 1
3
4
5
2
0 1

Ejercicios tema 6 Curso 2007-08 Pgina 29 de 55

Quinto intento: J
5
=1. Se asigna la tarea 5 a la posicin 1.
F(K) =1, F(I) =F(K) 1 =0. Fusionamos K con L












1 2 3 4 5
res[]

El algoritmo termina cuando ya no queda ninguna estructura de particin libre para asignar
tareas.
Por tanto, haciendo el cambio de i a o

quedara el resultado total as:

1 2 3 4 5
res[]

NOTA DEL AUTOR: Este ejercicio est reescrito tomando como base la solucin aportada del
mismo.

Febrero 2005-2 (ejercicio 3)
Enunciado: Demuestra por induccin que el algoritmo de Dijkstra halla los caminos mnimos
desde un nico origen hasta todos los dems nodos del grafo
Respuesta:
Esta solucin es totalmente dada en el libro, y hecho en el resumen del tema. Demostraremos
por induccin matemtica que:
a) Si un nodo i 1 est en S, entonces [i] da la longitud del camino ms corto desde el
origen hasta i, y
b) Si un nodo y no est en S, entonces [i] da la longitud del camino especial ms corto
desde el origen hasta i.
Base: Inicialmente, solo el nodo 1, que es el origen, se encuentra en S, as que la
situacin a) es cierta sin ms demostracin. Para los dems nodos, el nico camino
especial desde el origen es el camino directo y D recibe valores iniciales en
consecuencia. Por tanto, la situacin b) es tambin cierta cuando comienza el
algoritmo.
Hiptesis de induccin: La hiptesis de induccin es que tanto la situacin a) como la
b) son vlidas inmediatamente antes de aadir un nodo v a S (conjunto de nodos
seleccionados). Detallamos los pasos de induccin por separado para ambas
situaciones.
5 4 3 2 1
5 4 1 9 8
3
4
5
2
0
1

Ejercicios tema 6 Curso 2007-08 Pgina 30 de 55


Origen
Paso de induccin para la situacin a): Para todo nodo que ya est en S antes de aadir
v no cambia nada, as que la situacin a) sigue siendo vlida. En cuanto al nodo v,
ahora pertenecer a S. Antes de aadirlo a S, es preciso comprobar que D[v]
proporcione la longitud del camino ms corto que va desde el origen hasta v. Por
hiptesis de induccin, nos da ciertamente la longitud del camino ms corto. Por
tanto, hay que verificar que el camino ms corto desde el origen hasta v no pase por
ninguno de los nodos que no pertenecen a S.
Supongamos lo contrario; supongamos que cuando se sigue el camino ms corto
desde el origen hasta v, se encuentran uno o ms nodos (sin contar el propio v) que no
pertenecen a S. Sea x el primer nodo encontrado con estas caractersticas. Ahora el
segmento inicial de esa ruta, hasta llegar a x, es una ruta especial, as que la distancia
hasta x es D[x], por la parte b) de la hiptesis de induccin. Claramente, la distancia
total hasta v a travs de x no es ms corta que este valor, porque las longitudes de las
aristas son no negativas. Finalmente, D[x] no es menor que D[v], porque el algoritmo
ha seleccionado a v antes que a x. Por tanto, la distancia total hasta v a travs de x es
como mnimo D[v] y el camino a travs de x no puede ser ms corto que el camino
especial que lleva hasta v.
Grficamente, sera:
x El camino ms corto




S
v
El camino especial ms corto

Paso de induccin para la situacin b): Considrese ahora un nodo w, distinto de v, que
no se encuentre en S. cuando v se aade a S, ha dos posibilidades para el camino
especial ms corto desde el origen hasta w:
1. O bien no cambia.
2. O bien ahora pasa a travs de v.
En el segundo caso, sea x el ltimo nodo de S visitado antes de llegar a w. La longitud
de este camino es [x] +I[x,w]. Parece a primera vista que para calcular el nuevo
valor de [w] deberamos comparar el valor anterior de [w] con [x] +I[x,w] para
todo nodo x de S (incluyendo a v). Sin embargo, para todos los nodos x de S salvo v,
esta comparacin se ha hecho cuando se aadi x a S y [x] no ha variado desde
entonces. Por tanto, el nuevo valor de [w] se puede calcular sencillamente
comparando el valor anterior con [:] +I[:,w].
Puesto que el algoritmo hace esto explcitamente, asegura que la parte b) de la
induccin siga siendo cierta tambin cuando se aade a S un nuevo nodo v.
Para completar la demostracin de que el algoritmo funciona, obsrvese que cuando se
detenga el algoritmo, todos los nodos menos uno estarn en S. En ese momento queda
claro que el camino ms costo desde el origen hasta el nodo restante es un camino
especial.

Ejercicios tema 6 Curso 2007-08 Pgina 31 de 55


Febrero 2006-1 (ejercicio 3)
Enunciado: Dado el siguiente grafo, rellenar la tabla adjunta indicando paso a paso como el
algoritmo de Dijkstra encuentra todos los caminos mnimos de menor coste desde el nodo 1.

5 2
1
3 6
11 1


Respuesta:
Nodos Nodos no Vector de Vector de
Paso seleccionados seleccionados distancias predecesores
2 3 4 5
Inicializacin {1} {2,3,4,5} [3,,5,] [1,,1,]
1 {1,2} {3,4,5} [3,9,4,14] [1,2,2,2]
2 {1,2,4} {2,3} [3,6,4,14] [1,4,2,2]
3 {1,2,3,4} {2} [3,6,4,7] [1,4,2,3]

En ejercicios anteriores no hemos puesto los nodos seleccionados como en este ejercicio, pero
es otra interpretacin perfectamente vlida (de hecho no estoy segura que sea la oficial,
aunque en la interpretacin anterior seguimos la del libro de Brassard). Al igual que en
ejercicios anteriores el paso de inicializacin el vector de predecesores cambia con respecto a
la solucin oficial (insistimos u oficiosa), en la que no hay conexin directa, entre los nodos 1
al 3 ni el 1 al 5, por eso en el vector de predecesores est indicada esta unin con .

Febrero 2006-2 (ejercicio 2)
Enunciado: Sea el famoso problema de la mochila. Se dispone de n objetos y una mochila. Para
i =1,2,.n el objeto i tiene un peso positivo w

y un valor positivo :

. La mochila puede
llevar un peso que no sobrepase W. El objetivo es llenar la mochila de tal manera que se
maximice el valor de los objetos almacenados, respetando la limitacin de peso impuesta.
Indique que esquema considera ms adecuada para resolver este problema en los siguientes
casos:
a) Los objetos se pueden fraccionar, luego se puede decidir llevar una fraccin x

del
objeto i, tal que 0 x

1 para 1 i n.
b) Los objetos no se pueden fraccionar, por lo que un objeto puede o no ser aadido,
pero en este ltimo casi, solo se aade 1.
Adems de nombrar el esquema o esquemas, explica el porqu de su eleccin, los aspectos
destacados de cmo resolveras el problema y el coste asociado. No se piden los algoritmos.
Respuesta:
En el caso a) se puede utilizar el esquema voraz, ya que existe una funcin de seleccin que
garantice obtener una solucin ptima. La funcin de seleccin consiste en considerar los
1
2 3
4
5

Ejercicios tema 6 Curso 2007-08 Pgina 32 de 55

objetos por orden decreciente de

i
w
i
. El coste est en 0(n log(n)), incluyendo la ordenacin
de los objetos.
En el caso b) no se puede utilizar el esquema voraz, ya que no existe una funcin de seleccin
que garantice obtener una solucin ptima. Al ser un problema de optimizacin se puede
utilizar el esquema de ramificacin y poda. Se podran seleccionar los elementos en orden
decreciente de

i
w
i
. As, dado un determinado nodo, una cota superior del valor que se puede
alcanzar siguiendo por esa rama se puede calcular suponiendo que la mochila la rellenamos
con el siguiente elemento siguiendo el orden decreciente de

i
w
i
.
El coste en el caso peor seria de orden exponencial, ya que en el rbol asociado al espacio de
bsqueda, cada nodo tendr dos sucesores que representarn si el objeto se aade o no a la
mochila, es decir, 0(2
n
). Sin embargo, sera de esperar que, en la prctica, el uso de la cota
superior para podar reduzca el nmero de nodos que se exploran.

Febrero 2006-2 (ejercicio 3) (parecido a ejercicio 3 de Febrero 2008-1)
Enunciado: Un dentista pretende dar servicio a n pacientes y conoce el tiempo requerido por
cada uno de ellos, siendo t

, i =1,2,,n el tiempo requerido por el paciente i. El objetivo es

minimizar el tiempo total que todos los clientes estn en el sistema, y como el nmero de
pacientes es fijo, minimizar la espera total equivale a minimizar la espera media. Se pide:
1. Identificar una funcin de seleccin que garantice que un algoritmo voraz puede
construir una planificacin ptima.
2. Hacer demostracin de la optimalidad de dicha funcin de seleccin.

Respuesta:
Para la pregunta nmero 1 tendremos que este problema es uno de minimizacin del tiempo
en el sistema. Para minimizar el tiempo total de los clientes tendremos que cogerlos por orden
creciente de tiempos, es decir, atenderemos al cliente de menor tiempo de espera antes que
al del mayor. Esta ser nuestra funcin de seleccin de este problema.
Para la pregunta nmero 2 veremos la siguiente demostracin, la cual es una de las ms
importantes que se dan en este tema, por lo que nos fijaremos muy bien en ella:
Sea P =p
1
p
2
p
n
cualquier permutacin de enteros del 1 al n y sea s

=t
p
. Si se sirven
clientes en el orden P, entonces el tiempo requerido por el j-simo cliente que haya que servir
ser s
]
y el tiempo transcurrido en el sistema por todos los clientes es:
I(P) =s
1
+(s
1
+s
2
) +(s
1
+s
2
+s
3
) ++(s
1
+s
2
+s
3
++s
n
) =
=n s
1
+(n 1) s
1
++2 s
n-1
+s
n
=
= (n k +1) s
k
n
k=1
.
Supongamos ahora que P no organiza a los clientes por orden de tiempos crecientes de
servicio. Entonces, se pueden encontrar dos enteros a y b con o <b y s
u
>s
b
. Es decir, se
sirven al cliente a-simo antes que al b-simo, aun cuando el primero necesite ms tiempo de
servicio que el segundo. Sera algo as:
1o 1 o o +1b 1 b b +1n
P



Ejercicios tema 6 Curso 2007-08 Pgina 33 de 55

Si intercambiamos la posicin de esos dos clientes, obtendremos un nuevo orden de servicio o
permutacin P, que es simplemente el orden P despus de intercambiar p
u
y p
b
:
1a-1 a a+1b-1 b b+1n
P



P

El tiempo total transcurrido pasado en el sistema por todos los clientes si se emplea la
planificacin P es:
I(P) =(n o +1) s
b
+(n b +1) s
u
+ (n k +1)
n
k=1
k=u,b
s
k

La nueva planificacin es preferible a la vieja, porque:
I(P) I(P
i
) =(n o +1) (s
u
s
b
) +(n b +1) (s
b
s
u
) =
= (b o)
_____
>0
(s
u
s
b
)
_______
>0
>0
Se observa tras el intercambio que los clientes salen en su posicin adecuada, ya que s
b
<s
u

por nuestra suposicin inicial, estando el resto ordenados. Por tanto, P es mejor que P en
conjunto.
De esta manera, se puede optimizar toda planificacin en la que se sirva a un cliente antes que
requiera menos servicio. Las nicas planificaciones que quedan son aquellas que se obtienen
poniendo a los clientes por orden creciente de tiempo de servicio. Todas las planificaciones
son equivalentes y, por tanto, todas son ptimas.
NOTA DEL AUTOR: Este ejercicio se parece mucho al nmero 3 de Febrero 2008-1, aunque en
ese caso sera de unos fontaneros que quieren minimizar el tiempo de atencin del cliente
para que las ganancias sean mximas. Se hara exactamente igual, incluso la demostracin de
optimalidad.

Diciembre 2006 (ejercicio 3)
Enunciado: Dado el grado de la figura, aplica el algoritmo de Dijkstra para hallar los caminos
ms cortos desde el nodo 1 hasta uno de los otros nodos, indicando en cada paso: nodos
seleccionados, nodos no seleccionados, vector de distancias y vector de nodos precedentes.

10
13
26 7

5
8




1
3 2
4 5

Ejercicios tema 6 Curso 2007-08 Pgina 34 de 55

Respuesta: Estos ejercicios se hacen exactamente igual a los que hemos visto previamente, as
que pondremos el cuadro con los datos que nos solicitan:
Nodos Nodos no Vector de Vector de
Paso seleccionados seleccionados distancias predecesores
2 3 4 5
Inicializacin {1} {2,3,4,5} [13,26,,5] [1,1,,1]
1 {1,5} {2,3,4} [13,26,13,5] [1,1,5,1]
2 {1,2,5} {3,4} [13,23,13,5] [1,2,5,1]
3 {1,2,4,5} {3} [13,20,13,5] [1,4,5,1]

La solucin proporcionada es del autor totalmente, por lo que no se asegura que est correcta.

Febrero 2007-2 (ejercicio 3)
Enunciado: aplicar el algoritmo de Kruskal al siguiente grafo indicando claramente en cada
paso que arista se selecciona, la evolucin de las componentes conexas y la evolucin de la
solucin.

3 8
4
5 6

1 2 9 10

7

Respuesta: Ordenamos las aristas por orden creciente de coste (de menor a mayor):
|{3,5},{2,5},{1,3},{1,2},{2,3},{2,4},{5,6},{1,4},{2,6},{4,6}|
En la solucin que tengo, sale que las aristas estn entre parntesis (), en vez de entre
corchetes {}como se ha resuelto este ejercicio. Si hiciera falta solo hay que modificar el uso de
estos signos y adaptarlo a la solucin y cambiarlos.
Siguiendo el algoritmo ser:
Arista Componentes
Paso seleccionada conexas Solucin
Inicializacin - {1},{2},{3},{4},{5},{6}
1 {3,5} {1},{2},{3,5},{4},{6} |{3,5}|
2 {2,5} {1},{2,3,5},{4},{6} |{3,5},{2,5}|
3 {1,3} {1,2,3,5},{4},{6} |{3,5},{2,5},{1,3}|
4 {1,2} Rechazada, por estar en el mismo conjunto
5 {2,3} Rechazada, por estar en el mismo conjunto
6 {2,4} {1,2,3,4,5},{6} |{3,5},{2,5},{1,3},{2,4}|
7 {5,6} {1,2,3,4,5,6} |{3,5},{2,5},{1,3},{2,4},{5,6}|
Finaliza el problema, ya que existe una nica componente conexa.
1
2
3 4
5 6

Ejercicios tema 6 Curso 2007-08 Pgina 35 de 55

Septiembre 2008-reserva (ejercicio 3)
Enunciado: Aplique el algoritmo de Prim al siguiente grafo empezando por el nodo 1. Indique
claramente en cada paso qu arista se selecciona, y la evolucin de la solucin.

3 8
4


7 6 10 8

4


1 3



Respuesta: Hemos visto en muchos ejercicios anteriores como se resuelven este tipo de
problemas, por lo que lo dejaramos pendiente de resolucin. Simplemente, es seguir el
procedimiento de este algoritmo.





















1
2
3 4
5
6

Ejercicios tema 6 Curso 2007-08 Pgina 36 de 55

2 parte. Problemas de exmenes solucionados:
Tendremos en cuenta los pasos a seguir para resolver problemas:
Eleccin del esquema (voraz, vuelta atrs, divide y vencers).
Identificacin del problema con el esquema.
Estructura de datos.
Algoritmo completo (con pseudocdigo).
Estudio del coste.

Antes de ver los ejercicios decir que el esquema nos basaremos en los del libro de teora, de
Brassard, que como diferencia ms importante es que existe una funcin que es factible,
mientras que en el libro de prctica es completable. Ambas hacen la misma funcin, pero nos
seguiremos basando en el libro de teora.
Hay ejercicios que hemos modificado, sobre todo el cdigo del algoritmo completo, ya que no
cuadran la solucin dada, por lo que lo especificaremos cuando llegue ese caso en el ejercicio.
Al ser problemas con voraces, tendremos que realizar una demostracin de optimalidad y si
existe lo pondremos en la eleccin el esquema, por ser ms lgico ponerlo as (lo estimo yo).

Febrero 1996-1 (problema 2) (igual a 2.4 libro de problemas resueltos)
Enunciado: Un recubrimiento R de vrtices de un grafo no dirigido 0 =N,A es un conjunto
de vrtices tales que cada arista del grafo incide en, al menos, un vrtice de R. Disear un
algoritmo que, dado un grafo no dirigido, calcule un recubrimiento de vrtices de tamao
mnimo.
Respuesta:
1. Eleccin razonada del esquema
El esquema voraz se adapta perfectamente al problema, ya que:
Se trata de un problema de optimizacin: No slo hay que encontrar un
recubrimiento, sino que ste ha de ser de tamao mnimo.
De entre un conjunto de vrtices (candidatos) hay que seleccionar un subconjunto
que ser la solucin. Solo hay que encontrar la funcin de seleccin adecuada (si
existe) para resolver el problema mediante un algoritmo voraz.
El esquema de divide y vencers es descartable, pues no hay forma obvia de dividir el
problema en subproblemas idnticos cuyas soluciones puedan combinarse en una
solucin global. El esquema de vuelta atrs es un esquema muy general y casi siempre
muy costoso que no debemos usar si podemos dar un algoritmo voraz que resuelva el
problema.

2. Esquema general e identificacin con el problema
El esquema voraz se aplica a problema de optimizacin. Consiste en ir seleccionando
elementos de un conjunto de candidatos que se van incorporando a la solucin. Se
caracterizan porque nunca se deshace una decisin ya tomada: los candidatos desechados
no vuelven a ser considerados y los incorporados a la solucin permanecen en ella hasta
al final del algoritmo.
Es crucial determinar la funcin de seleccin adecuada que nos asegure que la solucin
obtenida es ptima.


Ejercicios tema 6 Curso 2007-08 Pgina 37 de 55

Esta notacin algortmica puede escribirse as (libro de Brassard pgina 214):
funcion voraz (C: Conjunto): conjunto
{ C es el conjunto de candidatos }
S { Construimos la solucin en el conjunto S }
mientras C 0 y solucin (S) hacer
x sclcccionor (C)
C C\ {x};
si factible (S {x}) entonces S S {x}
si solucin (S) entonces devolver S
si no devolver no hay solucin
El esquema general para el libro de problemas es:
fun voraz (C: Conjunto) dev (S:conjunto)
S
mientras solucin (S) y C hacer
x clcmcnto quc moximizo ob]cti:o (x)
C C\ {x};
si completable (S {x}) entonces
S S {x};
fsi
fmientras
dev S
ffun
donde:
C: Conjunto de vrtices del grafo.
S: Recubrimiento del grafo.
La forma ms intuitiva de garantizar que el recubrimiento sea mnimo es tomar vrtices
de los que salgan muchas aristas, esto es, elegir vrtices con mayor grado.
La funcin de seleccin debe escoger el candidato con ms vrtices de los que aun estn
en el conjunto de candidatos. Para ello, cada vez que seleccionemos un vrtice tendremos
que disminuir en uno el grado de cada uno de los vrtices candidatos con el. Hay que
seguir los siguientes pasos:
1 Elegir el vrtice de mayor grado.
2 Recorrer su lista asociada (aquellos vrtices con los que est conectado) y restar 1
al grado de cada uno de ellos en el campo correspondiente en el vector de vrtices.
De esta forma, cuando el grado de todos los candidatos sea cero todas las aristas del grafo
tocan al conjunto de seleccin y ser, por tanto, un recubrimiento.
Segn este criterio, las funciones del esquema principal tendrn el siguiente significado:
solucin(S): Todas las aristas del grafo tocan al menos un vrtice de S.
objetivo(x): Grado del vrtice.
factible(S) (o completable): Siempre es cierto, ya que se selecciona cada vez un
nico vrtice correcto.




Ejercicios tema 6 Curso 2007-08 Pgina 38 de 55

En estos problemas aadimos la demostracin de optimalidad, que ser la siguiente:
Este problema es un ejemplo de que los algoritmos voraces, en determinadas ocasiones,
no proporcionan la solucin ptima, aunque si una buena aproximacin a la misma.
Ocurre tambin en el ejemplo que se cita en el captulo de metodologa del texto con el
algoritmo de devolucin de monedas en el sistema britnico antiguo.
Aunque la intuicin nos indique, a veces una heurstica que no puede fallar, un sencillo
contraejemplo nos puede hacer ver ms claramente lo dificultoso, a veces, del estudio de
algoritmia. Se deja al lector que busque dicho contraejemplo para este caso.

3. Estructuras de datos
En el problema intervienen grafos, vrtices de un grafo y conjunto de vrtices. Para
representar el grafo podemos utilizar cualquiera de las dos formas habituales, teniendo
en cuenta que el uso de la matriz de adyacencia har menos eficiente el algoritmo. Aqu
representar el grafo como un vector de vrtices, teniendo asociado cada vrtice una lista
enlazada con los vrtices adyacentes a ste. Como los costes no juegan ningn papel en el
algoritmo, lo excluiremos (por comodidad) de la estructura de datos.
grafo =vrtice [1..N] de vrtice
vertice =tupla
indice: entero // Posicin en el vector
grado: entero // Grado del vrtice
adyacentes: apuntador a nodo_adyacente
nodo_adyacente =tupla
adyacente: entero
siguiente: apuntador a nodo_adyacente

4. Algoritmo completo a partir del refinamiento del esquema
Adaptamos el algoritmo general a lo dicho anteriormente:
fun recubrimiento-mnimo (G:grafo) dev (S: conjunto de vrtices)
S
mientras C 0 y solucin (S) hacer
x sclcccionor (C) // Elemento que maximiza objetivo (x)
C C\ {x};
disminuir_grado (x,C)
fmientras
dev S
ffun








Ejercicios tema 6 Curso 2007-08 Pgina 39 de 55

Las funciones son las siguientes:
Solucin: El conjunto S ser una solucin cuando el grado de todos los elementos que
restan en C ser cero. Ser en pseudocdigo as:
fun solucin (C: Conjunto de vrtices) dev (b:booleano)
b cicrto
para c en C hacer
b b onJ ([Link] =0)
fpara
dev b
ffun
Tal como comentbamos anteriormente, algunas soluciones aportadas en estos ejercicios
no cuadran, debido a sintaxis, debido a que no es entendible, etc. En este caso, es una
de ellas, ya que dentro del bucle para hay un bucle si que no comprendo muy bien
que hace, por lo que calculamos la variable b (que es un booleano) para averiguar si es
solucin o no. Cabe destacar que la solucin no es ma personal, la aport otro compaero
en los cursos virtuales, por ello gracias ;)
La funcin de seleccin devuelve el grado del vrtice en consideracin:
fun seleccionar (v: vertice) dev (g:entero)
dev [Link]
ffun
Es otra funcin modificada, ya que devuelven vrtice, cuando debera ser (creo yo)
[Link], que es el parmetro dado en la funcin.
Por ltimo, la funcin disminuir-grado resta 1 al grado de todos los elementos conectados
con el vrtice elegido:
fun disminuir_grado(v: vrtice, C: conjunto de vertices)
para w C en sucesores (v) hacer
[Link] [Link] 1
fpara
ffun

5. Anlisis del coste
El tamao del problema viene dado por el nmero de vrtices del grafo. El nmero de
veces que se ejecuta el bucle voraz es, en el peor de los casos, n. Dentro del bucle se
realizan dos operaciones:
Encontrar el vrtice de mayor grado, que tiene un coste lineal.
Disminuir en uno el grado de los dems, que tiene tambin coste lineal.
De modo que el coste del bucle es 0(n) y el coste del algoritmo es O(n
2
).






Ejercicios tema 6 Curso 2007-08 Pgina 40 de 55

Septiembre 1996 (problema 1) (igual a 2.3 libro de problemas resueltos)
Enunciado: Un cartgrafo acaba de terminar el plano de su pas, que incluye informacin sobre
las carreteras que unen las principales ciudades y sus longitudes. Ahora quiere aadir una tabla
que se recoja la distancia entre cada par de ciudades del mapa (entendiendo por distancia la
longitud del camino ms corto entre las dos). Escribir un algoritmo que permita realizar esta
tabla.
Repuesta:
1. Eleccin razonada del esquema algortmico
Para hallar la distancia mnima desde un vrtice de un grafo a cada uno de los dems
vrtices contamos con el algoritmo voraz de Dijkstra. Basta, pues, con aplicarlo para cada
una de las ciudades, siendo stas los vrtices, las carreteras las aristas del grafo y sus
longitudes los pesos de las aristas.
CUIDADO: No hay que confundir este problema (de caminos mnimos) con el problema
de dar un rbol de expansin mnimo, que resuelven algoritmos como el de Prim o
Kruskal. En este caso, un rbol de expansin mnimo seria un subconjunto de carreteras
que conectara todas las ciudades y cuya longitud total fuera mnima; pero esa condicin
no nos asegura que la distancia entre cada par de ciudades sea la menor posible.

2. Descripcin del esquema usado e identificacin con el problema
Tendremos el esquema general voraz:
funcion voraz (C: Conjunto): conjunto
{ C es el conjunto de candidatos }
S { Construimos la solucin en el conjunto S }
mientras C 0 y solucin (S) hacer
x sclcccionor (C)
C C\ {x};
si factible (S {x}) entonces S S {x}
si solucin (S) entonces devolver S
si no devolver no hay solucin
De nuevo hemos escrito el esquema general que viene del libro de teora, aunque como
hemos dicho antes dara igual cual de los esquemas escribir, ya que haran lo mismo
ambos.
El algoritmo de Dijkstra opera como sigue:
En un principio, el conjunto de candidatos son todos los nodos del grafo.
En cada paso, seleccionamos el nodo de C cuya distancia al origen es mnima y lo
aadimos a S. En cada fase del algoritmo, hay una matriz D que contiene la longitud
del camino especial ms corta que va hasta cada nodo del grafo (llamaremos especial
a un camino en el que todos los nodos intermedios pertenecen a S).
Cuando el algoritmo termina, los valores que hay en D dan los caminos mnimos
desde el nodo origen a todos los dems.





Ejercicios tema 6 Curso 2007-08 Pgina 41 de 55

El algoritmo es el siguiente:
fun Dijkstra (g:grafo) dev (vector[1..n])
:cctor[1..n]
C {2,3,,n}
para i 2 hasta n hacer [i] costc(1,i,g)
mientras C hacer
: elemento de C que minimiza [:]
C eliminar (v, C)
para cada w C hacer
[w] min([w],[:] +costc(:,w,g))
fpara
fmientras
dev S
ffun

3. Estructuras de datos
El conjunto de ciudades y carreteras viene representado por un grafo no orientado con
pesos. Podemos implementarlo como una matriz de adyacencia, lista de listas de
adyacencias, o como sea necesario.
Adems, necesitaremos otra matriz que acumule las distancias mnimas entre ciudades y
que sirva como resultado.

4. Algoritmo completo a partir del refinamiento del esquema general
La nica variacin respecto al algoritmo de Dijkstra es que necesitamos saber la distancia
mnima entre cada par de ciudades, no solo entre una ciudad y todas las dems. Por ello,
es necesario aplicar Dijkstra n veces, siendo n el nmero de ciudades (en rigor, no es
necesario aplicarlo sobre la ltima ciudad, pues los caminos mnimos a esa ciudad ya que
han sido obtenidas en aplicaciones anteriores):
fun mapa (g:grafo) dev (vector[1..N,1..N] de entero)
m :cctor[1..N,1..N]
para cada vrtice v hacer
m Ji]kstro(g,:,m)
fpara
dev m
ffun
donde el algoritmo de Dijkstra se implementa mediante una funcin i]kstro (g,:,m)
que devuelve una matriz m con la informacin aadida correspondiente a las distancias
entre el grafo v y todos los dems grafos de g.

5. Estudio del coste
El coste del algoritmo depende de la implementacin para grafos que se escoja. Si se
implementa como una matriz de adyacencia, sabemos que el coste del algoritmo de
Dijkstra es cuadrtico (0(n
2
)). Como hemos de aplicarlo n veces (o n 1 veces, que es
de orden n), el coste del algoritmo completo es O(n
3
).

Ejercicios tema 6 Curso 2007-08 Pgina 42 de 55

Septiembre 1996-reserva (problema 2) (igual a 2.5 libro de problemas resueltos)
Enunciado: Se planea conectar entre s todos los pueblos de una cierta regin mediante
carreteras que sustituyan los antiguos caminos vecinales. Se dispone de un estudio que
enumera todas las posibles carreteras que podran construirse y cul sera el coste de construir
cada una de ellas. Encontrar un algoritmo que permita seleccionar de entre todas las
carreteras posibles, un subconjunto que conecte todos los pueblos de la regin con un coste
global mnimo.
Respuesta:
1. Eleccin razonada del esquema algortmico
Si interpretamos los datos como un grafo en el que los pueblos son los vrtices y las
carreteras son las aristas, cuyos pesos son el coste de construccin, el problema no es
otro que el de hallar un rbol de expansin mnimo para ese grafo. En efecto, un rbol de
expansin mnimo es un conjunto de aristas que conecta todos los vrtices del grafo en el
que la suma de los pesos es mnima (por tanto, el coste de construir el subconjunto de
carreteras es mnimo).
Para resolverlo podemos usar cualquiera de los dos algoritmos voraces estudiados, que
resuelven este problema: el de Kruskal o Prim.

2. Descripcin del esquema usado e identificacin del problema
El esquema voraz se aplica a problemas de optimizacin. Consiste en ir seleccionando
elementos de un conjunto de candidatos que se van incorporando a la solucin. Se
caracteriza porque nunca deshace una decisin ya tomada: los candidatos no vuelven a ser
considerados, y los incorporados a la solucin permanecen en ella hasta el final del
algoritmo. Es crucial determinar la funcin de seleccin apropiada que nos asegura que la
solucin obtenida es ptima.
En notacin algortmica puede describirse as:
funcion voraz (C: Conjunto): conjunto
{ C es el conjunto de candidatos }
S { Construimos la solucin en el conjunto S }
mientras C 0 y solucin (S) hacer
x sclcccionor (C)
C C\ {x};
si factible (S {x}) entonces S S {x}
si solucin (S) entonces devolver S
si no devolver no hay solucin
Para resolver el problema utilizaremos un algoritmo voraz llamado de Prim, que resuelve
el problema de hallar el recubrimiento mnimo de un grafo. En este algoritmo, el rbol de
recubrimiento mnimo crece a partir de una raz arbitraria. En cada fase, se aade una
nueva rama al rbol ya construido, y el algoritmo se detiene cuando se han alcanzado
todos los nodos. En cada paso, el algoritmo busca la arista ms corta posible {u,:}tal que
u pertenece a B (conjunto de nodos) y v pertenece a N menos B. Entonces aade v a B y
{u,:}a S (conjunto de aristas). Las aristas de S forman en todo momento un rbol de
recubrimiento mnimo para los nodos de B.



Ejercicios tema 6 Curso 2007-08 Pgina 43 de 55

fun prim (0 =N,A: grafo, longitud: A R
+
): conj. aristas
S ;
B un elemento arbitrario de N
mientras B N hacer
buscar c ={u,:} de longitud mnima tal que u B y : N/ B
S S {c};
B B {:};
fmientras
devolver T
ffun

3. Estructuras de datos
Son exactamente las mismas que el algoritmo de Prim, pues se puede aplicar
directamente.

4. Algoritmo completo
El algoritmo de Prim no necesita ninguna modificacin posterior.

5. Estudio del coste
De nuevo, el coste es exactamente el del algoritmo de Prim, es decir, O(n
2
).


Febrero 1997-1 (problema 1) (igual a 2.2 libro de problemas resueltos)
Enunciado: Dado un conjunto de n cintas no vacas con n

registros ordenados cada uno, se

pretende mezclarlos a pares hasta lograr una nica cinta ordenada. La secuencia en la que se
realiza la mezcla determinara la eficiencia del proceso. Diseese un algoritmo que busque la
solucin ptima minimizando el nmero de movimientos.
Por ejemplo: 3 cintas: A con 30 registros, B con 20 y C con 10.
1. Mezclamos A con B (50 movimientos) y el resultado con C (60 movimientos), con la
que realiza en total 110 movimientos.
2. Mezclamos C con B (30 movimientos) y el resultado con A (60 movimientos), con la
que realiza en total 90 movimientos.
Hay alguna forma ms eficiente de ordenar el contenido de las cintas?
Respuesta:
1. Eleccin razonada del esquema algortmico
El problema presenta una serie de elementos caractersticos de un esquema voraz:
Por un lado, se tienen un conjunto de candidatos (las cintas) que vamos eligiendo
uno a uno hasta completar determinada tarea.
Por otro lado, el orden de eleccin de dichos elementos determina la optimalidad de
la solucin, de manera que para alcanzar una solucin ptima es preciso seleccionar
adecuadamente al candidato mediante un criterio determinado. Una vez escogido,
habremos de demostrar que nos lleva a una solucin ptima.

Ejercicios tema 6 Curso 2007-08 Pgina 44 de 55

El criterio de eleccin de las cintas para alcanzar una solucin ptima ser el de elegir en
cada momento aquella con menor nmero de registros.
Demostracin de optimalidad:
La demostracin corresponde con la de minimizacin del tiempo en el sistema, dada ya en
ejercicios antes, por lo que evitamos escribirla de nuevo.

2. Descripcin del esquema usado e identificacin con el problema
El esquema voraz es:
funcion voraz (C: Conjunto): conjunto
{ C es el conjunto de candidatos }
S { Construimos la solucin en el conjunto S }
mientras C 0 y solucin (S) hacer
x sclcccionor (C)
C C\ {x};
si factible (S {x}) entonces S S {x}
si solucin (S) entonces devolver S
si no devolver no hay solucin
Hemos de particularizar las siguientes funciones:
Solucin (S): El nmero de cintas, que es n.
Objetivo (x): Funcin que devuelve la cinta con menor nmero de registros de entre
el conjunto de cintas disponibles.
Factible (x) (o completable): Esta funcin es siempre cierta, pues cualquier orden de
combinacin es vlido.

3. Estructura de datos
Se utilizarn vectores de n valores naturales para representar los conjuntos. Por ejemplo,
para el conjunto C se define la variable c como vector de naturales, siendo c[i] =n

la
expresin de que la cinta i consta de n

registros. El conjunto S puede representarse de

manera anloga. Para representar la ausencia de un elemento puede usarse cualquier
marcador (por ejemplo, el valor ).

4. Algoritmo completo a partir del refinamiento del esquema general
Retocando el esquema general tenemos:
fun voraz (C: vector) dev (s:vector)
para i 0 hasta n hacer s[i] 0
i
mientras i n hacer
x sclcccionor (C)
c[i] 0
s[i] x
i i +1;
fmientras
dev S
ffun

Ejercicios tema 6 Curso 2007-08 Pgina 45 de 55

Esta solucin est modificada respecto de la solucin aportada en el libro de problemas. Se
ha aadido una lnea (la de i i +1) y se ha modificado la lnea c[i] 0. Con esto trato
de decir, que no es seguro que est correcta la respuesta, slo que pienso que haba
algunas erratas.
La nica funcin (de seleccin) por desarrollar es aqulla que obtiene en cada momento la
cinta con menor nmero de registros de entre las cintas no usadas todava y almacenadas
en el vector de cintas. La funcin devuelve la cinta, pero no la elimina del conjunto de
candidatos. Los argumentos son c, vector de cintas y cinta que es un vector de n

registros.
fun seleccionar (c: vector) dev (cinta:vector)
min 1
para ] 1 hasta n hacer
si c[]] <c[min] entonces min ] // Escoge la de menor tamao
fsi
fpara
dev c[min]
ffun

5. Estudio del coste
La funcin objetivo (para nosotros seleccionar) tiene coste de 0(n) y el bucle principal
(mientras) se repite n veces, por lo que el coste es O(n
2
).

Problema 2.2 del libro de problemas resueltos (sin correspondencia con ningn ejercicio de
examen)
Enunciado: Consideramos un conjunto de programas p
1
,p
2
,,p
n
que ocupan un espacio en
cinta l
1
,l
2
,,l
n
. Disear un algoritmo para almacenarlos en una cinta de modo que el tiempo
medio de acceso sea mnimo.
Respuesta:
1. Eleccin razonada del esquema algortmico
Si un programa p

ocupa la posicin x

el tiempo de acceso a ese programa es la suma del

tiempo que se tarda en avanzar la arista hasta x

y, a continuacin, seguir leyndola hasta

l

. Es decir:
t

=k (x

+l

)
donde la constante k no afecta al resultado.
El tiempo medio de acceso es:
I =
(x
i
+I
i
)
i
N

El problema se ajusta al esquema voraz: podemos considerar los programas como
candidatos que hay que ir seleccionando en el orden adecuado. Cada orden posible nos da
una solucin y buscamos entre ellas la solucin ptima.
Si tomamos como funcin de seleccin el escoger el programa ms corto de los que an no
han sido colocados, el esquema voraz resuelve el problema. Un punto clave, para no
confundir los problemas voraces con los de backtracking es asegurarse de que no es
necesario deshacer decisiones ya tomadas. Debemos hacer una demostracin de
optimalidad para el algoritmo, una vez especificado, para asegurarnos de este extremo.

Ejercicios tema 6 Curso 2007-08 Pgina 46 de 55

Demostracin de optimalidad
Hemos cambiado la demostracin de optimalidad a su sitio idneo dentro del problema. El
tiempo medio de acceso del sistema T es:
I =
(x
i
+I
i
)
i
N
=
_[ I
]
i
]=1
+I
i
]
i
N
=l
1
+
n-1
n
l
2
+
n-2
n
l
3
++
1
n
l
n
.
Hemos tenido en cuenta que x

es la suma de las longitudes de los programas que estn

antes de p

, es decir, x

= l
]
-1
]=1
.
Para minimizar ese sumatorio es necesario colocar en la primera posicin (l

) el programa
ms corto, para minimizar el factor ms grande l
1
y as sucesivamente. Supongamos que
hubiera dos elementos l

<l
]
con i <]. El sumatorio podra entonces reducirse
intercambiando sus posiciones, as que se disminuir la contribucin al sumatorio del
trmino:

n-+1
n
l

+
n-]+1
n
l
]

Por tanto, en la nica posicin en la que el sumatorio no puede ser reducido es aquella en
la que los programas estn ordenados con longitudes crecientes.

2. Descripcin del esquema usado e identificacin con el problema
El esquema voraz se aplica a problemas de optimizacin. Consiste en ir seleccionando
elementos de un conjunto de candidatos que se van incorporando a la solucin. Se
caracteriza porque nunca deshace una decisin ya tomada: los candidatos ya desechados
no vuelven a ser considerados y los incorporados a la solucin permanecen en ella hasta el
final del algoritmo.
En notacin algortmica:
funcion voraz (C: Conjunto): conjunto
{ C es el conjunto de candidatos }
S { Construimos la solucin en el conjunto S }
mientras C 0 y solucin (S) hacer
x sclcccionor (C)
C C\ {x};
si factible (S {x}) entonces S S {x}
si solucin (S) entonces devolver S
si no devolver no hay solucin
En este caso:
C: Es el conjunto de programas.
S: No es exactamente un conjunto, sino una lista de programas, ya que nos interesa
conservar la informacin sobre el orden en el que los programas fueran incorporados
a la solucin.






Ejercicios tema 6 Curso 2007-08 Pgina 47 de 55

3. Estructuras de datos
Hay dos posibles representaciones:
- El conjunto de programas puede ser implementado mediante un vector que cumpla
C[i] =l

.
- Otra opcin es definir un tipo de datos programa que consista en una etiqueta (un
nmero entero que lo identifica) y una longitud:
tipo programa =tupla
identificador: entero
longitud: entero
Un conjunto de programas puede entonces implementarse mediante una lista de
programas. De esta forma, ese tipo nos servir tambin para implementar S.

4. Algoritmo completo a partir del refinamiento del esquema general
En vista de que tanto la funcin solucin como la factible son triviales, podemos reescribir
el esquema para este problema simplificndolo:
fun voraz (C: conjunto) dev (S: conjunto)
S
mientras C hacer
x elemento que maximiza objetivo (x)
C C\ {x}
S S {x}
fmientras
dev S
ffun
La funcin objetivo devuelve la longitud del programa:
fun objetivo (p: programa) dev entero
dev [Link]
ffun

5. Estudio del coste
El bucle principal se recorre n veces. Dentro del bucle hay estas operaciones:
- Seleccin del candidato adecuado: 0(n)
- Eliminacin del candidato 0(n) si el conjunto es una lista.
- Adicin del candidato seleccionado al conjunto solucin: 0(1)
Tendremos, por tanto, que el coste total es 0(n
2
).
Para mejorar el coste usaremos un montculo invertido o de mnimos, como en ocasiones
anteriores, teniendo en la raz el programa ms corto. Hara estas operaciones:
- Eliminar el programa de C tendra coste 0(log(n)), ser lo que tarde en restaurar
la propiedad del montculo cuando se extrae la raz. Como el bucle se ejecuta n
veces el coste es 0(n log(n)).
- Hay que considerar una nueva instruccin para inicializar el conjunto de
candidatos como un montculo de mnimos, que tiene coste 0(n log(n)).
Por tanto, el coste total del algoritmo es O(n lug(n)).

Ejercicios tema 6 Curso 2007-08 Pgina 48 de 55

Septiembre 2003 (problema)
Enunciado: Una operadora de telecomunicaciones dispone de 10 nodos conectados todos
entre s por una tupida red de conexiones punto a punto de fibra ptica. Cada conexin c(i,])
entre el nodo i y j (con i,] {1..10}) tiene un coste asignado que sigue la frmula c(i,]) =
(i +]) H0 8. La operadora quiere reducir gastos, para lo cual est planificado asegurar la
conectividad de su red de nodos minimizando el coste. Disear un algoritmo que resuelva el
problema y aplicarlo a los datos del enunciado.
Respuesta: Se trata de un grafo dirigido de 10 nodos n
1
,n
2
,,n
10
con una matriz simtrica de
costes:









Se trata de conseguir minimizar el coste de los enlaces asegurando nicamente la conectividad
de la red.
El enunciado describe un problema de optimizacin en el que se nos pide que el grafo sea
conexo (asegurar la conectividad de la red) y contenga un rbol de expansin mnimo (que
el coste sea mnimo), ya que la conectividad se asegura no dejando subgrafos no conexos.

1. Eleccin razonada del esquema algortmico
Con las condiciones descritas podemos usar algoritmos que resuelvan el problema del
rbol de expansin mnimo, dentro de la familia de los algoritmos voraces.

2. Descripcin del esquema usado e identificacin con el problema
Se elige cualquiera de los algoritmos expuestos en el temario, Kruskal o Prim, por ejemplo,
este ltimo, siendo el enunciado informal sacado del resumen el siguiente:
funcion prim (0 =N,A: grafo, longitud: A R
+
): conj. aristas
{ Iniciacin }
I ;
B { un miembro arbitrario de N }
mientras B N hacer
buscar c ={u,:} de longitud mnima tal que u B y : N/ B
I I {c};
B B {:};
devolver T

1 2 3 4 5 6 7 8 9 10
1 - 3 4 5 6 7 0 1 2 3
2 3 - 5 6 7 0 1 2 3 4
3 4 5 - 7 0 1 2 3 4 5
4 5 6 7 - 1 2 3 4 5 6
5 6 7 0 1 - 3 4 5 6 7
6 7 0 1 2 3 - 5 6 7 0
7 0 1 2 3 4 5 - 7 0 1
8 1 2 3 4 5 6 7 - 1 2
9 2 3 4 5 6 7 0 1 - 3
10 3 4 5 6 7 0 1 2 3 -

Ejercicios tema 6 Curso 2007-08 Pgina 49 de 55

Hemos tomado 1 como nodo arbitrario. El conjunto B va a ir conteniendo los nodos del
subgrafo ya conexo y el conjunto T ira teniendo en cada iteracin aquellas aristas del rbol
de expansin mnimo que contiene los nodos de B. El conjunto de candidatos es B, la
condicin de finalizacin es B =N y la funcin de optimizacin es elegir aquella arista del
subgrafo B que conecte con algn nodo de N\ B con menor coste.
Una aplicacin al problema, que hace que se vea con ms claridad porque se ha escogido
el esquema voraz (reubicacin de apartados de la solucin por el autor):
Tenemos los siguientes conjuntos inicialmente B ={1}y la arista mnima entre un nodo de
B y otro de N\B es u =(1,7) con valor 0.
Los valores de B y la u elegida en cada momento evolucionan como sigue:
B ={1,7} u =(7,9) Coste: 0
B ={1,7,9} u =(7,2) Coste: 1
B ={1,2,7,9} u =(2,6) Coste: 0
B ={1,2,6,7,9} u =(6,10) Coste: 0
B ={1,2,6,7,9,10} u =(6,3) Coste: 1
B ={1,2,3,6,7,9,10} u =(3,5) Coste: 0
B ={1,2,3,5,6,7,9,10} u =(6,3) Coste: 0
B ={1,2,3,5,6,7,8,9,10} u =(9,8) Coste: 1
B ={1,2,3,4,5,6,7,8,9,10} u =(9,8) Coste: 1
Coste del rbol de expansin mnimo: 4
NOTA DEL AUTOR: Con calma he visto este ejercicio y veo que esta aplicacin es algo rara,
porque vuelve a coger la misma arista, lo cual segn el algoritmo voraz no puede ocurrir
nunca, por llegar a ciclos. No entiendo, por tanto, esta aplicacin.

Pondremos la demostracin de optimalidad a continuacin:
El algoritmo de Prim encuentra la solucin ptima. Se puede demostrar por induccin
sobre T que aadir la arista ms corta {c}que sale de T forma en I {c}un rbol de
recubrimiento mnimo que contendr al final n 1 aristas y todos los nodos del grafo G.
Para esta demostracin tendremos en cuenta este lema (sacado del resumen):
Icmo 6.3.1 Sea 0 =N,A un grafo conexo no dirigido en el cual est dado la
longitud de todas las aristas. Sea B N un subconjunto estricto de los nodos de
G. Sea I A un conjunto prometedor de aristas, tal que no haya ninguna arista
de T que salga de B. Sea v la arista ms corta que sale de B (o una de las ms
cortas si hay empates). Entonces I {:} es prometedor.




Ejercicios tema 6 Curso 2007-08 Pgina 50 de 55

3. Estructuras de datos
El grafo se representara mediante una matriz de costes. La estructura de datos tendr un
mtodo que implementa el clculo de la distancia entre dos nodos. En el caso de esta
implementacin, la distancia entre dos nodos i y j es el valor de la matriz de distancias y su
coste 0(1).

4. Algoritmo completo a partir del esquema general
Tendremos este algoritmo completo a partir del tomado en el punto anterior. Sera la
misma que el algoritmo ms refinado de la teora:
funcion prim (L[1..n,1..n]): conj. aristas
{ Iniciacin: solo el nodo 1 se encuentra en B }
I ; { Contendr las aristas del rbol de recubrim. mnimo }
para i 2 hasta n hacer
mas prximo [i] 1
distmin [i] I[i,1]
{ Bucle voraz }
repetir n 1 veces
min
para ] 2 hasta n hacer
si 0 Jistmin[]] <min entonces min Jistmin[]]
k ]
I I { ms prximo [k], k }
distmin [k] 1
para ] 2 hasta n hacer
si I[],k] Jistmin[]] entonces Jistmin[k] I[],k]
ms prximo []] k
devolver T



5. Coste del algoritmo
El coste del algoritmo de Prim es O(n
2
), que puede mejorarse utilizando una
representacin de montculos para el vector Jistmin[].











Ejercicios tema 6 Curso 2007-08 Pgina 51 de 55

3 parte. Problemas de exmenes sin solucin o planteados:
Febrero 1997-2 (problema 1)
Enunciado: Queremos grabar n canciones de duraciones t
1
,t
2
,,t
n
en una cinta de audio de
duracin I < t

n
=1
.
Disear un algoritmo que permita almacenar el mximo nmero de canciones en el espacio
disponible.
Respuesta: No hay solucin oficial de este ejercicio, por lo que al ser de optimizacin puede ser
o bien un esquema voraz o bien un ramificacin y poda. Hemos tomado parte de la solucin (el
esquema era nuestra duda) del libro de Estructuras de datos y mtodos algortmicos. Ejercicios
resueltos de Narciso Mart, Y. ortega, J.A. Verdejo, ejercicio 12.2.
Por tanto, en este caso, tenemos que en este caso iramos ordenaremos los programas de
menor a mayor tamao y para cada programa grabaremos si entra en el disco. Cuando los
siguientes no caben significa que no entrarn ninguno ms. Recordemos que esta solucin se
haba dado en el tema del problema de la mochila, en el que al verificar la optimalidad (lo ms
importante del esquema voraz) se tena que usar el mtodo de reduccin de diferencias, en el
que se comparaban dos soluciones y se verificaba que diferencias haba entre ellas. Para eso
habra que remontarse a la teora y a los ejercicios que hemos visto previamente.

Febrero 1998-1 (problema 1)
Enunciado: En la compleja red de metro de Japn, la cantidad que se paga por un billete es
proporcional a la distancia que se recorre. Por tanto, es necesario instalar en cada estacin un
panel informativo que informe del precio a cualquier otra estacin de la red. Describir un
algoritmo que deduzca la informacin de todos estos paneles, basando el clculo en la
suposicin de que el viajero se trasladar de una estacin a otra por el camino ms corto.
Respuesta: Este ejercicio nos est hablando del metro de Japn, considerando este como un
grafo, en el que hay que seleccionar las aristas ms cortas. Por ello y sin nimo de equivocarme
estimo que corresponde con el algoritmo de Dijkstra, en el que se calcula la distancia menor
entre cada nodo, seleccionando el camino menor. Recuerda enormemente al problema 2.3 del
libro de problemas resueltos de nuestra bibliografa bsica.

Febrero 1998-2 (problema 1)
Enunciado: Sobre un eje de coordenadas positivo se tienen representados edificios en forma
de rectngulos. Cada rectngulo descansa sobre el eje horizontal y se representa por sus
abscisas inicial y final y por su altura. La lnea de horizonte es el contorno que forman los
edificios. Se pide programar un algoritmo eficiente que encuentre la lnea de horizonte que
forma un conjunto de edificios.
Ejemplo: Una ciudad C ={(0,4,7),(2,14,4),(7,12,5),(8,17,2),(19,21,10)}tendra una lnea
de horizonte E ={(0,4,7),(4,7,4),(7,12,5),(14,17,2),(17,19,0)(19,21,10)}






Ejercicios tema 6 Curso 2007-08 Pgina 52 de 55

Respuesta: No s exactamente el tipo de problema al que pertenece el mismo. Lo he
preguntado y al final hemos llegado a la conclusin que puede ser un voraz. Realmente como
digo no lo tengo nada claro, solo s que los candidatos son los edificios y se trata de un
problema de maximizacin (muy disimulado), ahora explico el porqu de este problema,
representndolo grficamente:
Y

10


5



0 4 7 8 12 14 17 19 21 X

Hemos representado el ejemplo anterior. Pasamos a explicar que es cada valor:
- La primera cifra es el eje de abscisas inicial, es decir, donde empieza el rectngulo del
edificio.
- La segunda cifra es el eje de abscisas final, es decir, donde finaliza el rectngulo del
edificio.
- La ltima cifra es la altura del edificio.

Resaltaremos con negrita el contorno que nos piden que hagamos.
Y

10


5



0 4 7 8 12 14 17 19 21 X
Esto que hemos resaltado es el contorno solucin que nos han dado en el enunciado.
Como he puesto anteriormente no tengo nada claro que el esquema sea el voraz, ya que no
veo ni la funcin de seleccin que haga el contorno ni nada as, grafo descartado (supongo),
porque no lo parece. En conclusin, que no sabra cmo se resolvera, pero al menos queda
para estrujarnos la cabeza.

Ejercicios tema 6 Curso 2007-08 Pgina 53 de 55

Una posible solucin podra ser ordenar las alturas por orden creciente y verlas, pero me temo
que es algo as como escoger la mayor longitud de los edificios de entre dos que se solapen,
como pueden ser los edificios (7,12,5) y (8,17,2).

Septiembre 1998 (problema 1)
Enunciado: Dado un conjunto de n rectngulos cuyos lados son paralelos a los ejes del plano,
hallar el rectngulo interseccin de todos los rectngulos mediante un algoritmo eficiente.
Respuesta: Este ejercicio se parece mucho al anterior, el de los rectngulos. Lo hemos puesto
separado, ya que el enunciado en cierta manera es distinta. De nuevo, no resolveremos este
ejercicio, y nos remontaremos al anterior.

Septiembre 1998 (problema 2)
Enunciado: Una cadena euleriana en un grado no orientado es una cadena que une cada arista
del grafo exactamente una vez. Escribir un algoritmo que decida si un grafo dado tiene una
cadena euleriana y, si es as, que devuelva esa cadena.
Respuesta: Este ejercicio se asemeja bastante al problema 2.4 del libro de problemas, en el
que se nos peda un recubrimiento mnimo. De hecho, hemos puesto separado este ejercicio,
como en otras ocasiones por el enunciado que aunque realmente piden lo mismo suena a
distinto y as se hace ms rico el estudio de los problemas.

Febrero 2000-2 (problema)
Enunciado: La Base Area de Gando (Gran Canaria) posee una flota variada de n cazas de
combate c

(con i {1..n}). Cada caza tiene que salir del bunker y esperar un tiempo de
rodadura k

ms un tiempo despegue t

para estar en el aire y operativo. Durante este proceso

la nave es vulnerable. Suponiendo que se produce un ataque sorpresa, construir un algoritmo
que averige el orden de despegue de las aeronaves de manera que se minimice el tiempo
medio durante el cual son vulnerables.
Supongamos ahora que cada aeronave c

posee un ndice acumulativo b

de importancia
estratgica siempre que despegue antes de la ranura temporal

(con i {1..n}). si
queremos maximizar la importancia estratgica una vez que hayan despegado todas. Qu
tipo de problema es ste? Con que esquema se resuelve? Explica en un prrafo breve el
funcionamiento del algoritmo.
Respuesta: Este ejercicio es el tpico con dos partes, que se resuelven empleando distintos
esquemas algortmicos, aunque son de distintos temas los veremos juntos (por no separar el
enunciado). En este caso, el primero de ellos es un esquema voraz, en el que como hemos
visto en este tema numerosas ocasiones se empleara para ello la planificacin en tiempo fijo,
ya visto en temas anteriores, por lo que dejaramos el ejercicio para su resolucin posterior.
El segundo de ellos igualmente es un problema de optimizacin, slo que nos dan una ranura
temporal

, adems del tiempo que tarda en despegar cada nave. Este problema, por tanto,
se resolvera empleando un esquema de ramificacin y poda, adems se asemeja mucho al de
Febrero de 2008-1 semana (vase ejercicios tema 9), en la que el to Facundo quiere recopilar
una huertas con el mximo beneficio.



Ejercicios tema 6 Curso 2007-08 Pgina 54 de 55

Febrero 2001-2 (problema)
Enunciado: Se tiene que organizar un torneo con n participantes (con n potencia de 2). Cada
participante tiene que competir exactamente una vez con todos los posibles oponentes.
Adems cada participante tiene que jugar exactamente 1 partido al da. Se pide construir un
algoritmo que permita establecer el calendario del campeonato para que concluya en n 1
das. Sugerencia: Dos grupos disjuntos de m jugadores juegan entre ellos m das mediante
rotacin. Ejemplo: {o,b,c}contra {J,c,} juegan: Da 1: ad, be y cf. Da 2: ae, bf y cd y
finalmente da 3: af, bd y ce.
Respuesta: No estoy segura de la solucin, pero creo que es como el problema 2.4, donde
pedan recubrimiento de vrtices de un grafo. Entiendo que es un grafo con todas las posibles
uniones y cada vez hay una posible arista por da jugado que unira dos equipos distintos. Por
tanto, este ejercicio, al no estar resuelto se deja slo planteado. Por ello, estimo que se usara
un algoritmo de Prim o Kruskal, llegando a un recubrimiento mnimo, que es lo que parece que
solicitan.

Diciembre 2003 (problema) (igual a problema Febrero 2007-1)
Enunciado: Hoy es un da duro para el taller Sleepy. Llegan las vacaciones y a las 8:00 de la
maana n clientes han pedido una revisin de su coche. Como siempre, todos necesitan que
les devuelvan el coche en el menor tiempo posible. Cada coche necesita un tiempo de revisin
r

y al mecnico le da lo mismo por cul empezar: sabe que en revisar todos los coches tardar
lo mismo independientemente del orden que elija. Pero al jefe del taller no le da lo mismo, la
satisfaccin de sus clientes es lo que importa: es mejor tener satisfechos al mayor nmero de
ellos. Al fin y al cabo, la planificacin la hace l y, evidentemente, un cliente estar ms
satisfecho cuanto menos tarden en devolverle el coche. Implementar un programa que decida
el orden en el que revisar uno a uno los coches para maximizar la satisfaccin de los clientes de
Sleepy.
Respuesta: Este ejercicio no lo voy a resolver, ya que se trata exactamente el mismo
planteamiento que el de los dentistas, es decir, ordenar los clientes del taller por orden
creciente de tiempos e ir atendindoles. La demostracin de optimalidad ya se ha visto varias
veces, tanto en la teora (en el resumen) como en los ejercicios resueltos. Lo nico el
algoritmo, que sera lo ms complicado, pero aun as es la aplicacin casi exacta del esquema
general, en el que se ordenaran los clientes (costc 0(n log(n))), luego se escogeran por
este orden y se devolvera la suma de tiempos.

Septiembre 2004-reserva (problema)
Enunciado: Sea una red de comparticin de ficheros, similar a las que actualmente se utilizan
para intercambiar globalmente archivos por internet. Esta red se encuentra formada por n
servidores, siendo todos ellos capaces de distribuir un nmero n de archivos, de tamao I

Kilobytes, a diferentes velocidades de transmisin. La velocidad de transmisin de datos de
cada uno de los servidores viene determinada por una tabla de velocidades de transmisin S,
donde S
ij
es la velocidad de transmisin del servidor i para el archivo j (en K/seg). Se pide
disear un algoritmo capaz de repartir la descarga de los n archivos entre los n servidores
disponibles, minimizando el tiempo global de descarga de todos los archivos. La funcin
deber indicar el tiempo ptimo de descarga, as como los servidores desde los que sern
descargados los n archivos. Suponga que la descarga se lleva a cabo de manera secuencial, lo
que significa que no es posible descargar ms de un archivo al mismo tiempo.

Ejercicios tema 6 Curso 2007-08 Pgina 55 de 55

Tome como ejemplo ilustrativo de los datos de entrada una red de comparticin de 3 ficheros
(A1, A2 y A3) en 3 servidores distintos (S1, S2 y S3). El tamao de los 3 ficheros es I
1
=100K,
I
2
=200K, I
3
=300K y la velocidad de transmisin de los 3 servidores viene dado por la
matriz:
Servidores
S1 S2 S3

Archivos
A1 50 K/seg 12 K/seg 6 K/seg
A2 10 K/seg 20 K/seg 50 K/seg
A3 200 K/seg 50 K/seg 1 K/seg

Respuesta: Nos evitaremos dar ms detalles, ya que el ejercicio no est resuelto. Slo decir
que este ejercicio es igual al anterior, al del taller Sleepy, aunque en vez de tener un nico
servidor se tienen n servidores, por lo que hay que distribuir en n servidores distintos. Es decir,
se repartirn los tiempos entre los n servidores, como en el ejemplo anterior. Resumiendo, sin
decir ms, nos quedara el tiempo asociado algo as (tomado del libro de Mart):
I(P) = (n
]
k +1)t
(k-1)s+]
n
]
k=1
s
]=1

siendo
n Ji: s +1 si ] (n moJ s)
n
]
=
n Ji: s si ] >(n moJ s)

La demostracin de optimalidad se har como en los casos anteriores, basndose en el T (P)
antes escrito. Ya lo hemos visto, como digo no lo vuelvo a poner de nuevo.

Septiembre 2006-reserva (problema)
Enunciado: Un repartidor de pizzas tiene que entregar K pedidos de diferente valor de
recaudacin como mucho hasta la ranura de tiempo concreta que tiene asignada en la tabla
adjunta.

Pedido i: 1 2 3 4 5 6 7 8 9
Ranura: 1 5 5 6 6 4 4 2 2
Recaudacin: 60 70 80 20 20 30 50 50 90

Si un pedido se entrega tarde la recaudacin es 0. Construir un algoritmo que devuelva un plan
de trabajo para el repartidor que maximice el beneficio. Aplquelo al ejemplo detallando
TODOS los pasos. La resolucin del problema debe incluir, por este orden: eleccin razonada
del esquema algortmico y esquema, algoritmo completo a partir del refinamiento del
esquema general y estudio del coste del algoritmo desarrollado.
Respuesta: Este problema que yo sepa es similar al visto anteriormente de ordenar los pedidos
por orden decreciente de beneficios. Es como el de la minimizacin en tiempo del sistema que
hemos visto previamente en numerosos ejercicios.