Un esquema paralelo basado en ramificación y acotación programación dinámica para el problema de la mochila 0/1

  1. Almeida Rodriguez, Francisco
  2. Rodríguez León, Casiano
  3. García López, Félix César
  4. Morales González, Domingo
  5. Roda García, José Luis
Libro:
II Jornadas de informática. Actas: Almuñécar (Granada), 15 al 19 de julio 1996
  1. Clares Rodríguez, Buenaventura (dir. congr.)

Editorial: [Almuñécar?] : Asociación Española de Informática y Automática, [1996]

ISBN: 84-8254-080-7

Año de publicación: 1996

Páginas: 213-221

Congreso: Jornadas de Informática (2. 1996. Almuñécar)

Tipo: Aportación congreso

Resumen

Aunque la Programación Dinámica es una técnica de resolución de problemas muy importante y que ha sido ampliamente utilizada, es de conocimiento general que los problemas reales, los excesivos requerimientos de memoria y computacionales pueden provocar serias dificultades de implementación incluso en máquinas paralelas. Proponemos una extensión del algoritmo secuencial para programación dinámica a un algoritmo paralelo híbrido entre la ramificación y acotación y la programación dinámica, insertando test de cota inferior en el esquema de trabajode la programación dinámica. El algoritmo híbrido trabaja sobre redes en array lineal y anillos. Se muestran resultados computacionales para el problema de la mochila 0/1 tanto sobre redes de transputers utilizandol enguaje Inmos como en redes de área local usando PVM. Los resultados prueban que el algoritmo híbrido paralelo propuesto representa una alternativa adecuada para abordar los problemas de Programación Dinámica.