Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Elétrica. / Made available in DSpace on 2012-10-22T21:56:01Z (GMT). No. of bitstreams: 1
238306.pdf: 412990 bytes, checksum: 45884af398ed6a91e04edd7726745cd9 (MD5) / 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).
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufsc.br:123456789/89496 |
| Date | January 2006 |
| Creators | Shima, Ricardo Boveto |
| Contributors | Universidade Federal de Santa Catarina, Camponogara, Eduardo |
| Publisher | Florianópolis, SC |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | xiii, 71 f.| grafs., tabs. |
| Source | reponame:Repositório Institucional da UFSC, instname:Universidade Federal de Santa Catarina, instacron:UFSC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds