Tenho solução! Escolhe a melhor, se conseguires!

Temos a ideia quase generalizada que a Matemática é uma Ciência Exacta e que nesse sentido que todos os Problemas têm um algoritmo que os resolve e todas as demonstrações já foram feitas. Melhor dizendo: está tudo feito! Na Matemática nada mais há para fazer! Este é o grande erro, na Matemática tudo está por fazer!

Existem problemas cuja resolução resiste alguns séculos até se encontrar uma demonstração ou uma solução. Sendo comum que se ofereça prémios em dinheiro para a solução de problemas de Matemática. Em 1905, foi instituído por Paul Wolfskehl, médico e matemático de Darmstadt, Alemanha, um prémio de 100.000 marcos alemães para quem resolvesse o Último Teorema de Fermat que só foi resolvido por Andrew Wiles em 1995, tendo o prémio sido entregue 1997 depois de inúmeras verificações e discussões apaixonadas. Mais recentemente uma editora anunciou um prémio de um milhão de dólares para uma demonstração da conjectura de Goldbach. Estamos a falar de problemas complexos e cuja resolução exige um domínio muito grande dos conceitos da Matemática, criatividade e imaginação.
Outro exemplo como a Hipótese de Riemann que envolve uma pergunta sobre números primos, levantada pelo matemático alemão Bernhard Riemann em 1859 e que resiste há mais de 150 anos sem solução ou “P versus NP” é bem mais actual, um problema ligado à ciência da computação e que cuja questão é se existe ou não um problema que é fácil para um computador verificar, mas incrivelmente difícil para ele resolver. E muito mais!

Mas voltemos a coisas mais concretas e que ilustram melhor esta ideia. Vejamos este problema que é colocado aos alunos do Ensino Secundário, quando se trabalha a Resolução de Problemas:
Dois amigos encontram-se na rua.

- Quantos filhos tens?
- Três.
- Que idades têm?
- O produto das idades é igual a 36.
- Ó pá, assim fico na mesma.
- Olha, então digo-te que a soma das idades deles é igual ao número desta porta - Apontando para uma porta.
- Mesmo assim, ainda não chega para eu descobrir.
- Pronto, então digo-te que o mais velho toca piano.
- Está bem, assim já sei!

É um problema que exige alguma destreza mental e cuja solução se encontra por exaustão, ou seja pela enumeração de todas as soluções admissíveis e que no final se escolhe a mais adequada.

Mas existem problemas que não podem ser resolvidos desta forma.
Um dos problemas de matemática cuja solução tem resistido à passagem do tempo é o Problema do Caixeiro-viajante. A sua descrição é muito simples.

Dada uma lista de cidades um vendedor, partindo de uma cidade inicial pretende visitá-las todas uma única vez, e regressar à cidade de partida de forma a que a distância percorrida seja mínima.

 Não se sabe ao certo quando este termo entrou nos círculos matemáticos, mas aponta-se como data provável 1931-32. A importância do problema do problema do caixeiro viajante aliado ao facto de que é um representante de uma classe muito vasta de outros problemas de Combinatórios, caracterizados por uma enorme simplicidade na formulação e uma enorme dificuldade na resolução.

O problema consiste em encontrar uma solução, ou seja uma lista de cidades, com um custo, de entre um conjunto muito grande de soluções e escolher aquela cuja distância seja menor, isto é um óptimo global. Este problema tem de facto uma, ou várias soluções óptimas, uma vez que o espaço de soluções é finito, no entanto o número de elementos deste conjunto é muito grande e cresce exponencial com o número de cidades a percorrer. Se tiver que encontrar a solução para 10 cidades demora, aproximadamente, três segundos; para 15 cidades demora seis meses e para 20 cidades um milhão de anos. Ou seja a solução não pode ser encontrada em tempo útil. A isto chama-se explosão combinatória!

Mas então as empresas de distribuição que operam em Moçambique, por exemplo, não entregam as mercadorias enquanto esperam por uma solução? Entregam!

Usamos para isso as Heurísticas, assim chamados porque a solução obtida pode não ser a óptima. São uma via inevitável para o cálculo de uma boa solução. A importância de encontrar uma heurística para o Problema do Caixeiro Viajante reside no facto de muitos problemas em muitos aspectos da nossa vida poderem ser formulados de igual forma.

Este é um Mundo fantástico da Matemática. A resolução de problemas inspira e faz transpirar muitos cientistas pelo Mundo fora no sentido de dar uma solução a problemas reais e para os quais é necessário muito trabalho, muita investigação, imaginação e perseverança.