Trabalho elaborado no Centro Federal de Educação Tecnológica de Minas Gerais, com intuito de discutir sobre os algorítmos da computação que, ainda não se sabe ao certo se são capazes de atuar em um tempo polinomial.
- O problema escolhido por nosso grupo para demonstrar a capacidade de se resolver algo sem uma solução fixa, ou seja, um problema não polinomial, foi o "problema do caixeiro viajante" (traveling salesman problem - TSP). De acordo com o site Wikipedia, nele tentamos "determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Ele é um problema de otimização NP-difícil inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível".
Para ilustrar o problema, observe a imagem:
- Construído utilizando a linguagem C através do sistema operacional Windows 11 operando em ambiente Linux (WSL2 - Ubuntu-20.04). Para execução do programa siga os comandos abaixo:
make clean
make
make run
- Ao iniciar o programa serão exibidas três opções
- 1 - Redireciona para o menu de grafos da opção Brute Force
- 2 - Redireciona para o menu de grafos da opção Busca rápida
- 0 - Finaliza o programa
- Menu de opções de entrada para utilizar o Brute Force
- Menu de opções de entrada para utilizar o Busca Rápida
- Exemplo utilizando o método Brute Force (10 vértices)
- Exemplo utilizando o método Busca Rápida (10 vértices)
- O método de Busca Rápida para resolver o problema utiliza o sistema de backtracking, que auxilia ao percorrer o grafo fazendo isso uma única vez e em um único caminho, que já indica o menor caminho possível. Porém, fazendo isso ele descarta outras possibilidades por elas serem "redundantes" já que mudam a rota mas não o tamanho. Desse modo, essa é a explicação resumida do motivo de sua execução levar um tempo inferior, principalmente considerando os grafos com maiores quantidades de vértices. Já o método Brute Force testa todas as possibilidades da menor rota entre os vértices e por isso leva um tempo superior de execução.