Mostrar registro simples

dc.contributor.advisorTrevisan, Vilmarpt_BR
dc.contributor.authorConte, Nelsonpt_BR
dc.date.accessioned2015-06-26T01:59:48Zpt_BR
dc.date.issued2002pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/118198pt_BR
dc.description.abstractO 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.pt_BR
dc.description.abstractThe 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.en
dc.format.mimetypeapplication/pdf
dc.language.isoporpt_BR
dc.rightsOpen Accessen
dc.subjectTeoria dos grafospt_BR
dc.subjectAlgoritmo de tempo polinomialpt_BR
dc.subjectModelos computacionaispt_BR
dc.subjectAlgoritmos numéricospt_BR
dc.titleO problema do caixeiro viajante, teoria e aplicaçõespt_BR
dc.title.alternativeThe traveling salespersor problem theory and applications en
dc.typeDissertaçãopt_BR
dc.identifier.nrb000339835pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Matemáticapt_BR
dc.degree.programPrograma de Pós-Graduaçãoem Matemática Aplicadapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2002pt_BR
dc.degree.levelmestradopt_BR


Thumbnail
   

Este item está licenciado na Creative Commons License

Mostrar registro simples