A alternativa correta é a letra C) II e III. I. A complexidade do problema do caixeiro viajante é NP-completo, ou seja, não se sabe se existe um algoritmo de tempo polinomial para resolvê-lo. Portanto, a afirmação está incorreta. II. A complexidade do problema de coloração de grafos é NP-completo, ou seja, não se sabe se existe um algoritmo de tempo polinomial para resolvê-lo. Portanto, a afirmação está incorreta. III. O objetivo do problema do caixeiro viajante é encontrar a rota de menor custo que passe por todos os vértices do grafo. A complexidade do problema é O(n!), que é exponencial. No entanto, existem algoritmos aproximados que resolvem o problema em tempo polinomial. Portanto, a afirmação está correta. IV. O problema da mochila é um problema de otimização que pode ser resolvido em tempo polinomial por meio de programação dinâmica. Portanto, a afirmação está incorreta. Assim, as afirmações corretas são II e III, e a alternativa correta é a letra C.
Para escrever sua resposta aqui, entre ou crie uma conta
Compartilhar