Programación dinámica.

EL ALGORITMO DE DIJKSTRA

2009-06-01T07:44:00.000-07:00

Sea un grafo ponderado g = (V,A), donde V es su conjunto de vértices, A el conjunto de arcos y sea L[i,j] su matriz de adyacencia. Queremos calcular el camino más corto entre un vértice vi tomado como origen y cada vértice restante vj del grafo.
El clásico algoritmo de Dijkstra trabaja en etapas, en donde en cada una de ellas va añadiendo un vértice al conjunto D que representa aquellos vértices para los que se conoce su distancia al vértice origen. Inicialmente el conjunto D contiene sólo al vértice origen.
Es posible plantear el algoritmo de Dijkstra en términos de la Programación Dinámica, y de esta forma aprovechar el método de diseño y las ventajas que esta técnica ofrece.
En primer lugar, observemos que es posible aplicar el principio de óptimo en este caso: si en el camino mínimo de vi a vj está un vértice vk como intermedio, los caminos parciales de vi a vk y de vk a vj han de ser a su vez mínimos.
Llamaremos D(j) al vector que contiene el camino mínimo desde el vértice origen i = 1 a cada vértice vj, 2 <=j <=n, siendo n el número de vértices. Inicialmente D contiene los arcos L(1,j), o bien ∞ si no existe el arco. A continuación, y para cada vértice vk del grafo con k <>1, se repetirá:

De esta forma el algoritmo que resuelve el problema puede ser implementado
como sigue:

CONST n = ...; (* numero de vertices del grafo *)
TYPE MATRIZ = ARRAY [1..n],[1..n] OF CARDINAL;
MARCA = ARRAY [1..n] OF BOOLEAN;(* elementos ya considerados*)
SOLUCION = ARRAY [2..n] OF CARDINAL;

PROCEDURE Dijkstra(VAR L:MATRIZ;VAR D:SOLUCION);
VAR i,j,menor,pos,s:CARDINAL; S:MARCA;
BEGIN
FOR i:=2 TO n DO
S[i]:=FALSE;
D[i]:=L[1,i]
END;
S[1]:=TRUE;
FOR i:=2 TO n-1 DO
menor:=Menor(D,S,pos);
S[pos]:=TRUE;
FOR j:=2 TO n DO
IF NOT(S[j]) THEN
D[j]:= Min2(D[j],D[pos]+L[pos,j])
END;
END;
END
END Dijkstra;

La función Menor es la que calcula el mínimo de la expresión en recurrencia
que define la solución del problema:

PROCEDURE Menor(VAR D:SOLUCION; VAR S:MARCA; VAR pos:CARDINAL)
:CARDINAL;
VAR menor,i:CARDINAL;
BEGIN
menor:=MAX(CARDINAL); pos:=1;
FOR i:=2 TO n DO
IF NOT(S[i]) THEN
IF D[i]
menor:=D[i]; pos:=i
END
END
END;
RETURN menor
END Menor;

La complejidad temporal del algoritmo es de orden O(n2), siendo de orden O(n) su complejidad espacial. No ganamos sustancialmente en eficiencia mediante el uso de esta técnica frente al planteamiento ávido del algoritmo, pero sin embargo sí ganamos en sencillez del diseño e implementación de la solución a partir del planteamiento del problema.

El viajante de comercio

2009-06-01T06:48:00.000-07:00

Se conocen las distancias entre un cierto número de ciudades. Un viajante debe, a partir de una de ellas, visitar cada ciudad exactamente una vez y regresar al punto de partida habiendo recorrido en total la menor distancia posible.
Este problema consiste en encontrar el camino sin ciclos de menor peso de un grafo ponderado que recorra todos los vértices y vuelva al vértice original.
Solución

En primer lugar, vamos a plantear la solución del problema como una sucesión de decisiones que verifique el principio de óptimo. La idea va a consistir en construir una solución mediante la búsqueda sucesiva de recorridos mínimos de tamaño 1, 2, 3, etc.
Representando el problema a través de un grafo g = (V,A), y siendo L su matriz de adyacencia, cada recorrido del viajante que parte del vértice v1 estará formado por un arco (v1,vk) para algún vértice vk perteneciente a V–{v1} y un camino de vk al vértice v1.
Pero si el recorrido es óptimo también ha de ser óptimo el camino de vk al vértice v1, pues si no lo fuese llegaríamos a una contradicción. Si no lo fuese y existiera otro camino mejor, incluyendo a éste en el recorrido original obtendríamos un camino mejor que el óptimo, lo cual es imposible. Por tanto, se cumple el principio de óptimo.
Planteemos entonces la relación en recurrencia. Para ello, llamaremos D(vi,S) a la longitud del camino mínimo que partiendo del vértice vi pasa por todos los vértices del conjunto S y vuelve al vértice vi. La solución al problema del viajante vendrá dada entonces por D(v1,V–{v1}):

