Teoria da Complexidade e o Caixeiro Viajante

291 palavras 2 páginas
Resumo: Introduc¸ ˜ao a Teoria da Complexidade de modo a apresentar o porque os profissionais se preocupam tanto com esse estudo e explicar o problema do Caixeiro Viajante(NP).
Abstract: Introduction to Theory Complexity to explain why the professionall worried so much about this study and explain the problem of NP algorithms.
A Teoria da Complexidade ela estuda a eficiˆencia dos algoritmos de modo a calcular qual seria o melhor modo de faze-lo, ou seja, otimizar esse algoritmo para que ele se torne mais rapido ou que ocupe menos espac¸o de mem´oria. Um problema enfrentado ´e que para essa otimizac¸ ˜ao acontecer ela depende de v´arios fatores da maquina a ser utilizada, como o hardware, software, mem´oria dispon´ıvel, sistema operacional dentre outros. E para piorar a situac¸ ˜ao existe inumeras maquinas diferentes e um programa ´e feito para rodar em diferentes tipo de maquinas, portanto calcular qual a melhor maneira de se fazer um algoritmo n˜ao ´e t˜ao facil.
Outro problema ´e que existem algoritmos que nem se quer o homem chegou na soluc¸ ˜ao, porque para compilar tais programas demora-se milhares de anos, e um exemplo de algoritmos como esse ´e o do Caixeiro
Viajante, que ´e um problema matem´atico aparentemente simples mais sua estrutura ´e de crescimento fatorial. O problema acontece com um carteiro que vai de cidade em cidade e vocˆe tem que calcular a menor rota. Por´em o algoritmo precisa andar de rota por rota para calcular qual ´e menor, ou seja, se torna um problema de enumerac¸ ˜ao, como o crescimento ´e fatorial, n(numero de rotas) ´e elevad´ıssimo, fazendo com que a maquina mais rapida inventada at´e hoje demore milhares de

Relacionados

  • modeloPCV Caixeiro Viajante
    1786 palavras | 8 páginas
  • CAIXEIRO VIAJANTE 1
    1506 palavras | 7 páginas
  • O Problema do Caixeiro Viajante
    1455 palavras | 6 páginas
  • caixeiro viajante
    5556 palavras | 23 páginas
  • Otimização de transporte
    5575 palavras | 23 páginas
  • Resumo da origem e no que conssiste o problema do caixeiro-viajante
    607 palavras | 3 páginas
  • classes e subclasses NP
    2143 palavras | 9 páginas
  • NP-Completude
    1980 palavras | 8 páginas
  • Complexidade de Algoritmos - Problema P versus NP
    2189 palavras | 9 páginas
  • Otimozação de Sistema de transporte
    8694 palavras | 35 páginas