Algoritmos para o problema da árvore geradora mínima probalística

AUTOR(ES)
DATA DE PUBLICAÇÃO

2010

RESUMO

O Problema da Árvore Geradora Mínima Probabilística é uma generalização do problema clássico da Árvore Geradora Mínima em que se considera a situação na qual nem todos os nós estão deterministicamente presentes, mas estão presentes conforme uma determinada probabilidade. Dado um grafo, G=(V,E), que possui um custo associado a cada aresta em E e uma probabilidade de cada vértice em V estar ativo, pretende-se construir uma árvore geradora T em G a priori, tal que o custo ativo esperado de T seja mínimo. Este problema, provado como NP-Difícil em seu caso geral, possui aplicações em diversas áreas como roteamento, desenho de circuitos integrados, logística e telecomunicações. Nesta dissertação, a versão homogênea do problema, situação em que todos os nós têm a mesma probabilidade de estarem ativos, é descrita, analisada e resolvida através de heurísticas e algoritmos de busca local. Apresentam-se heurísticas construtivas capazes de encontrar soluções viáveis para o problema e, a partir de uma técnica que avalia os custos de soluções vizinhas de maneira eficiente, propõe-se a incorporação de algoritmos de busca local a um algoritmo de Busca Tabu - capaz de gerar soluções de melhor qualidade para o problema. Propõe-se também uma modelagem que permite a resolução do problema por Programação Inteira. A análise dos resultados revela que os algoritmos, quando comparados à resolução do modelo exato, mostraram ser uma ferramenta bastante eficiente para lidar com um problema computacionalmente difícil.

ASSUNTO(S)

teoria dos grafos teses. otimização combinatória teses. programação linear teses.

ACESSO AO ARTIGO

Documentos Relacionados