O problema do caixeiro viajante

O Problema do Caixeiro Viajante (PCV), ou Traveling Salesman Problem (TSP), é um caso típico de otimização combinatória, freqüentemente utilizado em computação para demonstrar problemas de difícil resolução. A sua definição formal é: encontrar um caminho através de um grafo valorado que inicie e termine no mesmo vértice, passe por todos os demais vértices do grafo uma única vez e minimize o custo total. O problema do caixeiro viajante é um problema de otimização associado ao da determinação dos caminhos hamiltonianos em um grafo qualquer. O objetivo do PCV é encontrar, em um grafo G = (N, A), o caminho hamiltoniano de menor custo.

Fiz um programa em Java que implementou o algoritmo Depth-First Search (busca em profundidade) para encontrar a solução ótima do problema do caixeiro viajante. Quem quiser pode fazer o download do programa. O algoritmo implementado é de força-bruta, ou seja, testa todas as possibilidades possíveis. Assim, como a complexidade do programa é da ordem de n!, logo a execução do programa torna-se inviável. Em meus testes, para n=14, o tempo de execução foi de 42,73 minutos. A estimativa de tempo para n=15 é de 15 vezes esse tempo, ou seja, 641 minutos.

Ao executar o programa, deve ser informada a matriz de adjacência do grafo, indicando as distâncias entre os vértices. A figura acima ilustra a execução do problema do caixeiro viajante com n=4. Para n=5, deve-se incluir uma uma nova linha e uma nova coluna em todas as linhas. O resultado apresentará o menor caminho que saia da cidade 0, passe por todas as outras cidades e retorne para 0.

Atualizado em 14/02/2011: O link para download do programa foi corrigido.

Convertendo AFND para AFD

Tive que implementar, para a disciplina de Análise de Algoritmos, um conversor de autômato finito não-determinístico para autômato finito determinístico. Disponibilizo o programa que implementei em java para download. A implementação é bem simples, sem orientação a objetos propriamente dita, apenas uma classe com alguns métodos. O importante é que funcionou. Importante salientar que não foi implementada a conversão de estados vazios.

Ao iniciar o programa, algumas opções já vêm pré-preenchidas, como os estados, o alfabeto, o estado inicial, um estado final e a função de transição de um autômato, ilustrado na figura abaixo. O único campo que precisa ser informado é a seqüência de entrada. Primeiramente deve ser executada a conversão, clicando-se no botão "Converter para AFD". Depois clica-se em "Executar" para verificar se a entrada é aceita ou rejeitada. Por exemplo, para o AFND padrão (pré-preenchido) a entrada 010101 resultará em rejeição e a entrada 0101010 será aceita.

Abraços

Atualizado em 14/02/2011: O link para download do programa foi corrigido.