Generalizando para comenzar el recorrido desde cualquier vértice:

Obsérvese la diferencia que existe entre la estrategia de este algoritmo y los que tratamos de diseñar siguiendo dos técnicas ávidas (ver el problema 4.4 del capítulo anterior). En los algoritmos ávidos se ha de escoger una de las posibles opciones en cada paso, y una vez tomada –o descartada–, ya no vuelve a ser considerada nunca. Son algoritmos que no guardan “historia”, y por tanto no siempre funcionan. Sin embargo, en la Programación Dinámica la solución al problema total se va construyendo de otra forma: a partir de las soluciones óptimas para problemas más pequeños.
No obstante, el diseño aquí realizado tiene un serio inconveniente: su implementación utilizando una estructura de datos que permita reutilizar los
cálculos. Tal estructura debería contener las soluciones intermedias necesarias para el cómputo de D(v1,V–{v1}), pero estas son demasiadas.
En efecto, la tabla debe tener n filas, y 2n columnas, pues éste es el cardinal de las partes del conjunto V, que son todas las posibilidades que puede tomar el segundo parámetro de D en su definición.
Por tanto, sí existe una solución al problema del viajante utilizando Programación Dinámica, pero no sólo no consigue mejorar la eficiencia de su versión clásica mediante Vuelta Atrás (véase el siguiente capítulo), sino que tampoco ofrece una mejora en cuanto a la simplicidad de su implementación.

Más información en Programación Dinámica

Camino de coste mínimo en un grafo multietapa.

2009-05-28T08:51:00.000-07:00

Un grafo multietapa G = {N, A} es un grafo dirigido en el que se puede hacer una partición del conjunto de nodos o vértices N en k(≥ 2) conjuntos disjuntos Ci , 1 ≤ i ≤ k, donde todo arco del grafo (n, m) es tal que n pertenece a Ci y m pertenece a Ci+1 para algún i, 1 ≤ i ≤ k − 1. El coste de cada arco (i, j) lo proporciona la función c. Los conjuntos C1 y Ck tienen un sólo nodo, llamándose al primero nodo origen (o) y al segundo nodo destino (d). Si el número de conjuntos Ci es k se dice que es un grafo k-etapa.
El problema consiste en encontrar un camino de coste mínimo que vaya desde el nodo origen o al nodo destino d. Por las restricciones impuestas, un camino de coste mínimo tendrá exactamente un sólo nodo en cada conjunto Ci , de ahí que cada Ci deﬁna una etapa del grafo. También puede decirse que cada arco del camino une una etapa con la siguiente.
Este problema tiene gran importancia en la práctica ya que muchos de los problemas de reparto óptimo de recursos pueden formularse en términos de un grafo multietapa.
Veamos cómo aplicar programación dinámica a esta situación:
Se satisface el principio de optimalidad ya que el camino de coste mínimo debe contener subcaminos de coste mínimo; en caso contrario, podrá sustituirse dichos subcaminos por otros mejores, resultando un camino total de coste menor. Además, la solución ﬁnal será una secuencia de decisiones, y cada decisión depende del resultado de otras. En general, la i-ésima decisión consiste en determinar, a partir de un nodo ni de Ci , un arco que tenga a ni como nodo origen y a algún ni+1 de Ci+1 como nodo destino, siendo 1 ≤ i ≤ k − 2. El número mínimo de decisiones para un grafo k-etapa es k − 2 ya que cada camino consta de k − 1 arcos, y el ultimo queda determinado por la decisión tomada en la etapa anterior.

Sea CA(i, j) un camino de coste mínimo COST E(i, j) desde el nodo origen o hasta el nodo j de Ci . Usando una formulación hacia atrás tenemos

De igual forma, podemos analizar el coste mediante una formulación hacia adelante:
Si CA(i, j) es un camino de coste mínimo COSTE(i, j) desde el nodo j del conjunto Ci hasta el nodo destino d , entonces:

En general, se podrán utilizar indistintamente cualquiera de las dos formulaciones. Veamos a continuación el algoritmo que nos permite construir la trayectoria de coste mínimo con una formulación hacia atrás. (Hemos suprimido el primer índice de la variable COSTE ya que considerábamos que no era trascendente para el algoritmo.)

algoritmo multigrafo (ENT A :arcos; k, n :entero; C :tabla[1..n,1..n]; SAL P :tabla[1..k])
{Este algoritmo construye a partir de un grafo de k etapas, con n vértices,
conjunto de arcos A y costes C, la trayectoria P de coste mínimo}

Para estudiar la complejidad de este algoritmo hay que tener en cuenta que la complejidad del primer bucle sera O(max(n, a)) = O(n + a) siendo n el número de vértices y a el número de aristas, y la del segundo O(k), donde k siempre es menor que n. Por tanto, la complejidad total del algoritmo es O(n + a).

