Programación dinámica paralela para problemas de mochila 0/1

  1. Almeida Rodriguez, Francisco
  2. Morales González, Domingo
  3. García López, Félix César
  4. Rodríguez León, Casiano
Liburua:
I Jornadas de informática. Actas: Puerto de la Cruz, 17-21 de julio de 1995
  1. Troya Linero, José María (dir. congr.)
  2. Rodríguez León, Casiano (dir. congr.)

Argitaletxea: Asociación Española de Informática y Automática

Argitalpen urtea: 1995

Orrialdeak: 415-425

Biltzarra: Jornadas de Informática (1. 1995. Puerto de la Cruz)

Mota: Biltzar ekarpena

Laburpena

Se estudia la paralelización de una técnica de programación dinámica para resolver el problema de la mochila 0/1 en redes de transputers desde cuatro diferentes perspectivas. El primer algoritmo divide el conjunto de capacidades entre los procesadores disponibles y combina las soluciones parciales, mientras que los otros tres algoritmos consideran diferentes alternativas de partición del conjunto de objetos. Los resultados del análisis de complejidad teórica son contrastados con los resultados computacionales obtenidos al ejecutar los algoritmos sobre redes de transputers con diferentes tipologías.