Existem problema que podem ser considerados complexos de ser resolver, pois exigem muito processamento de tal forma que aumentando a escala do problema o processamento necessário se torna inviável de ser realizado, podendo demorar anos processando.

Para resolver estes problemas, as pessoas normalmente adotam heurísticas, que são lógicas para se chegar a um resultado bom, mesmo que este não seja o melhor resultado possível.

Um exemplo clássico é o caso do caixeiro viajante, veja a imagem abaixo:

Problema do caixeiro viajante

Este problema  consiste em percorrer todas os vértices, partindo de um vértice inicial (A) e chegando novamente no vertice inicial, de tal forma que somente passe uma vez em cada vértice e que o percurso seja mínimo.

O nome deste problema como pode reparar na figura é Caixeiro Viajante.

Inicialmente existem várias maneiras de solucionar o problema, a mais fácil de se pensar é traçar todas rotas possíveis de tal forma a obter a menor soma dos caminhos, esta maneira garante que encontre o caminho mínimo necessário para o percurso, mas apenas funciona para cenários pequenos, pois a medida que a quantidade de vértices aumenta as ramificações da árvore de caminhos aumenta em uma grande proporção para cada novo vértice adicionado.

Assim, resolver tal problema pode demorar muito tempo para uma pessoa resolver e até mesmo para um computador, desta forma as pessoas começaram a fazer heurísticas para a decisão da melhor rota a ser tomada, de forma a dininuir o impacto de um novo vértice adicionado.

Neste simples exemplo, os possíveis caminhos seriam

D[B[A[C], C[A]], C[A[B], B[A]], A[C[B], B[C]]]

Desprezando a volta para o vértice inicial, formando assim 6 possíveis caminhos a seguir, partindo do vértice D.

Nos próximos artigos irei comentar sobre algumas heurísticas.