Un esquema paralelo basado en ramificación y acotación programación dinámica para el problema de la mochila 0/1
- Almeida Rodriguez, Francisco
- Rodríguez León, Casiano
- García López, Félix César
- Morales González, Domingo
- Roda García, José Luis
- 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.