Función de Fibonacci

2009-05-21T06:41:00.000-07:00

Codigo fuente

import java.io.*;
 
public class Fibonacci {
      BufferedReader teclado = new BufferedReader(new InputStreamReader(System.in));
int opcionSalir;
      public Fibonacci(){
        mostrarMenu();
      }
 
 
public static long fibonacci_pd(long n) throws NumeroException {
   if (n < 0) {
       throw new NumeroException("No se pueden introducir números negativos");
   }
 
 
  if(n==0 || n==1){
      return n;
  }
 long[] a=new long[(int)n+1];
 a[0]=0;
 a[1]=1;
 for(int i=2;i<=n;i++){
   a[i]=a[i-1]+a[i-2];
 }
  return a[(int)n];
}
 
  private void mostrarMenu() {
 
    opcionSalir = 2;
 
    int opcion;
    do {
      String[] menu = {
          "\n-------------- Fibonacci --------------",
          " 1.- Introducir valor",
 
          "",
          " 2.- Salir",
          "----------------------------------------"};
 
      for (int i = 0; i < menu.length; i++) {
        System.out.println(menu[i]);
      }
 
      System.out.println();
      opcion = pedirOpcion();
      System.out.println();
      procesarOpcion(opcion);
      System.out.println();
    }
    while (opcion != opcionSalir);
    System.out.println("Programa finalizado.");
 
  }
 
  private void procesarOpcion(int opcion) {
    switch (opcion) {
      case 1:
    calcular();
        break;
 
      case 2:
        System.exit(0);
        break;
    }
 
  }
 
  private int pedirOpcion() {
    int opcion = 0;
    do {
      opcion = pedirEntero("Opcion: ");
      if (opcion < 1 && opcion > opcionSalir) {
        System.out.println("Opcion inválida, repite");
      }
    }
    while (opcion < 1 || opcion > opcionSalir);
    return opcion;
  }
  private int pedirEntero(String mensaje) {
  int entero = 0;
  try {
    System.out.print(mensaje);
    entero = Integer.parseInt(teclado.readLine());
  }
  catch (IOException ex) {
    System.out.println(
        "Error generico de Entrada-Salida con el teclado");
  }
  catch (NumberFormatException ex) {
    System.out.println("Formato erroneo para numero");
  }
  return entero;
}
 
public void calcular(){
  System.out.println(
          "\nIntroduzca el numero del que desea calcular la sucesión de Fibonacci: ");
 
     
        try {
          long numero = Long.parseLong(teclado.readLine());
          System.out.println(
              "\nEl valor del la función de Fibonacci para el número " + numero +
              " es: " + fibonacci_pd( numero));
        }
        catch (NumeroException ex) {
          System.err.println("Solamente se puede introducir números");
 
        }
        catch (IOException ex) {
            System.err.println(ex.getMessage());
        }
        catch (NumberFormatException ex) {
                  System.err.println(ex.getMessage());
        }
 }
   
  public static void main(String[] args) {
    new Fibonacci();
  }
}

CLASE NUMEROEXCEPTION

 
public class NumeroException extends Exception {
 
public NumeroException(String mensaje) {
  super(mensaje);
}
 
}


Código anterior

 
import java.io.*;
 
public class Fibonacci {
 
  /**
   * Función de fibonacci, se implementa con la técnica Programación Dinámica.
   * Se comprueba que el número sea positivo.
   * @param n long
   * @throws NumeroException
   * @return long
   */
  public static long fibonacci_pd(long n) throws NumeroException {
    if (n < 0) {
      throw new NumeroException("No se pueden introducir números negativos");
    }
    if (n == 0) {
      throw new NumeroException("El número tiene que ser mayor que 0");
    }
    long[] f = new long[ (int) n + 1];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i < n + 1; i++) {
      f[i] = f[i - 1] + f[i - 2];
    }
    return f[ (int) n];
  }
 
  /**
   * Función Main. Se pide al usuario un número para calcular su valor mediante
   * la función de Fibonacci
   * @param args String[]
   */
  public static void main(String[] args) {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    System.out.println(
        "\nIntroduzca el numero del que desea calcular la sucesión de Fibonacci: ");
    try {
      long numero = Long.parseLong(reader.readLine());
      System.out.println(
          "\nEl valor del la función de Fibonacci para el número " + numero +
          " es: " + fibonacci_pd(numero));
    }
    catch (NumberFormatException nfe) {
      System.err.println("Solamente se puede introducir números");
      main(args);
    }
    catch (NumeroException ne) {
      System.err.println(ne.getMessage());
      main(args);
    }
    catch (IOException ioe) {
      System.err.println(ioe.getMessage());
    }
  }
}
 

