Fluxo Maximo

de tentativas cresce exponencialmente. Sendo assim, torna-se essencial utilizar métodos heurísticos que amenizem essa exploração combinatória.
O PCV tem importantes aplicações práticas, tais como identificar itinerários de cobertura de regiões, como, por exemplo, a rota de um carteiro, visto que diminuir o trajeto pode significar economia de tempo e de pessoal. Outra aplicação prática é o processo de furação de placas para circuito impresso. Como
6
e-xacta, Belo Horizonte, v. 4, n.1, p. 5-16. (2011) Editora UniBH
Disponível em: www.unibh.br/revistas/exacta/ existem vários furos de diâmetros diferentes, e a troca da ferramenta pode demandar tempo, os furos de mesmo tamanho devem ser feitos de maneira sequencial, percorrendo-se a menor distância possível, para diminuir o tempo gasto numa produção em série.
Segundo Helsgaun (2000), esse problema, por ser combinatorial, tem (n-1)!/2 soluções possíveis para um conjunto de n nós, e que por isso é importante escolher uma boa heurística para obter uma solução viável: baixo custo computacional e, se possível, próxima da ótima. Ainda de acordo com o autor, o maior mapa com solução ótima conhecida é de 7.397 cidades, sendo que, a solução ótima conseguida com algoritmos exatos foi obtida por uma rede de computadores com entre três a quatro anos de processamento. Além disso, o autor destaca que o algoritmo heurístico proposto no seu estudo encontrou uma solução ótima em sete das dez tentativas com uma média de 3,6 horas.
Além dos algoritmos heurísticos, outras técnicas da IA podem ser aplicadas neste problema, dentre elas as redes neurais, que são eficientes por causa de sua adaptabilidade, ou seja, capacidade de aprendizado por treinamento; e os algoritmos genéticos, que são eficientes pela grande diversidade de soluções testadas e pela convergência através do cruzamento das soluções mais promissoras (baseado na seleção natural). Mais especificamente, as redes neurais são usadas