Problema do Caixeiro Viajante (8)


Muitos dos que estudam ou ensinam matemática associam à palavra algoritmo memórias da multiplicação ou da divisão inteira ou do cálculo da raíz quadrada, mais raramente à bissecção de um ângulo ou à realização de certas tarefas na programação de computadores. Temos tratado aqui de algoritmos completamente diferentes que são muito interessantes e definitivamente muito úteis em muitos problemas realistas, sendo ao mesmo tempo muito fáceis de compreender e aprender.

Consideremos um gestor de vendas responsável por dez cidades. Da sua agenda fazem parte dez apresentações de um novo produto, uma para cada um dos grupos de vendedores sediados em cada uma das cidades. O gestor terá de partir da sua cidade (uma das dez), deslocar-se a cada uma das restantes cidades e voltar a casa pelo mais curto caminho possível - uma solução óptima. O circuito que o gestor procura é um circuito de Hamilton (parte e volta à mesma cidade, visitando cada um das restantes cidades uma só vez; num grafo completo, pois há estradas(ou linhas aéreas) ligando cada par de cidades).

Este problema é um exemplo do famoso Problema do Caixeiro Viajante (PCV) da teoria de grafos (10, 4). Pesquisar sobre o melhor caminho tem importantes aplicações em muitos domínios, em especial nos domínios da economia e gestão. Óptimo ppode aqui siginificar mais curto, mais rápido, mais barato, etc. Outros aspectos da teoria de grafos envolvem problemas de optimização em circuitos telefónicos a estabelecer entre comunidades, recolha de lixo ou distribuição postal que precisam de pesquisa ao nível de encontrar percursos em que a passagem por todas as arestas é necessária (circuitos de Euler), ou para produzir circuitos electrónicos impressos.

Sendo limitado o orçamento para o gestor de vendas, este tem de tomar decisões ao nível do planeamento do circuito a fazer e isso quer dizer procurar um caminho em que a quilometragem total seja mínima. Em primeiro lugar, o gestor confirma que há estradas ligando todos os pares de cidades a visitar e isso é condição suficiente para a existência de um circuito de Hamilton (como já vimos).


voltar ao sumário