Excepción usada en el codigo anterior

 
public class NumeroException
    extends Exception {
 
  public NumeroException(String mensaje) {
    super(mensaje);
  }
}

Función de Fibonacci con Programación Dinámica

2009-05-21T06:00:00.000-07:00

Vamos a resolver la función de Fibonacci mediante programación dinámica, esta función como sabéis corresponde a la ecuación : f(x)= f(x-1) + f(x-2)

Se puede realizar este problema mediante programación dinamica al igual que mediante divide y venceras, si bien es mas eficiente la resolución de programación dinamica para evitar calcular varias veces un mismo valor.

La precondición que presenta este problema es que no se puede buscar el valor de la función de fibonacci para numeros negativos.

Solución al problema

La solución que hemos dado al problema es un ejemplo del algoritmo de Programación dinamica, siendo esta implementacion una ligera mejora del ejemplo presentado en el cuaderno didactico de búsqueda recursivo "Función de Fibonacci".

Complejidad Temporal

Este código contiene varias sentencias condicionales y varias instrucciones lineales, a la hora de hallar la complejidad temporal lo unico que nos interesa mirar es el unico bucle simple que hay. Teniendo en cuenta esto la complejidad temporal sería O(n) donde n es el numero de pasadas que tiene que realizar el bucle.

Función de Fibonacci implementada con Programación Dinámica mediante Java:

He encontrado esta implementación de clases que crea un programa que resuelve la función de Fibonacci mediante Java y programación dinámica:

CLASE FIBONACCI

Codigo fuente

import java.io.*;
 
public class Fibonacci {
      BufferedReader teclado = new BufferedReader(new InputStreamReader(System.in));
int opcionSalir;
      public Fibonacci(){
        mostrarMenu();
      }
 
 
public static long fibonacci_pd(long n) throws NumeroException {
   if (n < 0) {
       throw new NumeroException("No se pueden introducir números negativos");
   }
 
 
  if(n==0 || n==1){
      return n;
  }
 long[] a=new long[(int)n+1];
 a[0]=0;
 a[1]=1;
 for(int i=2;i<=n;i++){
   a[i]=a[i-1]+a[i-2];
 }
  return a[(int)n];
}
 
  private void mostrarMenu() {
 
    opcionSalir = 2;
 
    int opcion;
    do {
      String[] menu = {
          "\n-------------- Fibonacci --------------",
          " 1.- Introducir valor",
 
          "",
          " 2.- Salir",
          "----------------------------------------"};
 
      for (int i = 0; i < menu.length; i++) {
        System.out.println(menu[i]);
      }
 
      System.out.println();
      opcion = pedirOpcion();
      System.out.println();
      procesarOpcion(opcion);
      System.out.println();
    }
    while (opcion != opcionSalir);
    System.out.println("Programa finalizado.");
 
  }
 
  private void procesarOpcion(int opcion) {
    switch (opcion) {
      case 1:
    calcular();
        break;
 
      case 2:
        System.exit(0);
        break;
    }
 
  }
 
  private int pedirOpcion() {
    int opcion = 0;
    do {
      opcion = pedirEntero("Opcion: ");
      if (opcion < 1 && opcion > opcionSalir) {
        System.out.println("Opcion inválida, repite");
      }
    }
    while (opcion < 1 || opcion > opcionSalir);
    return opcion;
  }
  private int pedirEntero(String mensaje) {
  int entero = 0;
  try {
    System.out.print(mensaje);
    entero = Integer.parseInt(teclado.readLine());
  }
  catch (IOException ex) {
    System.out.println(
        "Error generico de Entrada-Salida con el teclado");
  }
  catch (NumberFormatException ex) {
    System.out.println("Formato erroneo para numero");
  }
  return entero;
}
 
public void calcular(){
  System.out.println(
          "\nIntroduzca el numero del que desea calcular la sucesión de Fibonacci: ");
 
     
        try {
          long numero = Long.parseLong(teclado.readLine());
          System.out.println(
              "\nEl valor del la función de Fibonacci para el número " + numero +
              " es: " + fibonacci_pd( numero));
        }
        catch (NumeroException ex) {
          System.err.println("Solamente se puede introducir números");
 
        }
        catch (IOException ex) {
            System.err.println(ex.getMessage());
        }
        catch (NumberFormatException ex) {
                  System.err.println(ex.getMessage());
        }
 }
   
  public static void main(String[] args) {
    new Fibonacci();
  }
}

CLASE NUMEROEXCEPTION

 
public class NumeroException extends Exception {
 
public NumeroException(String mensaje) {
  super(mensaje);
}
 
}


Código anterior

 
import java.io.*;
 
public class Fibonacci {
 
