Então pessoal…
Sei que o caixeiro viajante está classificado como um problema NP. Alguém sabe qual é a complexidade real desse problema? Alguém conhece algum problema real com complexidade maior?
Certa vez eu vi uma tabela em que mostrava um comparativo entre complexidades, mostrando o tempo estimado que levaria (alguns ultrapassando a idade do universo). Queria essa tabela, alguém sabe onde posso encontrar?
De fato, ser NP não significa muita coisa. Significa apenas que o reconhecimento de um certificado (possível solução) é feita em tempo polinomial. Assim sendo, todo problema em P (para os quais se conhecem algoritmos determinísticos que os resolva em tempo polinomial) está em P.
A rigor, a complexidade do Caixeiro Viajante é (n-1)!. O fato de ser NP-Completo implica que resolvê-lo é tão difícil quanto resolver qualquer outro problema em NP. Ou seja, está entre os problemas “mais difíceis” em NP. Entretanto, existem determinadas configurações (por exemplo, Caixeiro Viajante Métrico), em que se conhecem bons algoritmos aproximativos, com uma razão, por exemplo, de aproximação igual a 2.
Essa tabela se encontra no livro do Garey and Johnson, “Computers and Intractability: A Guide to Theory of NP-Completeness”.
O algoritmo super ingenuo que é n-1!, da pra melhorar, mas continua exponencial ate onde conhecemos. Mas nada impede que alguem encontre algo super rapido :), a nao ser que P seja realmente diferente de NP.
A página da Wikipédia em inglês(como sempre), tem uma discussão bem longa sobre esse problemas, algoritmos para resolvê-lo, a complexidade de cada um, dê uma olhada.
Tem uma tabela que mostra a quantidade de passos aqui: http://www.codeproject.com/KB/recipes/GeneticandAntAlgorithms/table1.GIF
Ou:
Eu já vi essa tabela do tempo, mas não consigo mais achar a dita cuja.
Por falar em NP e P, a 1 ano atrás (até mais) um professor da UFPE falou, em uma apresentação, que ele iria provar que P = NP (ou diferente, não lembro), mas nunca ouvi mais falar nele :\
[editado]
Acho que achei:
Mais especificamente:
Cara, eu garanto que consigo achar o menor caminho entre 30 cidades em menos tempo que isso.
Tentar todas as possibilidades é um absurdo.
[quote=Bruno Laturner]Cara, eu garanto que consigo achar o menor caminho entre 30 cidades em menos tempo que isso.
Tentar todas as possibilidades é um absurdo.[/quote]
Ou me refraseando:
É perda de tempo querer saber a solução perfeita para o pior caso.
[quote=Bruno Laturner]Cara, eu garanto que consigo achar o menor caminho entre 30 cidades em menos tempo que isso.
Tentar todas as possibilidades é um absurdo.[/quote]
Oi bruno, mas voce vai ter de tentar um numero de possibiliades proporcional a todas as possibilidades, o que continua um absurdo, pois um zilhao dividido por 10, nao ajuda muito, entende? Sempre vai ser proporcional a n!. Mesmo que voce faca em n!/1000000, ainda é ruim demais para casos ate de tamanho pequeno.
Por isso que acho um absurdo, a solução não é expressa em fatorial. A árvore de possibilidades reais é muito menor que ela.
O menor caminho entre 30 cidades não é aquele que começa indo até a cidade mais longe de todas, mas pode ser aquele que começa indo até a 3ª mais perto.
Só acho ruim que esse problema não reflete a realidade, deixa de considerar zilhões de pesos para as rotas, necessidades humanas, comodidade, troncos principais de rotas comerciais, a predilência de se conectar a cidades importantes. Às vezes nem é importante chegar a menor rota, mas a melhor rota.
Aquela velha história de teoristas vs pragmatistas.
Mas aí é que está…Se você modelar todas essas necessidades humanas no teu modelo de problema, parece-me que várias abordagens de IA dão conta de encontrar uma solução razoável, mas nunca ótima…
A maior parte das necessidades humanas se satisfaz com uma solução razoável…Mas, sei lá…Imagine um problema em que se modele um fenômeno natural, em uma perspectiva física (nível atômico, sei lá), em que ocorre o caminho ótimo em uma instância do caixeiro viajante…Aí não tem choro. Se quiser determinar como ocorre o tal fenômeno dada uma determinada configuração, é preciso enconrar o caminho ótimo…
Esqueci!
Valeu aí galera…Eram exatamente essas tabelas que eu queria!
Oi Bruno!
Nao é tão menor não! Ou ao menos, não assintoticamente menor!
Entao, existem varios casos que um dos passos o caminho mais curto consiste em ir SIM a uma cidade que é a mais longe de todas (pense numa semi circunferencia, em algum momento voce precisa atravessar o diametro, considerando que ha duas cidades em cada uma das extremidades) ! Ta vendo como não é simples podar possibilidades? Se voce matasse esse caminho, nunca ia pegar o menor caminho…
Mas realmente muitas vezes o 2o ou 3o melhor caminho ja é mais que suficiente…
Meu orientador do TCC fez doutorado na alemanha onde eles implementaram na Siemens um TSP para reduzir custos que o braco mecanico tinha, o percorrer o caminho de um circuito integrado. Teve muita economia de dinheiro achando o menor caminho que o braco precisava percorrer para soldar todos os pontos do CI.
abracos
Acho que o publico que esta lendo este post pode se referenciar aqui !!!
Como anda o problema P = NP ?
http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext