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
Book:
II Jornadas de informática. Actas: Almuñécar (Granada), 15 al 19 de julio 1996
  1. Clares Rodríguez, Buenaventura (dir. congr.)

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

ISBN: 84-8254-080-7

Year of publication: 1996

Pages: 213-221

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

Type: Conference paper

Abstract

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.