Mostrar código-fonte de Problema do caixeiro-viajante

{{sem-notas|data=Agosto de 2013}}
{{Formatar referências|data=fevereiro de 2013}}
{{Reciclagem|data=junho de 2011}}

O '''problema do caixeiro-viajante'''  ('''''PCV''''') é um problema que tenta 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 combinatória|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.

== Fatos históricos ==
A origem do nome «''travelling salesman problem''» é desconhecida. Não parece existir qualquer documento que prove o(a) autor(a) do nome do problema. Merril Flood, da [[Universidade de Princeton]], um dos investigadores mais proeminentes nas primeiras aplicações do problema proferiu, no entanto, o seguinte comentário: «I don´t know who coined the peppier name "Traveling Salesman Problem" for ''Whitney's'' problem, [...]» [[#refcApplegate2006|(Applegate et al., cop. 2006, p. 2)]].

Nos anos de 1800, problemas relacionados com o PCV começaram a ser desenvolvidos por dois matemáticos: o escocês [[William Rowan Hamilton]] e o britânico Thomas Penyngton Kerkman. A forma geral do PCV parece ter sido, pela primeira vez, estudada por matemáticos nos anos de 1930 em [[Universidade Harvard|Harvard]] e [[Universidade de Viena|Viena]]. O problema foi posteriormente estudado por Hassler Whitney e Merril Flood em Princeton. Exceptuando pequenas variações ortográficas, como ''traveling'' vs ''travelling'' ou ''salesman'' vs ''salesman's'', o nome do problema ficou globalmente conhecido por volta do ano 1950 [[#refcApplegate2006|(Applegate et al., cop. 2006, p.2)]].

== Definição e formulação do problema ==
[[Ficheiro:Example The travelling salesman problem (TSP).gif|thumb|right|400px|Figura 1. Problema do caixeiro-viajante.]]

