Caminhos mínimos sob restrições: uma revisão e aplicações

Abstract

O problema clássico de caminhos mínimos pode ser resolvido com algoritmos conhecidos de tempo de execução polinomial. Mas quando restrições de tempo ou recursos são impostas ao problema, este se torna NP-Difícil. Este problema é conhecido como problema de caminhos mínimos sob restrições e são estudados neste trabalho a sua modelagem, algoritmos e aplicações. O algoritmo de programação dinâmica e o de aproximação-e são os métodos de maior destaque, que nesta dissertação foram implementados e exemplificados. No presente trabalho são apresentados aplicação em diversos contextos: em agentes móveis, em tráfego urbano e em redes de computadores. No contexto de agentes móveis este tipo de algoritmo pode resolver problemas como o escalonamento de tarefas com restrição de tempo de execução, ou seja, com um deadline. Em redes de tráfego veicular pode auxiliar na resolução de um problema mais complexo, ou simplesmente obter o caminho mais rápido com restrições orçamentárias. E por fim, em rede de computadores pode criar rotas que satisfazem métricas de Qualidade de Serviço (QoS).