caixeiro viajante

Páginas: 4 (816 palavras) Publicado: 27 de setembro de 2015


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 wereused. 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 umasoluçã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 paraproblemas 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 eretornando 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çõesdos 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étodosutilizados.

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, osistema 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 gulosostomam 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...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Caixeiro viajante
  • Caixeiro viajante
  • Caixeiro Viajante
  • Caixeiro Viajante
  • O Caixeiro Viajante
  • o Caixeiro Viajante
  • caixeiro viajante
  • caixeiro viajante

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!