  /**
   * Función de fibonacci, se implementa con la técnica Programación Dinámica.
   * Se comprueba que el número sea positivo.
   * @param n long
   * @throws NumeroException
   * @return long
   */
  public static long fibonacci_pd(long n) throws NumeroException {
    if (n < 0) {
      throw new NumeroException("No se pueden introducir números negativos");
    }
    if (n == 0) {
      throw new NumeroException("El número tiene que ser mayor que 0");
    }
    long[] f = new long[ (int) n + 1];
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i < n + 1; i++) {
      f[i] = f[i - 1] + f[i - 2];
    }
    return f[ (int) n];
  }
 
  /**
   * Función Main. Se pide al usuario un número para calcular su valor mediante
   * la función de Fibonacci
   * @param args String[]
   */
  public static void main(String[] args) {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    System.out.println(
        "\nIntroduzca el numero del que desea calcular la sucesión de Fibonacci: ");
    try {
      long numero = Long.parseLong(reader.readLine());
      System.out.println(
          "\nEl valor del la función de Fibonacci para el número " + numero +
          " es: " + fibonacci_pd(numero));
    }
    catch (NumberFormatException nfe) {
      System.err.println("Solamente se puede introducir números");
      main(args);
    }
    catch (NumeroException ne) {
      System.err.println(ne.getMessage());
      main(args);
    }
    catch (IOException ioe) {
      System.err.println(ioe.getMessage());
    }
  }
}
 

Excepción usada en el codigo anterior

 
public class NumeroException
    extends Exception {
 
  public NumeroException(String mensaje) {
    super(mensaje);
  }
}

Problema de la moneda con programación dinámica

2009-05-12T04:23:00.001-07:00


public int[][] Mochila(int[] pesos, int[] beneficios, int capacidad){
 
   //Creamos la matriz de devoluciones
   int[][]  matriz_mochila = new int[pesos.length+1][capacidad+1];

  //Rellenamos la 1ª fila de ceros
  for(int i = 0; i <= capacidad; i++) 
    matriz_mochila[0][i] = 0;       
  //Rellenamos la 1ª columna de ceros  
  for(int i = 0; i <= pesos.length; i++)     
     matriz_mochila[i][0] = 0;      

  for(int j = 1; j <= pesos.length ; j++) 
    for(int c = 1; c <= capacidad; c++){   
        if(c <  pesos[j-1] ){           
          matriz_mochila[j][c] = matriz_mochila[j-1][c];     
        }else{
          if(matriz_mochila[j-1][c] > matriz_mochila[j-1][c-pesos[j-1]]+ beneficios[j-1]){
             matriz_mochila[j][c] = matriz_mochila[j-1][c];
          }else{
             matriz_mochila[j][c] = matriz_mochila[j-1][c-pesos[j-1]]+beneficios[j-1];
          }
        }
     }
   return matriz_mochila;
}

Libros sobre Programación Dinámica

2009-05-11T13:32:00.000-07:00

Teoría de colas y programación dinámica

Autora: Isabel Plaza Idalgo.

75 págs. / Rústica / Castellano / Libro
ISBN10 8436236882; ISBN13 9788436236880

Fundamentos de Programación Lineal y Optimización en Redes: Ejercicios Resueltos de Investigación Operativa Asistidos por Ordenador

Autor:David Pujolar Morales(Universidad Autónoma de Barcelona. Servicio de Publicaciones = Universitat Autònoma de Barcelona. Servei de Publicacions)

Problema de la mochila con programación dinámica

2009-05-11T08:07:00.000-07:00

Sea n objetos no fraccionables de pesos pi y beneficios bi. El peso máximo que puede llevar la mochila es C. Queremos llenar la mochila con objetos, de forma que se maximice el beneficio.

Datos

* n objetos con pesos pi y beneficios bi asociados a cada objeto.
* No se pueden fraccionar los objetos (se cogen o no se cogen).
* Se define un problema más general en función del número de objetos y la capacidad C de la mochila: mochila(k,l,C)
* Resolver el problema consiste en obtener: mochila(1,n,C)

Resolución mediante Programación Dinámica

Para resolver el problema de la mochila necesitamos realizar ciertas acciones:

* Ver que se cumple el principio de optimalidad de Bellman.
* Buscar ecuaciones recurrentes para el problema.
* Construir una tabla de valores a partir de las ecuaciones.

Principio de optimalidad de Bellman

* Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones que resuelve un problema también debe ser óptima respecto al subproblema que se resuelve.
* Sea y1,…,yn una secuencia óptima de valores 0-1 para x1,…,xn.
o Si y1=0, entonces y2,…,yn forman una secuencia óptima para el problema mochila(2, n, C).
o Si y1=1, entonces y2,…,yn forman una secuencia óptima para el problema mochila(2, n, C - p1).

* Demostración: Si existe una solución mejor para el problema correspondiente, entonces es mejor que para el problema mochila(1, n, C), en contra de la hipótesis. Lo mismo se cumple en cualquier etapa de decisión.

