Problema de maximización del número de programas almacenados en disco

De Wikipedia, la enciclopedia libre

Este artículo debería estar en Wikilibros ya que es una guía o manual en vez de un verdadero artículo enciclopédico.
Si modificas este artículo dándole una orientación enciclopédica, elimina por favor esta plantilla.

[editar] Descripción del problema

Consideremos n programas P₁,P₂,…P_n que debemos almacenar en un disco. El programa $P i$ requiere $s i$ megabytes de espacio de disco, y la capacidad del disco es D megabytes.

Supondremos que la capacidad del disco es insuficiente para contener todos los programas, es decir, que $D<\sum_{k=1}^n s_i$

[editar] Esquema de algoritmos voraces

Aplicaremos la técnica de los algoritmos voraces:

Conjunto de candidatos: Los n programas.

Función de selección: Nos proporcionará el mejor candidato aún no seleccionado. Elegiremos la estrategia de considerar los programas de menor a mayor tamaño. Si el programa cabe en el espacio de disco todavía no utilizado, graba el programa y pasa al siguiente; si el programa no cabe, lo descarta y termina, pues los siguientes tampoco van a caber.

Solución factible: Es un vector de n componentes (P₁,P₂,…P_n) tal que 0≤P_i≤1 y además $\sum_{k=1}^n P_i\cdot s_i\le D$

Solución óptima: Es una solución factible tal que representa el mayor beneficio posible.

Función objetivo: Maximizar el número de programas que caben en un disco, es decir, $max\left ( \sum_{k=1}^n P_i\cdot s_i\le D\right )$ tal que $\sum_{k=1}^n P_i\cdot s_i= D$

[editar] Demostración de la optimalidad

Vamos a demostrar que la estrategia de elección de programas de menor a mayor tamaño es la óptima. Compararemos la solución devuelta por la estrategia voraz, X, con otra solución óptima. Para ello representamos una solución cualquiera Z mediante su función característica, es decir, con una tupla (z₁,z₂,…z_n), donde z_i=0 indica que el programa P_i no se coge, mientras que $z i = 1$ indica que P_i forma parte de la solución. Para ella el número de programas seleccionados viene dado por $D<\sum_{k=1}^n z_i$

Supongamos que la estrategia voraz propuesta escoge los k primeros programas, con 1≤k≤n, y el (k+1)-ésimo programa ya no cabe, por lo que se descarta junto con los restantes. Entonces en la solución X se tiene que i : 1≤i≤ k: $x i = 1$ y i : k <i ≤ n : $x i = 0$ . El número de programas correspondiente es k.

Empezando a comparar (de izquierda a derecha) con Y, sea j≥1 la primera posición donde xj≠yj . Observamos que j≤k, porque si no la solución óptima incluiría todos los programas escogidos por la estrategia voraz y alguno más, por lo que llegaríamos a una contradicción con lo anterior, ya que rechazábamos los programas porque no cabían.

Se tiene, por tanto, la siguiente situación:

1	1	...	1	...	1	...	0	...	0
x₁	x₂	...	x_j	...	x_k	...	x_l	...	x_n
=	=	...	≠				≠
y₁	y₂	...	y_j	...	y_k	...	y_l	...	x_n

Entonces si y_j≠ x_j=1, tenemos y_j=0, y de aquí se sigue que $\sum_{k=1}^j y_i= j-1< j= \sum_{k=1}^j x_i$ .Ahora bien, como suponemos que Y es óptima, $\sum_{k=1}^n y_i \ge\sum_{k=1}^n x_i=k$ .Por tanto, existe $l > k\ge j$ tal que $y l = 1$ , es decir, tiene que haber un programa posterior para compensar el que no se ha cogido antes.

Ahora bien, por la ordenación de los programas sabemos que $s_j\le s_l$ , es decir, que si P_l cabe en el disco, podemos poner en su lugar P_j sin sobrepasar la capacidad total. Realizando este cambio en la solución óptima Y, obtenemos otra solución Y’ en la cual y’_j =1= x_j , y’_l=0 y para el resto y’_i = y_i . Esta nueva solución es más parecida a X, y tiene el mismo número de programas que Y, por lo que sigue siendo óptima.

Si seguimos repitiendo el proceso anterior, podemos ir igualando los programas en la solución óptima a los de la solución voraz X, hasta alcanzar la posición k.

[editar] Implementación

En la precondición de nuestro programa supondremos que los programas ya están en orden creciente de tamaño (el más pequeño se trata el primero) y que el tamaño de todos los programas no tiene que caber en el disco. El algoritmo que implementa esta estrategia es el siguiente:

Precondición: {s[1] ≤ s[2 ] ≤…≤ s[n] $\land \sum_{k=1}^n s \left [ i \right ]$ }

fun maximizar-programas-en-disco(s[1..n] de real, D: real) dev solucion[1..n] de 0..1
 {inicializamos las soluciones a 0}
 solucion [1..n]:=[0];
 utilizado:=0;
 i:=1;
 mientras utilizado + s[i] ≤ D hacer              
   solucion [i]:=1;             
   utilizado:= utilizado +s[i];
   i:=i+1;
 fmientras
ffun

Nota: los reales serán positivos

[editar] Ejemplo resuelto

Tenemos el siguiente tamaño para estos cuatro programas:

s₁	s₂	s₃	s₄
10	15	20	25

Para un tamaño de disco de D=40

Como observamos, se cumple la precondición (ordenado de forma creciente), y que la suma del tamaño de todos los programas es mayor que la capacidad del disco ( 10+15+20+25 =70 > 40)

Si aplicamos el algoritmo implementado tendremos como solución las dos primeras posiciones : s₁= 10 y s₁=15

El número de programas que caben en este disco será 2.

[editar] Enlaces interesantes

Algoritmo voraz

[editar] Bibliografía

Martí Oliet, N.; Ortega Mallén, Y.; Verdejo López, J. A. (2003), Estructuras de datos y métodos algorítmicos. Ejercicios resueltos, Pearson Prentice Hall.

Obtenido de "http://es.wikipedia.org../../../p/r/o/Problema_de_maximizaci%C3%B3n_del_n%C3%BAmero_de_programas_almacenados_en_disco.html"

Categorías: Wikipedia:Trasladar a Wikilibros | Programación