Algoritmos paralelos para o problema da mochila.

AUTOR(ES)
DATA DE PUBLICAÇÃO

2003

RESUMO

Esta tese melhora o upper bound de tempo e de espaÃo da resoluÃÃo paralela do Subset-Sum Problem (SSP) - que à uma variante do Problema da Mochila - numa mÃquina PRAM SIMD CREW (Parallel Random Access Machine; Single Instruction/Multiple Data; Concurrent Read/Exclusive Write) nos dois paradigmas mais consagrados na literatura cientÃfica, isto Ã, tanto na abordagem atravÃs das listas como por programaÃÃo dinÃmica. Com relaÃÃo ao primeiro paradigma, à apresentada uma paralelizaÃÃo Ãtima e adaptativa do conhecido algoritmo das duas listas de Horowitz e Sahni (JACM, 1974) numa PRAM SIMD CREW de p processadores: ela resolve o SSP de n objetos em tempo O(2n/2/p) e espaÃo O(2n/2), onde 1  p <2n/2/n2. Como esse algoritmo seqÃencial tem atà hoje a melhor complexidade de tempo para a resoluÃÃo do Problema da Mochila, entÃo nosso algoritmo paralelo pode ser considerado, a partir de agora, como o melhor resultado teÃrico de toda a literatura. AlÃm disso, sÃo apresentados trÃs algoritmos paralelos adaptativos baseados no paradigma da programaÃÃo dinÃmica, que sÃo os primeiros a resolverem o SSP de n objetos e capacidade c em tempo o(nc/p) e espaÃo O(n+c) numa PRAM SIMD CREW de p processadores. Eles melhoram as complexidades de tempo e de espaÃo do algoritmo de Lin e Storer, (JPDC, 1991), que vinha sendo o mais eficiente atà o momento.

ASSUNTO(S)

processamento em paralelo (computadores) programaÃÃo dinÃmica problema da mochila programaÃÃo matemÃtica algoritmos pesquisa operacional

ACESSO AO ARTIGO

Documentos Relacionados