Geração das K-melhores soluções para o problema da mochila unidimensional em ambiente distribuído

Detalhes bibliográficos
Ano de defesa: 1996
Autor(a) principal: Rodrigo de Castro Penna Franca
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Instituto Tecnológico de Aeronáutica
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://www.bd.bibl.ita.br/tde_busca/arquivo.php?codArquivo=1643
Resumo: Este trabalho sugere um algoritmo para ambiente distribuído que determina as K-melhores soluções para o problema da mochila unidimensional. O algoritmo baseia-se no trabalho de Yanasse, Soma e Maculan (1995), que trata da mesma questão para ambiente serial. Entretanto, convém ressaltar que a versão distribuída do algoritmo possui profundas modificações em relação à versão serial. Primeiramente, o algoritmo serial foi estudado e totalmente implementado. A segunda etapa do trabalho foi o desenvolvimento do algoritmo distribuído. Parte desta tarefa tratou da escolha de uma abordagem de implementação no ambiente distribuído. Duas abordagens foram levadas em consideração e os respectivos algoritmos foram implementados e testados. O paradigma divide and conquer para algoritmos paralelos foi o que prevaleceu. Quanto ao ambiente operacional, o algoritmo serial foi desenvolvido, na sua fase inicial, sobre a plataforma 486/Windows e linguagem de programação C++. Posteriormente, portou-se a aplicação para o ambiente RISC/UNIX. O algoritmo distribuído foi desenvolvido em linguagem de programação C++ aliada às funções da biblioteca PVM, Parallel Virtual Machine (Máquina Paralela Virtual), em uma rede de estações UNIX. Resutaldos computacionais são apresentados.