caixeiro viajante

Trabalho Prático 02
Projeto de Algoritmos

Abstract. The objective of this work is to develop a solution to the traveling salesman problem. Two techniques known to Backtracking and Greedy were used. These techniques are known as heuristics, ie, seeking viable solutions to more complicated problems, even if they are imperfect answers.

Resumo. O objetivo deste trabalho é desenvolver uma solução para o problema do caixeiro viajante. Foram utilizadas duas técnicas conhecidas como Backtracking e Guloso. Essas técnicas são conhecidas como heurísticas, ou seja, procuram soluções viáveis para problemas mais complicados, mesmo que sejam imperfeitas as respostas.

1. Descrição do problema
O problema do caixeiro viajante consiste em verificar o menor caminho passando por todas as cidades e retornando ao ponto de partida. Cada cidade poderá ser visitada somente uma vez. Existem algumas técnicas para resolver esse problema, mas, ainda não foi descoberta uma solução ótima.

2. Definições dos métodos Os algoritmos utilizados para executar as operações foram implementados na linguagem de programação Java, utilizando a IDE NetBeans.
Abaixo, está descrição de cada um dos métodos utilizados.

2.1 Backtracking Segue um padrão de busca em profundidade, ou seja, percorre a arvore de cima para baixo e da esquerda para a direita, quando encontra um ponto terminal em uma das folhas, o sistema volta pelo mesmo caminho percorrido e continua a busca a partir de um caminho alternativo.

2.2 Algoritmo Guloso Geralmente, são utilizados para problemas de otimização. Os algoritmos gulosos tomam decisões com base apenas na informação disponível, sem sepreocupar com os efeitos futuros de tais decisões, isto é, eles nunca reconsideram as decisões tomadas, independentemente das consequências.

3. Diferenças dos métodos utilizados A principal diferença entre os dois algoritmos acontece quando é necessário um retorno. No algoritmo Backtracking, quando o próximo caminho não é melhor, ele