Un esquema paralelo basado en ramificación y acotación programación dinámica para el problema de la mochila 0/1
-
Autores: Francisco Almeida Rodriguez
, Casiano Rodríguez León , Félix César García López , Domingo Morales González , José Luis Roda García
- Localización: II Jornadas de informática. Actas: Almuñécar (Granada), 15 al 19 de julio 1996 / Buenaventura Clares Rodríguez (dir. congr.) , 1996, ISBN 84-8254-080-7, págs. 213-221
- Idioma: español
- Texto completo no disponible (Saber más ...)
-
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.
