O objetivo principal deste trabalho é apresentar uma. descrição detalhada sobre as diversas abordagens do Problema do Caixeiro Viajante, a complexidade na sua resolução e as aplicações nas diversas áreas do conhecimento. O Problema do Caixeiro Viajante é um dos mais conhecidos e estudados problemas da Teoria dos Grafos e sua importância é tanta teórica quanto prática. O resultado teórico mais importante que apresentamos neste trabalho é a prova de que o PCV é -P-Completo, usando (e provando) o Teorema de Cook, como ponto de partida e a Máquina de Turing como o modelo computacional para as provas da complexidade dos problemas envolvidos. O PCV é equivalente ao problema de encontrar um circuito Hamiltoniano de peso mínimo em um grafo ponderado. Uma das questões principais envolvidas neste problema, e na verdade uma das principais indagações da Ciência da Comput ação, é saber se existe um algoritmo eficiente de tempo polinomial para calcular tal circuito, ou se tal algoritmo não existe, caracterizando-o, assim, como um problema impossível de ser resolvido. Quando não se pode encontrar uma solução eficiente para um dado problema e também não pode ser demonstrado que tal solução existe, deve-se usar técnicas que permitam construir um algoritmo que forneça soluções aproximadas. Neste trabalho, apresentamos um algoritmo de tempo polinomial que nos fornece soluções aproximadas para o PCV. / The main objective of this work is to present a detailed description on the various approaches to the Traveling Salesperson Problem (TSP), the complexity of its solution and its applications to the various knowledge area.s. The Traveling Salesperson Problem is one of the most known and studied problems in graph theory and its importance is theoretical as well as practical. The theory result more important who we will introduce in this work is the proof of the TSP is NP-complete, using (and proving) of Cook's Theorem like point of departure and the Turing Machine like the model computational for the tests of complexity of problems involved. The TSP is equivalent to the problem of finding a Hamiltonian circuit of minimal weight in a weighted graph. One of the main questions involved in this problem, and actually one of the main questions of the whole Computing Science, is to know if there exists an polynomial-time efficient algorithm to compute such a circuit, or if such an algorithm can not exist, then characterizing it as an impossible problem. When one can not find an efficient solution for a given problem and also can not show that such a solution exists, we must use techniques that aid us to construct an algorithm providing approximate solutions. In this work, we will present a polynomial-time algorithm that gives approximate solutions for the solution of the Traveling Salesperson Problem.
| Identifer | oai:union.ndltd.org:IBICT/oai:lume56.ufrgs.br:10183/118198 |
| Date | January 2002 |
| Creators | Conte, Nelson |
| Contributors | Trevisan, Vilmar |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, instname:Universidade Federal do Rio Grande do Sul, instacron:UFRGS |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0022 seconds