Ecuaciones recurrentes para el problema

a) Ecuación hacia delante

* Supongamos que gi(C) es el beneficio acumulado para la solución óptima del problema mochila(j,n,C), entonces:

gj(C)= max {gj+1(C), gj+1(C-pj)+bj}

cuyo significado:

gj+1(C) -> no se coge el objeto j
gj+1(C-pj)+bj -> se coge el objeto j

* El caso trivial se da cuando j vale n+1, y en este caso:

gn+1(C) = 0

* Luego el cálculo de mochila(1,n,C) se reduce a la aplicación de las ecuaciones:

gj(C) = max {gj+1(C), gj+1(C-pj)+bj} si j<>n+1
gj(C) = 0 si j = n+1

b) Ecuación hacia atrás

* Supongamos que gj(C) es el beneficio acumulado para la solución óptima del problema mochila(1,j,C), entonces:

gj(C)= max {gj-1(C), gj-1(C-pj)+bj}

cuyo significado:

gj-1(C) -> no se coge el objeto j
gj-1(C-pj)+bj -> se coge el objeto j

* El caso trivial se da cuando j vale 0, y en este caso:

g0(C) = 0

* Luego el cálculo de mochila(1,n,C) se reduce a la aplicación de las ecuaciones:

gj(C) = max {gj-1(C), gj-1(C-pj)+bj} si j<>0
gj(C) = 0 si j = 0

Implementación

* Si consideramos la ecuación hacia atrás, la implementación nos quedará:


proc mochila(p,b:vector[1..n] de nat,cap: nat,g: vector[0..n, 0..cap] de nat)
var c,j: nat;
para c=0 hasta cap hacer g[0,c]=0 fpara;
para j=1 hasta n hacer g[j,0]=0 fpara;
para j=1 hasta n hacer
para c=1 hasta cap hacer
si c menor que  p[j] entonces
g[j,c]=g[j-1,c];
en caso contrario
si g[j-1,c] mayor  que g[j-1,c-p[j]]+b[j] entonces
   g[j,c]=g[j-1,c];            
en caso contrario
   g[j,c]=g[j-1,c-p[j]]+b[j];
fsi;
fsi;
fpara;
fpara;
fproc;

Función Java del problema de la mochila


 public int[][] Mochila(int[] pesos, int[] beneficios, int capacidad){
   
    //Creamos la matriz de devoluciones
    int[][]  matriz_mochila = new int[pesos.length+1][capacidad+1];

   //Rellenamos la 1ª fila de ceros
   for(int i = 0; i <= capacidad; i++)
            matriz_mochila[0][i] = 0; 

   //Rellenamos la 1ª columna de ceros
   for(int i = 0; i <= pesos.length; i++)  
           matriz_mochila[i][0] = 0;   

        for(int j = 1; j <= pesos.length ; j++)  
           for(int c = 1; c <= capacidad; c++){  
      if(c <  pesos[j-1] ){   
        matriz_mochila[j][c] = matriz_mochila[j-1][c]; 
            }else{   
              if(matriz_mochila[j-1][c] > matriz_mochila[j-1][c-pesos[j-1]]+ beneficios[j-1]){
           matriz_mochila[j][c] = matriz_mochila[j-1][c];
               }else{
                 matriz_mochila[j][c] = matriz_mochila[j-1][c-pesos[j-1]]+beneficios[j-1];
               }
            }
       }
       return matriz_mochila;
     }

Principio de optimalidad de Bellman

2009-05-11T02:41:00.000-07:00

En este contexto, "optimizar" equivale a seleccionar (buscar) la "mejor" solución de entre muchas posibles alternativas. Este proceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución correcta. Si, dada una subsecuencia de decisiones,
siempre se conoce cual es la decisión que debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz.

A menudo, aunque no sea posible aplicar la estrategia voraz, se cumple el principio de optimalidad de Bellman : "dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez, óptima". En este caso sigue siendo posible el ir tomando decisiones elementales, en la
confianza de que la combinación de ellas seguirá siendo óptima, pero será entonces necesario explorar muchas secuencias de decisiones para dar con la correcta, siendo aquí donde interviene la programación dinámica.

Contemplar un problema como una secuencia de decisiones equivale a dividirlo en subproblemas de talla inferior, en principio más fácilmente resolubles. Ello se enmarca en el método de Divide y Vencerás, técnica similar a la de Programación Dinámica. La programación dinámica se aplica cuando la subdivisión de un problema conduce a:

Una enorme cantidad de subproblemas.
Subproblemas cuyas soluciones parciales se solapan.
Grupos de subproblemas de muy distinta complejidad.

circunstancias que en conjunto o por separado, llevarían a una complejidad exponencial de la estrategia "Divide y Vencerás".

Proceso de resolución de problemas de programación dinámica

2009-05-07T03:18:00.000-07:00

