Como posso verificar uma solução para o problema do vendedor ambulante em tempo polinomial?

31

Portanto, o problema de decisão do TSP (problema do vendedor ambulante) é NP completo .

Mas não entendo como posso verificar se uma determinada solução para o TSP é de fato ideal no tempo polinomial, já que não há como encontrar a solução ideal no tempo polinomial (o que ocorre porque o problema não está em P)?

Alguma coisa que possa me ajudar a ver que a verificação pode realmente ser feita em tempo polinomial?

lazer
fonte

Respostas:

20

Para ser mais preciso, nós não sabemos se TSP está em . É possível que ele pode ser resolvido em tempo polinomial, embora talvez a crença comum é que PN P . Agora, lembre-se que isso significa para um problema a ser N P -Hard e N P -completo, ver por exemplo a minha resposta aqui . Acredito que sua fonte de confusão decorre das definições: um N P problema -Hard não é necessariamente em N P .PPNPNPNPNPNP

Como você e a página da Wikipedia vinculados afirmam, o problema de decisão é completo: dados os custos e um número inteiro x , decida se existe um passeio mais barato que x . Uma maneira de ver o problema em N P é ver que, dada uma solução, é fácil verificar em tempo polinomial se a solução é mais barata que x . Como você pode fazer isso? Basta seguir o tour fornecido, registrar seu custo total e finalmente comparar o custo total com x .NPxxNPxx

Juho
fonte
"Basta seguir o passeio dado, registrar seu custo total e finalmente comparar o custo total com x". -> Sim, mas há um número exponencial de passeios para conferir!
Lazer
2
Eu estava um pouco lento demais, ao que parece. ;-)
Niel de Beaudrap
3
@Lazer Não, há exatamente um tour para verificar. Você recebe um tour e registra sua duração. Se for menor que , produza sim , caso contrário não . x
21412 Juho
"decidir se existe um passeio", isso definitivamente significa que não temos um passeio. o que estou perdendo?
Lazer
3
@Lazer Não, no problema, você recebe um gráfico ponderado e um custo-alvo. O certificado é um tour. Para uma explicação alternativa, consulte a resposta de Niel. Assim como no exemplo no Wiki, no caso de SUBSET-SUM, não recebemos zero, mas, em vez disso, recebemos um subconjunto específico como certificado.
Juho
34

O ponto crucial é que você deve considerar o problema de decisão :

Problema do vendedor ambulante (versão de decisão). Dado um gráfico ponderado G e um custo alvo C , existe um ciclo hamiltoniano em G cujo peso é no máximo C ?

Para uma instância 'sim', o certificado é apenas um ciclo hamiltoniano cujo peso é no máximo C . Se você pudesse resolver esse problema com eficiência, poderia encontrar o custo de um passeio mínimo por pesquisa binária, começando com o peso de toda a rede como um limite superior.

Niel de Beaudrap
fonte
3

Você provavelmente está pensando no problema de determinar se uma determinada solução para o TSP é a melhor solução. No entanto, não há uma solução polinomial conhecida para isso, o que significa que esse problema é difícil no NP, mas não necessariamente no NP-Completo.

O Problema de Decisão da TSP é, na verdade, determinar se o peso de qualquer solução em um gráfico Gtem o maior custo C(como explicado melhor na resposta de Niel), o que certamente é verificável em tempo polinomial.

Casey Kuball
fonte
5
Desculpe pelo pedantismo, mas o TSP não é NP-difícil, porque existem passeios . Por exemplo, a classificação está em P, embora haja n ! possíveis permutações também. Espaços de pesquisa enormes ou em rápido crescimento nem sempre implicam dureza. O(n!)n!
Juho
@Juho É possível verificar se uma sequência está classificada, simplesmente verificando se . No entanto, para saber que algo é a melhor solução para o TSP, é necessário saber que o custo é o custo mínimo, o que exige inerentemente conhecer todos os outros custos. n0 0<=n1<=...
Casey Kuball
4
Não, você pode obter o melhor, mesmo sem calcular os comprimentos de todos os outros passeios. E sim, é possível provar que esse é realmente o ideal sem calcular todos os outros passeios. Por exemplo, considere branch & bound.
Juho
7
O(n22n)
@Juho bom ponto. Atualizei a resposta para não indicar mais a força bruta como a única opção (apenas que não existem soluções polinomiais).
Casey Kuball
2

MM . Nesse caso, deixe a borda para fora e continue. Caso contrário, coloque a borda de volta e continue. Quando você processar todas as bordas, ficará com um ciclo hamiltoniano de peso mínimo.

RecursivelyIronic
fonte