O problema do caixeiro-viajante (representado na Figura 1) consiste na procura de um circuito que possua a menor distância, começando numa cidade qualquer, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial <span id=refbNilsson1982>[[#refNilsson1982|(Nilsson, 1982)]]</span>.

; Formulação combinatória
Dado um conjunto <big><math>C=\{ c_1\;, ...,\;c_n \}</math></big> de ''n'' cidades ''c<sub>i</sub>'' e uma matriz de distâncias <big><math>\left ( \rho_{ij} \right )</math></big>, onde <big><math>\rho_{ij}=\rho( c_i,\;c_j )</math></big> <big><big><math>(</math></big></big> <math>i,\;j</math> <big><math>\in</math></big> <big><math>\{ 1,\;...,\;n \}</math></big>,  ''<big><big><math>\rho_{ij}</math></big></big>'' ''<big><big><math>=\rho_{ji}</math></big></big>'', ''<big><big><math>\rho_{ii}</math></big></big>''<big><big><math>=0 )</math></big></big>, a tarefa passa por encontrar a [[permutação]] <math> \pi \in S_n = \{ s : \{ 1, ..., n \} \rightarrow \{ 1, ..., n \} \}</math> que faça com que a função objectivo (distância do circuito) <math>f : S_n \rightarrow \mathbb{R}</math>, onde

          <math>f ( \pi ) = \sum_{i=1}^{n-1} \rho\pi( i ), \pi( i+1 ) + \rho\pi( n ), \pi( 1 )</math>,

atinja o seu [[mínimo]].

O tamanho do espaço de procura aumenta exponencialmente dependendo de ''n'', o número de cidades, uma vez que existem

          <math>( n-1 )!/2 \approx {1 \over 2}\sqrt{2\pi( n-1 )}\left ( \frac{n-1}{e} \right )^{n-1}</math>

circuitos possíveis (a posição inicial é arbitrária, e a ordem do circuito pode ser invertida).

Embora tenham sido desenvolvidos bons [[algoritmos]] de aproximação para o PCV, o problema continua a oferecer uma grande atracção para a aplicação de novos algoritmos, tais como os evolucionários. Isto deve-se, essencialmente, às seguintes razões:

* A problemática do PCV pode ser entendida facilmente, uma vez que se aproxima dos problemas populares do mundo real;
* O PCV demonstra o caso mais simples dos problemas de requisição que são de enorme relevância para a programação de processos industriais;
* Existem vários conjuntos de dados sobre o PCV «standard» que estão disponíveis em literatura, de tal forma que os resultados são comparáveis mesmo que o óptimo global não seja ainda definitivamente conhecido;
* Relativamente à complexidade computacional, o PCV, como um problema [[NP-completo]], é conhecido por representar uma larga classe de problemas para os quais não existem algoritmos polinomiais em [[séries temporais]] determinísticos.

; Representação continua do PCV
A topologia de um PCV pode ser visualizada segundo uma representação contínua do problema:

          <math> \vec x \in [u, v]^n ; u, v \in \mathbb{R} </math>

Partindo de   <math>\ \vec x\ = (x_{1}, ..., x_{n}) \in [u, v]^n\ </math> , uma permutação   <big><math> \pi </math></big>   pode ser obtida através de uma ordenação das componentes do [[vetor (espacial)|vector]], que originam um novo vector <math>\vec x^\prime\ = (x_{\pi(1)}, ..., x_{\pi(n)})</math>   de tal forma que   <big><math>\ x_{\pi(1)}\;<\;x_{\pi(2)}\;<\;x_{\pi(n)}\ </math></big>.    A nova ordem   <big><math>\  \pi(1),\;\pi(2),\;\pi(n)\ </math></big> é interpretada como o circuito resultante da permutação <span id=refbBäck1996>[[#refB&auml;ck1996|(B&auml;ck, 1996)]]</span>.

; Formulação gráfica
No domínio da [[teoria dos grafos]], cada cidade é identificada com um nó (ou vértice) e as rotas que ligam cada par de nós são identicadas como arcos (ou arestas). A cada uma destas linhas estarão associadas as distâncias (ou custos) correspondentes. Desde que seja possível ir directamente de uma cidade para qualquer outra, o gráfico diz-se completo. Uma viagem que passe por todas as cidades corresponde a um [[caminho hamiltoniano|ciclo Hamiltoniano]], representado por um conjunto específico de linhas. A distância do ciclo é o somatório das distâncias das linhas presentes no mesmo.

Formalmente, o problema pode ser representado por um [[grafo]] G(V, E), com <math>|V| \ge 3</math> e custos <big><big><math>c_{ij}</math></big></big>,  ''<math> \left ( i,\;j \right )</math>'' <math>\in E</math>, referentes a cada uma das arestas. O objectivo, no caso de um [[grafo completo]] com ''n'' vértices (cidades) é encontrar o melhor circuito entre os <big><math> [(n-1)!/2]</math></big> possíveis.

Dependendo da importância que poderá ter o sentido das setas(arestas), entre nós(cidades), o PCV pode-se distinguir em simétrico ou assimétrico <span id=refbGuedes2005>[[#refGuedes2005|(Guedes, 2005)]]</span>.

; PCV assimétrico
Dependendo da importância que a direção das arestas que atravessam o grafo possam ter, distingue-se o PCV assimétrico do simétrico. Para formular o PCV assimétrico em ''m'' cidades, introduzem-se variáveis zero ou um:

          <math>x_{ij} = \begin{cases} 1,  & \mbox{se }i \rightarrow j\mbox{ existe} \\ 0, & \mbox{se }i \rightarrow j\mbox{ não existe} \end{cases}</math>

Assim, e dado o facto de que a cada nó do grafo apenas pode corresponder e sair uma seta (Figura 2), um obtém uma atribuição clássica do problema. Estas restrições, contudo não são suficientes, uma vez que esta formulação permite a ocorrência de subcircuitos, ou seja, mesmo respeitando as condições impostas, considera-se a formação de aglomerados de cidades sem ligação. Por esta razão, a formulação do problema tem que possuir condições necessárias para remoção de subcircuitos. Assim, o problema é reformulado da seguinte forma:

[[Ficheiro:TSP degree constraints.png|thumb|right|300px|Figura 2. Entrada e saída de uma seta por cada nó.]]

          <center><math>{\rm min} \sum_{j=1}^{m} \sum_{i=1}^{m} c_{ij} x_{ij}</math></center>

          <center><math>{\rm Sujeito}\,{\rm a}: \sum_{j=1}^{m} x_{ij}=1 \qquad \qquad \forall i = 1, ..., m</math></center>

          <center><math>\sum_{i=1}^{m} x_{ij}=1 \qquad \qquad \forall j = 1,..., m</math></center>

          <center><math>\sum_{i \in K} \sum_{j \in K} x_{ij} \le |K| - 1 \qquad \qquad \forall i, j</math></center>

          <center><math> x_{ij} = \{0,1\} \qquad \qquad \forall i,j</math></center>

Onde:

* ''K'' é um [[subconjunto]] não vazio apropriado das cidades ''1, ..., m'';
* O custo <big><math>c_{ij}</math></big> pode ser diferente do custo <big><math>c_{ji}</math></big>;
* Existem ''m(m-1)'' zero-um variáveis.

; PCV simétrico
Para formular o PCV simétrico, um demonstra que a direcção atravessada é imaterial, de modo que <big><math>c_{ij}</math></big> = <big><math>c_{ji}</math></big>. Uma vez que a direcção não tem interesse, um pode considerar o gráfo onde existe apenas um arco, sem direcção, entre todos os pares de nós. Assim, <math>x_{j}\ \varepsilon\ {0,1}</math> é a variável de decisão onde ''j'' percorre todos os arcos ''E'' do grafo, sem direcção, e <big><math>c_{j}</math></big> é o custo de percorrer cada troço. Para encontrar um circuito neste gráfo, um, deve seleccionar um subconjunto de arcos, tal que todos os nós estejam contidos exactamente em dois dos arcos seleccionados. Assim, o problema pode ser formulado como um problema 2-''matching'' no gráfo <math>G^V</math> com ''m(m-1)/2'' zero-um variáveis, isto é, metade do número da formulação anterior. Tal como no caso assimétrico, os subcircuitos devem ser eliminados através de restrições de eliminação de subcircuitos. O problema pode então ser formulado como:

          <center><math> {\rm min}\ \frac{1}{2}\sum_{j=1}^{m} \sum_{k \in J(j)} c_{k}\ x_{k}</math></center>

          <center><math> {\rm Suj.a:} \sum_{k \in J(j)} x_{k}=2 \qquad \qquad \forall j=1, ..., m</math></center>

          <center><math> \sum_{j \in E(K)} x_{j} \le |K| - 1 \qquad \qquad \forall K \subset {1, ..., m}</math></center>

          <center><math> x_{j} = \{0,1\} \qquad \qquad \forall j \varepsilon E</math></center>

onde ''J(j)'' é o conjunto de todos os arcos, não direccionados, ligados ao nó ''j'' e ''E(K)'' é o subconjunto de todos os arcos, não direccionados, que ligam as cidades em qualquer subconjunto ''K'' não vazio apropriado de todas as cidades.

É evidente que o problema simétrico é um caso especial do assimétrico, mas experiências práticas demonstram que os algoritmos para o problema assimétrico, regra geral, desenvolvem mal no simétrico. Assim, este tipo de problemas requerem formulações especiais e tratamentos de soluções <span id=refbHoffman2000>[[#refHoffman2000|(Hoffman, 2000)]]</span>.

== Tipologia de métodos para a resolução do PCV ==
A solução do PCV pode ser determinada por diferentes métodos. Estes, podem ser agrupados em métodos exactos e heurísticos. Os primeiros têm por base procedimentos {{Link|en|http://en.wikipedia.org/wiki/Branch_and_bound|''branch-and-bound'' |4=, isto é, de enumeração implícita em árvore onde é necessário inserir um limite inferior, no leque de soluções do problema. Existem limites inferiores triviais, como por exemplo, o elemento mínimo das soluções encontradas. Contudo, este tipo de métodos demonstram muita dificuldade quando aplicados a problemas muito complexos, isto é, um PCV com muitas cidades, uma vez que a árvore de enumeração é muito extensa <span id=refbConway2003>[[#refConway2003|(Conway, 2003)]]</span>.}}

Os métodos heurísticos são procedimentos bastante particulares, o que os torna inflexíveis para a determinação de boas soluções para um outro problema ligeiramente diferente.

As heurísticas podem ser agrupadas em métodos de construção de circuitos e métodos de melhorias de circuitos.

; Métodos de construção de circuitos
Nestes métodos, o circuito é construído sequencialmente, isto é, os nós vão sendo inseridos faseadamente, mediante certas condições, sem que exista qualquer modificação posterior à inserção definida pelo processamento do algoritmo.

A construção do circuito pode ser elaborada através dos seguintes métodos:

* [[Algoritmo do vizinho mais próximo|Vizinho mais próximo]], que é caracterizado pela escolha da cidade mais próxima, sempre que o caixeiro se desloque, até que todas as cidades sejam visitadas;
* De inserção, que se descreve pela inclusão de cidades, uma a uma, atendendo a um determinado critério de proximidade, por exemplo, a cidade mais distante, partindo de um circuito inicial com duas cidades. Aquando da inserção, a escolha deve ser analisada entre cada par de cidades do circuito parcial, até que todas estejam inseridas;
* Da [[Árvore de extensão mínima|cobertura mínima]], onde é elaborada um árvore que contenha todas as cidades, com a finalidade de se encontrar uma árvore de cobertura com a menor soma de distâncias possível;
* Das economias, ou [[heurística de Clarke e Wright]], que consiste no agrupamento sequencial de cidades, com base numa ordem decrescente de economias decorrentes da sua inclusão, isto é, considerando o impacto, da junção do nó no circuito, nas economias agregadas da distância entre nós e da distância de cada um dos nós ao nó inicial [[#refcCunha2002|(Cunha, 2002)]] e <span id=refbGoodrich1899>[[#refGoodrich1899|(Goodrich, 1899)]]</span>.
* [[Algoritmo de Christofides]], cuja ideia geral é: criar uma árvore geradora mínima T; criar um subgrafo M induzido pelo acoplamento perfeito dos nós de grau ímpar da árvore T, formar um multigrafo H com a união de T e M, gerar um circuito Euleriano em H e, por fim, eliminar os nós repetidos do circuito.

; Métodos de melhoria de circuitos
Estes métodos procuram melhorar o circuito obtido através de algum outro método. Para tal, o método mais utilizado, elaborado por Lin e Kernighan em 1973, denomina-se por ''k-opt''. Nesta proposta, ''k'' arcos são substituídos, no circuito, por outros ''k'' arcos com o objectivo de diminuir a distância total percorrida.
Quanto maior for o valor de ''k'', melhor é a precisão do método, mas maior é o esforço computacional.

Com a variação do valor ''k'', no método de melhoria ''k-opt'', a heurística de Lin e Kernighan aumentaria a sua eficiência quando comparada com o mesmo método utilizando um valor de ''k'' fixo. Desta forma, o método não fica mais simples, contudo passa a ser possível a aplicação do método a problemas mais abrangentes com resultados favoráveis.

Para além deste método, existem outros métodos de melhorias baseados em [[metaheurística]]s do tipo ''[[simulated annealing]]'' e [[Pesquisa tabu|busca tabu]]. Estes, para além de se basearem no desenvolvimento ''k-opt'', procuram uma solução que não a dada pelos métodos anteriores. No ''simulated annealing'' é utilizado um controlo de possibilidades de solução melhores partindo de piores, no início. Na busca tabu os movimentos considerados tabu, isto é, que não se podem efectuar, mesmo que melhorem a solução são temporariamente interditos com o objectivo de se alcançar soluções piores no início que no final poderão ser consideradas melhores (Laporte, 2002) e (Heslgaun, 2000), citados por [[#refcCunha2002|(Cunha, 2002)]].

== Exemplos ==
=== WRNN e WTA ===
A [[rede neural]] periódica de Wang, do inglês ''Wang Recurrent Neural Network'' (WRNN), com o princípio ''Winner Takes All'' (WTA), pode ser aplicada para a resolução do PCV. Além disso, a utilização do princípio WTA nas soluções encontradas pelo WRNN faz com que as mesmas formem circuitos exequíveis. Como tal, este é um método de construção (WRNN) e de melhoria (WTA) de circuitos.

O número médio de iterações necessárias para a resolução do PCV  utilizando o WRNN é de 4463, com o WRNN + WTA é de 41, isto em problemas que variam entre 3 x 3 e 20 x 20.

A WRNN é caracterizada por uma equação diferencial, que engloba uma função do tipo [[Função sigmóide|sigmóide]]. Os vários parâmetros incluídos nas equações afectam a convergência da rede, pois trata-se de factores penalizantes pelas violações às restrições do problema, de controlo para a minimização da função objectivo, entre outros. Esta formulação possui ainda um termo que avalia as violações às restrições do problema dando a indicação do cumprimento das mesmas, após um certo número de iterações. Depois de encontrados tais parâmetros, aplica-se o princípio WTA que pode ser dado através do seguinte algoritmo:

1) Determinar o número máximo de circuitos r<sub>max</sub> e encontrar uma solução  para o problema utilizando a técnica WRNN. Se o termo que avalia as restrições for satisfeito, segue-se para o passo 2, caso contrário encontra-se outra solução x.

2) Dada uma matriz de decisão, considera-se uma matriz <math> \overline{x}</math>, onde <math> \overline{x}</math> = x = <math>x</math>;

3) Escolhe-se uma linha ''k'' na matriz de decisão <math> \overline{x}</math>. Faz-se ''p'' = ''k'', <math>x^\prime (m) = k</math>:

4) Encontra-se o maior elemento da linha ''k'', <math> \overline{x}_{kl}</math>. O valor deste elemento é dado por metade do somatório de todos os elementos da linha ''k'':

          <math> \overline{x}_{kl} = \frac{1}{2} \left (\sum_{i=1}^{n} x_{il} + \sum_{j=1}^{n} x_{kj}  \right )</math>

Os outros elementos da linha ''k'' e da coluna ''l'' passam a ser nulos. Para que não exista a formação de sub circuitos os elmentos da coluna ''k'' têm, também, que ser nulos. Depois destas condições, faz-se  <math>x^\prime (m + 1) = l</math> e avança-se para o passo 5.

5) Se ''m'' < ''n'', então faz-se ''m = m + 1'' e retorna-se ao passo 4. Caso contrário, aplica-se a seguinte expressão:

          <math> \overline{x}_{kp} = \frac{1}{2} \left (\sum_{i=1}^{n} x_{ip} + \sum_{j=1}^{n} x_{kj} \right )</math>

A equação <math>x^\prime (n + 1) = p</math>  determina o custo do circuito, ''z''.

6) Se ''z'' <''z<sub>min</sub>'', faz-se z<sub>min</sub> = z e x = <math> \overline{x}</math>. De seguida verifica-se se ''r'' <''r<sub>max</sub>'' pela equação ''r'' = ''r + 1''. Se tal acontecer, inicia-se o procedimento do WRNN no passo 2, caso contrário finaliza-se o algoritmo.

Este procedimento pode ser aplicado tanto ao PCV simétrico como ao assimétrico <span id=refbSiqueira2006>[[#refSiqueira2006|(Siqueira, 2006)]]</span>.

=== [[Algoritmos genéticos]] ===
Os algoritmos genéticos (AGs) são um dos vários métodos que se utilizam para a resolução de problemas complexos. Este método tem por base um processo iterativo sobre uma determinada população fixa, denominados por indivíduos, que representam as várias soluções do problema. Esta técnica advém do processo de evolução dos seres vivos demonstrada por Darwin.

Da mesma forma que os sistemas biológicos, ao longo da sua evolução, tiveram que se «moldar» às alterações ambientais para a sua sobrevivência, os AGs acumulam a informação sobre o ambiente com o intuito de se adptarem ao novo meio. Tal informação funciona como um sistema de triagem para a obtenção de novas soluções exequíveis.

O método dos algoritmos genéticos é muito utilizado devido à simplicidade de operação, eficácia pela determinação de um máximo global e aplicabilidade em problemas onde se desconhece o modelo matemático ou onde o mesmo se torna impreciso em [[função linear|funções lineares]] e não-lineares <span id=refbCosta2003>[[#refCosta2003|(Costa, 2003)]]</span>.

==== Método de aplicação ====
A formação de um algoritmo genético convencional desenvolve-se através dos seguintes passos:

# Representação de uma solução (Loco) na estrutura do [[cromossoma]];
# Construção de uma população (indivíduos) inicial de cromossomas;
# Mecanismo para avaliação dos cromossomas mediante as suas características;
# Mecanismo para reprodução de cromossomas, designado por operador genético;
# Definição dos parâmetros de um AG.

Para o desenvolvimento do primeiro passo, deve-se ter em consideração que a representação tradicional de um algoritmo genético é feita por [[Sistema binário (matemática)|binários]] (zero-um). Esta representação, embora eficiente, torna-se cada vez mais limitada à medida que o número de restrições do problema cresce. Desta forma, convencionou-se a utilização de um vector, formado por números inteiros, para a representação de um cromossoma.

Qualquer que seja a representação escolhida, a mesma deve verificar uma associação correcta com as soluções do problema em estudo. Isto é, para cada solução deve existir um cromossoma associado, atribuído pelo AG, e vice-versa.

Para o PCV a representação que mais se adequa é a dos números inteiros. Tal facto, deve-se à possibilidade de obtenção de soluções, por sequência de três bits, além do número de cidades do problema.

Para a construção de uma população inicial de cromossomas (passo 2), o AG demonstra uma capacidade bastante alta. Pegando num exemplo de um PCV com ''n'' cidades, a tarefa de se obter ''k'' soluções exequíveis numa estrutura de ''k'' cromossomas, mediante a utilização da representação por números inteiros, tem o mesmo significado que a obtenção de ''k'' vectores com ''n'' números inteiros, de ''1'' a ''n'' e diferentes entre eles. Caso a obtenção da população inicial de cromossomas seja difícil, isto é, caso o problema tenha vários parâmetros e restrições, torna-se mais fácil e rápido a utilização de heurísticas simples.

A avaliação dos cromossomas num AG, faz-se considerando a capacidade de sobrevivência dos cromossomas. Num PCV, esta capacidade de sobrevivência é relativa ao valor da função objectivo, que por sua vez, é avaliada pelo cromossoma associado. Para um PCV com ''n'' igual a 5 cidades, por exemplo, a capacidade do cromossoma é avaliada consoante o custo ''D'', referente à soma das distâncias ''(<math>d_{ij}</math>)'':

          <big><math>D = d_{12} + d_{23} + d_{34} + d_{45} + d_{51}</math></big>

Assim, quanto menor o ''D'', maior é o nível de aptidão do cromossoma.

O operador genético é o núcleo de um AG e o seu objectivo passa pela produção de novos cromossomas, com propriedades superiores relativamente aos que lhes deram origem.

[[Ficheiro:Computational.science.Genetic.algorithm.Crossover.One.Point.svg|thumb|right|250px|Figura 3. Exemplo de ''crossover'' de um ponto, ou seja, um ''crossover'' com apenas uma quebra no cromossoma.]]

Nos AG convencionais, os operadores genéticos mais utilizados são a [[mutação]] e o {{Link|en|http://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)|''crossover'' |4=(Figura 3). O primeiro consiste numa alteração de genes de um cromossoma consoante a função probabilidade. O ''crossover'' consiste na produção de um ou dois cromossomas filhos, denominados como ''offsprings'', com base nas informações dos dois cromossomas pais. Este operador demonstra uma determinada eficiência consoante a representação utilizada. Salienta-se que caso a representação adoptada seja a binária, é normal a produção de soluções não exequíveis, como referido anteriormente.}}

Estes dois tipos de operadores, embora simples, têm a particularidade de não conseguirem dar uma resposta adequada quando confrontados com problemas de elevada complexidade.

Os parâmetros de um algoritmo genético que se devem ter em consideração, aquando da sua implementação, diferem entre autores. De uma maneira geral, os parâmetros são os seguintes:

* Tamanho da população;
* Selecção dos cromossomas reprodutores;
* Critério de sobrevivência dos cromossomas;
* Critério de finalização de um AG.

Sendo o PCV um problema de optimização muito complexo, o AG convencional é um método relativamente ineficaz quando comparado com outras heurísticas desenvolvidas. Desta forma, o AG sofreu vários desenvolvimentos com o intuito de dar resposta às condições propostas pelos problemas. A este conjunto de algoritmos genéticos dá-se o nome de algoritmos genéticos não convencionais <span id=refbOchi1998>[[#refOchi1998|(Ochi, 1998)]]</span>.

=== [[Otimização da colônia de formigas|Algoritmo ACO]] ===
O PCV tem um papel importante na [[Otimização da colônia de formigas|optimização das colónias de formigas]], {{Link|en|http://en.wikipedia.org/wiki/Ant_colony_optimization|''ant colony optimization'' (ACO) |4=, desde o primeiro algoritmo ACO, chamado «Sistema de Formigas», do inglês ''Ant System'', até aos mais recentes.}}

O PCV foi escolhido por muitas razões:

* É um problema para o qual os algoritmos ACO são facilmente aplicados;
* É um problema de optimização NP-difícil;
* Serve de teste para a aplicação de novos algoritmos, e um bom desempenho no PCV é muitas vezes tido em consideração como prova da sua utilidade;
* É um problema facilmente perceptível, o que faz com que a linha de desenvolvimento de um algoritmo não se difunda em demasiados aspectos técnicos.

Nos algoritmos ACO, as formigas são simples agentes que, no caso do PCV, constroem circuitos através do movimento entre cidades no grafo do problema. A solução construída pelas formigas é elaborada por trilhos de [[Feromônio|feromonas]] (artificiais) e pela disponibilidade de informação heurística, à priori. Quando o algoritmo ACO é aplicado, é associada uma força da feromona , onde <big><math>\tau_{ij}(t)</math></big> é uma informação numérica que é modificada durante o algoritmo, e ''t'' é o contador das iterações.

Para o PCV simétrico, o algoritmo ACO caracteriza-se por <big><math>\tau_{ij}(t) = \tau_{ji}(t)</math></big>. No assimétrico a igualdade pode ser desfeita por  <math>\ne</math> <math>\tau_{ji}(t)</math>.

Inicialmente, cada uma das ''m'' formigas é colocada numa cidade, de forma aleatória, aplicando-se depois, de modo iterativo, uma regra de transição de estado para cada uma das cidades.

Uma formiga constrói um circuito da seguinte forma. Na cidade ''i'' a formiga escolhe uma cidade ''j'' que ainda não tenha visitado. Esta escolha é feita probabilisticamente segundo a força da feromona <math>\tau_{ij}(t)</math> no arco entre as cidades ''i'' e ''j'', e a informação heurística disponível localmente, que é função do [[comprimento do arco]]. As formigas, de um modo probabilístico, preferem as cidades que estejam mais próximas e ligadas por arcos com grande força de feromona. Para construir um solução exequível, cada formiga possui uma forma de memória limitada, chamada ''tabu list'' onde é guardada o corrente circuito parcial. A memória é utilizada para determinar, a cada passo da construção, o conjunto de cidades que têm ainda que ser visitadas e para garantir que é elaborada uma solução exequível. Adicionalmente, permite à formiga refazer o seu circuito, assim que esteja completo.

Depois de todas as formigas terem construído um circuito, as feromonas são actualizadas. Isto é tipicamente elaborado através da descida da força dos trilhos das feromonas, através de um factor constante, e depois é dada liberdade para que as formigas depositem as suas feromonas nos arcos que visitaram. A actualização dos trilhos é feita de tal forma que os arcos mais curtos, ou visitados por muitas formigas, recebem quantidades maiores de feromonas e por isso são escolhidas com uma maior probabilidade nas iterações posteriores (Figura 4). Neste sentido, a quantidade de feromonas <big><math>\tau_{ij}(t)</math></big> representa o desejo instruído de escolher a próxima cidade ''j'' quando a formiga estiver na cidade ''i''.

[[Ficheiro:Aco TSP.svg|thumb|center|450px|Figura 4. Efeito do algoritmo ACO para a constituição do circuito preferencial.]]

Os algoritmos ACO que melhor desempenho têm no PCV, melhoram os circuitos construídos pelas formigas através da aplicação de algoritmos de procura local. Estes algoritmos são na verdade algoritmos híbridos que combinam a construção da solução de modo probabilístico com algoritmos de procura local.

No aspecto geral, todos os algoritmos ACO para o PCV seguem o esquema de um algoritmo específico. Depois de iniciados o rasto de feromonas e alguns parâmetros, o circuito principal é repetido até que a condição seja conhecida e rescindida. No circuito principal, primeiro as formigas constroem circuitos exequíveis, depois os circuitos produzidos são melhorados pela aplicação de uma procura local, e finalmente, os rastos de feromonas são actualizados. De facto, a maior parte dos algoritmos ACO que melhor se desenvolvem nos problemas NP-difícil seguem este esquema algorítmico.

Por fim é de salientar que as meta-heurísticas ACO são mais generalizados que o esquema algorítmico dado anteriormente <span id=refbStützle1999>[[#refStützle1999|(Stützle, 1999)]]</span>.

==={{Âncora|Algoritmo por programação dinâmica}} Algoritmo por programação dinâmica ===

Se pensarmos em um abordagem de força bruta, temos que avaliar todas as possíveis jornadas e retornar a melhor encontrada. Essa abordagem utiliza tempo O(n!).

Em [[programação dinâmica]] temos uma solução muito mais rápida, embora não polinomial.

A programação dinâmica reduz o número de possíveis combinações eliminando as que não poderão fazer parte de uma solução ótima do problema, dando assim origem a algoritmos mais eficientes.

A ideia básica é construir por etapas uma resposta ótima combinando respostas já obtidas para partes menores. Assim, é possível escolher subproblemas de modo que a informação vital seja recordada e levada a diante.

Precisamos saber todas as cidades visitadas, para que não repitamos nenhuma delas. Veja um subproblema apropriado:

Para um subconjunto de cidades <math>S \subseteq {1,2,...,n}</math> que inclui <math>1</math> e <math>j \in S</math>, seja <math>C(S,j)</math> o comprimento do caminho mínimo visitando cada nó em <math>S</math> exatamente uma vez, começando em <math>1</math> e terminando em <math>j</math>.

Vamos expressar <math>C(S,j)</math> em termos de subproblemas menores. Precisamos começar em <math>1</math> e terminar em <math>j</math>; qual devemos escolher como a penúltima cidade? Ela tem de ser algum <math>i</math> <math>\in S</math>, tal que o comprimento total seja a distância de <math>1</math> até <math>i</math>, ou seja <math>C(S - \{j\}, i)</math>, mais o comprimento da aresta final, <math>d_{ij}</math>. Temos de selecionar o melhor tal que:

<math>C(S,j) = \min_{i \in S, i \neq j} C(S - \{j\}, i) + dij</math>

[[Pseudocódigo]]:
 
 '''Os problemas são ordenados por |S|:'''
 
    '''C({1},1) = 0''':
    '''Para s = 2 até n''':
            '''Para todos os subconjuntos S <math>\subseteq</math> {1,2,...,n} de tamanho s e contendo 1:'''
                '''C(S,1) = <math>\infty</math>''':
                '''Para todo j <math>\in</math> S, i <math>\neq</math> j:'''
                       '''C(S,j) = min{C(S - {j},i) + d<math>_{ij}</math>: i <math>\in</math> S, i <math>\neq</math> j}
    '''Retornar min<math>_{j}</math> C({1,...,n},j) + d<math>_{ij}</math>'''

== Referências gerais ==
* <div id=refcApplegate2006>APPLEGATE, David L. [et al.] – ''The travelling salesman problem: a computational Study''. Princeton: Princeton University Press, 2006. ISBN 978-0-691-12993-8</div>
* <div id=refBäck1996>[[#refbBäck1996|BäCK]], Thomas – ''Evolutionary algorithms in theory and practice''. New York: Oxford University Press, 1996. ISBN 978-0-195-09971-3</div>
* <div id=refConway2003>[[#refbConway2003|CONWAY]], Richard Walter; MAXWELL, William L.; MILLER, Louis W. – ''Theory of scheduling''. Reading, [Mass]: Edição de Courier Dover Publications, 2003. ISBN 978-0-486-42817-8</div>
* <div id=refCosta2003>[[#refbCosta2003|COSTA]], Fredson Vieira; VIDAL, Fábio Silveira; ANDRÉ, Claudomiro Moura Gomes – ''SLAG – Resolvendo o problema do caixeiro viajante utilizando algoritmos genéticos'' [Em Linha]. Tocantins [Brasil]: Sistemas e Computação - Pós-Graduação, 2003. [Consult. 15 Abr. 2009]. Disponível em WWW: <URL:http://www.de9.ime.eb.br/~fsvidal/trabpub/slag.pdf></div>
* <div id=refcCunha2002>CUNHA, Claudio Barbieri da; BONASSER, Ulisses de Oliveira; ABRAHÃO, Fernando Teixeira Mendes – ''Experimentos computacionais com heurísticas de melhorias para o problema do caixeiro viajante'' [Em Linha]. São Paulo: ANPET, 2002. [Consult. 13 Abr. 2009]. Disponível em WWW: <URL:http://www.ptr.poli.usp.br/ptr/docentes/cbcunha/files/2-opt_TSP_Anpet_2002_CBC.pdf></div>
* <div id=refGuedes2005>[[#refbGuedes2005|GUEDES]], Allison da Costa Neves; LEITE, Jéssica Neiva de Figueiredo; ALOISE, Dário José – ''Um algoritmo genético com infecção viral para o problema do caixeiro viajante'' [Em Linha]. Natal [Brasil]: Revista On Line de Iniciação Científica, 2005. [Consult. 15 Abr. 2009]. Disponível em WWW: <URL:http://www.propesq.ufrn.br/publica/artigos-1edicao/et/MSIC-ET-011.pdf></div>
* <div id=refGoodrich1899>[[#refbGoodrich1899|GOODRICH]], Michael T.; TAMASSIA, Roberto – ''Estruturas de Dados E Algoritmos Em Java ''. 4ª ed.. São Paulo: Edição de Bookman, 1899. ISBN 978-0-471-73884-8</div>
* <div id=refHoffman2000>[[#refbHoffman2000|HOFFMAN]], Karla; [[Manfred Padberg|PADBERG, Manfred]] – ''Traveling salesman problem'' [Em Linha]. Fairfax [Virgínia]: Department of Electrical and Computer Engineering - George Mason University, 2000. [Consult. 13 Abr. 2009]. Disponível em WWW: <URL: http://iris.gmu.edu/~khoffman/papers/trav_salesman.html></div>
* <div id=refNilsson1982>[[#refbNilsson1982|NILSSON]], Nils J. – ''Principals of artificial intelligence''. New York: edição de Birkhauser, 1982. ISBN 978-3-540-11340-9</div>
* <div id=refOchi1998>[[#refbOchi1998|OCHI]], Luiz Satoru – ''Algoritmos genéticos: origem e evolução'' [Em Linha]. São Paulo: Sociedade Brasileira de Matemática Aplicada e Computacional, 1998. [Consult. 18 Abr. 2009]. Disponível em WWW: <URL:http://www.sbmac.org.br/bol/bol-2/artigos/satoru/satoru.html#caixeiro></div>
* <div id=refSiqueira2006>[[#refbSiqueira2006|SIQUEIRA]], Paulo Henrique; STEINER, Maria Teresinha Arns; SCHEER, Sérgio – ''A new approach to solve the traveling salesman problem'' [Em Linha]. Amsterdam: ScienceDirect - Neurocomputing: A new approach to solve the traveling salesman problem, 2006. [Consult. 15 Abr. 2009]. Disponível em WWW: <URL:http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V10-4M7CMDB-1&_user=2975255&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000057395&_version=1&_urlVersion=0&_userid=2975255&md5=c0e8406e94b63d03d280bac5311d805e></div>
* <div id=refStützle1999>[[#refbStützle1999|ST&Uuml;TZLE]], Thomas; DORIGO, Marco – ''ACO Algorithms for the traveling salesman problem'' [Em Linha]. New York: Swarm Intelligence Resources, 1999. [Consult. 17 Abr. 2009]. Disponível em WWW: <URL:http://staff.washington.edu/paymana/swarm/stutzle99-eaecs.pdf></div>

== Bibliografia ==
* CERVIERI, Alexandre; PY, Mónica – ''Algoritmo para a resolução do problema do caixeiro viajante'' [Em Linha]. Porto Alegre: Instituto de Informática - UFRGS, 2000. [Consult. 15 Abr. 2009]. Disponível em WWW: <URL:https://web.archive.org/web/20040926043051/http://www.inf.ufrgs.br/procpar/disc/cmp134/trabs/T2/001/mpisalesman/mpisalesman.pdf>
* REEVES, Colin R., ed. – ''Modern heuristic techniques for combinatorial problems''. Ed. Colin R. Reeves. London: McGraw-Hill Book, 2000. XIII, 320 p..( Advanced Topic in Computer Science). ISBN 978-0-077-09239-9
* LAWLER, Eugène L.; RINNOOY-KAN, A. H. G.; LENSTRA, Jan Karel; SHMOYS, David B. – ''The Traveling salesman problem: a guided tour of combinatorial optimization''. [S.l.]: Edição de Wiley, 1985. ISBN 978-0-471-90413-7

== Ver também ==
* [[Algoritmo simplex]]
* [[Problema de roteamento de veículos]]
* [[Problema da mochila]]
* [[Problema do caminho mínimo]]
* [[Caminho hamiltoniano]]
* [[Sete pontes de Königsberg]]

== Ligações externas ==
* {{Link|en|2=http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ |3=TSPLIB}}
* {{Link|en|2=http://www.tsp.gatech.edu/ |3=TSP}}
* {{Link|en|2=http://www.maths.tcd.ie/pub/HistMath/People/Hamilton/ |3=Vida e obras de Hamilton}}

{{DEFAULTSORT:Problema Caixeiro Viajante}}
[[Categoria:Algoritmos de grafos]]
[[Categoria:Pesquisa operacional]]
[[Categoria:Problemas matemáticos]]
[[Categoria:Otimização]]