En general el problema se puede usando un proceso de tres pasos:

Separar el problema en subproblemas más pequeños.
Resolver estos problemas óptimamente usando este proceso de tres pasos de manera recursiva.
Use las soluciones optimas para construir una solución óptima del problema original.

Los subproblemas son así mismo resueltos dividiendo estos en subproblemas y así en adelante hasta que se alcance el caso más simple que sea fácil de resolver.

Decir que un problema tiene subproblemas sobrepuestos es decir que un mismo subproblema es usado para resolver muchos problemas diferentes
más grandes.

Por ejemplo en la secuencia de Fibonacci F3 = F1 + F2 y F4 = F2 + F3, el calculo de cada número involucra el cálculo de F2. Ya que ambos F3 y F4 son necesarios para calcular F5, un método ingenuo para calcular F5 puede terminar haciendo el calculo de F2 dos o más veces.

Cuando los subproblemas se sobreponen un método puede perder tiempo recalculando soluciones óptimas de subproblemas ya resueltos.

A fin de evitar la repetición de cálculos, se pueden guardar las soluciones a los problemas ya resueltos de manera que si se requiere resolver el mismo problema después, se puede reutilizar los cálculos
hechos previamente.

Este approach es llamado memoización (no memorización).

Cuando se este seguro de que una solución particular ya no se necesita más se puede entonces borrarla, liberando así el espacio.

En algunos casos se pueden hacer cómputos que se saben se requerirán en lo posterior.

Subestructura óptima y subproblemas sobrepuestos

2009-05-07T03:11:00.000-07:00

Subestructura óptima significa que la subestructura de los subproblemas puede ser usada para encontrar la solución óptima para
el problema completo.

Por ejemplo, el camino más corto a un objetivo desde un vértice, en un grafo acíclico puede ser encontrado calculando inicialmente el camino más cercano al objetivo desde todos los vértices adyacentes y entonces
usando esto para encontrar el mejor camino completo.

Figura 1. Encontrando el camino más cercano en un grafo usando subestructuras optimas; las líneas oscuras indican el camino más cercano entre el inicio y el objetivo.

Decir que un problema tiene subproblemas sobrepuestos es decir que un mismo subproblema es usado para resolver muchos problemas diferentes más grandes.

Resolución de problemas de programación dinámica

El problema de las monedas con programación dinámica.

2009-05-05T22:59:00.000-07:00

Solucionemos este problema de programación dinámica en una función Java:


public int Minima_devolucion(int cantidad_devuelta, int[]  monedas){
  
  
  //Creamos la matriz de devoluciones
  int[][]  matriz_cambio = new int[monedas.length+1][cantidad_devuelta+1];
  
 //Rellenamos la 1ª columna de ceros
 for(int i = 0; i < monedas.length; i++)
     matriz_cambio[i][0] = 0;
  
 //La 1ª fila menos la 1ª columna un número alto
 for(int j = 1; j <= cantidad_devuelta; j++)
     matriz_cambio[0][j] = 999999;
  
 for(int i = 1; i <= monedas.length ; i++)
    for(int j = 1; j <= cantidad_devuelta; j++){
     if(monedas[i-1] > j ){
       //Si la moneda es superior a la cantidad a devolver
       matriz_cambio[i][j] = matriz_cambio[i-1][j]; 
     }else{
       //Si la moneda no es superior a la cantidad a devolver
     
       //Calcular cual es el mínimo de estas dos posiciones
       int minimo = 0; //Guardaremos aquí el mínimo
     
      if(matriz_cambio[i-1][j] < matriz_cambio[i][j - monedas[i-1]] + 1){
        minimo = matriz_cambio[i-1][j];
      }else{
        minimo = matriz_cambio[i][j - monedas[i-1]] + 1;
      }
      //Guardamos mínimo
      matriz_cambio[i][j] = minimo;
    }
   }
  

 return matriz_cambio[monedas.length][cantidad_devuelta];
}

Problema de las monedas con programación dinámica

2009-05-05T03:26:00.000-07:00

Para el problema de las monedas con programación dinámica se necesita crear un algoritmo que permita a una máquina expendedora devolver el cambio mediante el menor número de monedas posible. Mediante la programación dinámica se solucionará el caso en el que el número de monedas de cada tipo es ilimitado. En el problema de las monedas mediante el algoritmo voraz el que el número de monedas es ilimitado.

Descripción

Supongamos que se tienen monedas de valor 1, 4 y 6 y que se debe devolver una cantidad correspondiente al valor 8. Siguiendo el método de la programación dinámica, se rellenará una tabla con las filas correspondientes a cada valor para las monedas y las columnas con valores desde el 1 hasta el 8. Cada posición (i, j) de la tabla nos indica el número mínimo de monedas requeridas para devolver la cantidad j con monedas con valor menor o igual al de i:

____ 1 2 3 4 5 6 7 8
m1=1 1 2 3 4 5 6 7 8
m2=4 1 2 3 1 2 3 4 2
m3=6 1 2 3 1 2 1 2 2

Ejemplo para la posición i = 2 y j = 7, se requiere una moneda tipo 2 con valor 4 y tres monedas de tipo 1 con valor uno, por lo tanto en la tabla el número de monedas en la posición (2,7) sera 1 + 3 = 4.

Algoritmo

1. Para cada casilla de la tabla hacer:
2. Si el valor de la moneda actual es mayor que la cantidad, se paga con el resto de monedas, es decir, se toma el resultado de la casilla superior.
3. Si el valor de la moneda actual es menor o igual que la cantidad, se toma el mínimo entre:
1. Pagar con el resto de monedas, tomando el resultado de la casilla superior.
2. Pagar con una moneda del tipo actual y el resto con el resultado que se hubiera obtenido al pagar la cantidad actual a la que se le ha restado el valor de la moneda actual.
4. Tomar como resultado el valor de la última celda.

Pseudocódigo

Solucionemos este problema de programación dinámica en un pseudocódigo.

Como parámetros de entrada, la función toma C, que corresponde con la cantidad a devolver, y un vector M de monedas, que almacena el valor de cada tipo. Devuelve num, el número de monedas necesarias para realizar la devolución.


fun cambio (C: nat; M[1..n] de nat) dev num: nat
var
 T[0..n][0..C] de nat
begin
 T[0][1..C] := \infty;
 T[1..n][0] := 0;
 para i := 1 hasta n hacer
     para j := 1 hasta C hacer
         si M[i] > j entonces T[i, j] := T[i-1, j]
             si no
                 T[i, j] := min {T[i-1, j], T[i, j-M[i] ] + 1 }
             fsi
     fpara
 fpara
 num := T[n, C]
ffun

Código Java

Solucionemos este problema de programación dinámica en un código Java:



public int Minima_devolucion(int cantidad_devuelta, int[]  monedas){
  
  
  //Creamos la matriz de devoluciones
  int[][]  matriz_cambio = new int[monedas.length+1][cantidad_devuelta+1];
  
 //Rellenamos la 1ª columna de ceros
 for(int i = 0; i < monedas.length; i++)
     matriz_cambio[i][0] = 0;
  
 //La 1ª fila menos la 1ª columna un número alto
 for(int j = 1; j <= cantidad_devuelta; j++)
     matriz_cambio[0][j] = 999999;
  
 for(int i = 1; i <= monedas.length ; i++)
    for(int j = 1; j <= cantidad_devuelta; j++){
     if(monedas[i-1] > j ){
       //Si la moneda es superior a la cantidad a devolver
       matriz_cambio[i][j] = matriz_cambio[i-1][j]; 
     }else{
       //Si la moneda no es superior a la cantidad a devolver
     
       //Calcular cual es el mínimo de estas dos posiciones
       int minimo = 0; //Guardaremos aquí el mínimo
     
      if(matriz_cambio[i-1][j] < matriz_cambio[i][j - monedas[i-1]] + 1){
        minimo = matriz_cambio[i-1][j];
      }else{
        minimo = matriz_cambio[i][j - monedas[i-1]] + 1;
      }
      //Guardamos mínimo
      matriz_cambio[i][j] = minimo;
    }
   }
  

 return matriz_cambio[monedas.length][cantidad_devuelta];
}

Características de un Problema de Programación Dinámica

2009-04-30T15:18:00.000-07:00

Para que un problema pueda ser resuelto con la técnica de programación dinámica, debe

cumplir con ciertas características:

Naturaleza secuencial de las decisiones: El problema puede ser dividido en etapas.

Cada etapa tiene un numero de estados asociados a ella.

La decisión óptima de cada etapa depende solo del estado actual y no de las decisiones

anteriores.

La decisión tomada en una etapa determina cual será el estado de la etapa siguiente.

En síntesis, la política óptima desde un estado s de la etapa k a la etapa final esta constituida

por una decisión que transforma s en un estado s0 de la etapa k +1 y por la política óptima

desde el estado s0 hasta la etapa final.

La programación dinámica

2009-04-23T09:13:00.001-07:00

La programación dinámica es utilizada en compiladores, consiste en solucionar cierto problema diviendolo en subproblemas más sencillos, calculando sus resultados y almacenándolos.

Estos resultados posteriormente se utilizan para la resolución del problema final.

Almacenar resultados de subproblemas es una gran ventaja en cálculos dónde se repiten las mismas operación múltiples veces, mediante el método de la programación dinámica estas operaciones sólo se realizan una vez y se guarda la solución.

Se dice de la programación dinámica que es un método para resolver problemas que exhiben propiedades de problemas sobrepuestos y estructura óptima.