Olá galerinha esperta!
Disponibilizo o material de apoio que elaborei (Powerpoint) referente ao Capítulo 2 do PLT - Transporte Rodoviário de Passageiros. Clique aqui para acessar.
Não posso deixar de lembrar também da 2ª etapa da ATPS (Passos 2, 3 e 4), que ficou para ser entregue no dia 05 de outubro. Não esqueçam de perguntar sobre a frota, as linhas existentes (de transporte intermunicipal, interestadual ou internacional!) e o número de motoristas. Precisamos saber como eles estudam a demanda e a oferta, como determinam as linhas, número e horários e como fazem a alocação de veículos e motoristas. Além disso sugiro ainda que perguntem se eles medem a qualidade e a produtividade. Releiam os indicadores do Capítulo 1 e tentem adaptar às perguntas que serão feitas.
Será um trabalho PRÁTICO bem completo, não acham?
A tarefa dessa semana é pesquisar sobre as 2 técnicas mais conhecidas de roteamento (ou roteirização) de veículos: o Problema do Caixeiro Viajante e o Problema do Carteiro Chinês. Não espero que vocês entendam sozinhos e nem descrevam as fórmulas matemáticas, o que quero que vocês postem é o objetivo de cada uma dessas técnicas. Uma dica: além da internet, pesquisem também e PRINCIPALMENTE em livros de pesquisa operacional, temos várias obras na biblioteca! Não esqueçam de mencionar a(s) fonte(s) pesquisada(s). Se tiverem dúvidas me procurem, ok?
Figura 1 - Ilustração de um Caixeiro Viajante
Figura 2 - Ilustração de um Carteiro Chinês
Um abraço a todos e boa semana!
Caixeiro Viajante:
ResponderExcluirO objetivo do caixeiro viajante é partir de sua cidade, visitar uma cidade de cada vez voltar para casa pela menor distancia possivel, ele precisa achar uma rota que passe por todas as cidades e que tenha um custo minimo.
Carteiro Chinês: Objetivo dele é determinar um circuito de menor custo dentro de um ''arco''.
*O problema do caixeiro viajante é um dos problemas mais estudados em otimização combinatória. O problema consiste na determinação da rota de menor custo para um vendedor que deseja visitar um conjunto finito de cidades. Para tanto, ele deverá iniciar a viagem em uma cidade qualquer, passar por todas as demais cidades exatamente uma vez, e então retornar para a cidade onde a rota teve início.
ResponderExcluir*O Problema do carteiro chinês consiste na resolução de minimizar a distância total que o carteiro percorre, como deverá ser a sua rota de forma que ele passe por todas as ruas ao menos uma vez .
Xi...esqueci de mencionar, mas é preciso colocar a fonte da pesquisa!!
ResponderExcluirAndreia e Alfredo, se puderem complementar suas postagens, agradeço.
Abraços a todos!
Caixeiro viajante: consiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.
ResponderExcluirFonte http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante
Carteiro chinês: consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado.
Fonte
http://pt.wikipedia.org/wiki/Problema_do_carteiro_chin%C3%AAs
Caixeiro Viajante: consiste no problema de determinar o circuito mais curto que é possível efetuar entre as cidades constantes de uma determinada lista, de modo a que cada cidade seja visitada uma e uma só vez.
ResponderExcluirhttp://to-campos.planetaclix.pt/neural/hop.html
Carteiro Chinês: determinar um circuito de custo mínimo, também chamado de rota, em um grafo com ou sem restrições, tal que todos os arcos sejam atravessados apenas uma vez.
http://www.sbmac.org.br/eventos/cnmac/cd_xxviii_cnmac/resumos%20estendidos/frederico_paes_ST18.pdf
Problema do caixeiro viajante:
ResponderExcluirProblema que consiste na determinacao da rota de menor custo para uma pesoa que parta de uma cidade e deva visitar outras,passando ao nenos uma vez em cada cidade e retornando ao ponto de partida.
Problema do carteiro chines:
Ele deve percorrer um roteiro todo dia,oproblema e identificar esse roteiro de maneira a minimizar a distancia total percorrida.
fonte:www.munif.com.br/munif/arquivos/E1-GrafoEuler_Hamilton.pdf?id...
Paulo Nestor
PROBLEMA DO CAIXEIRO VIAJANTE - O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial. problema de optimização que, apesar de parecer modesto é, na realidade, muito investigado por cientistas, matemáticos e investigadores de diversas áreas, tais como: logística, genética e produção, entre outros. O problema pertence à categoria NP-Completo que o remete para um campo de complexidade exponencial, isto é, o esforço computacional necessário para a sua resolução cresce exponencialmente com o tamanho do problema. Assim, dado que é difícil, se não impossível, determinar a solução óptima desta classe de problemas, os métodos de resolução passam pelas heurísticas e afins que, do ponto de vista matemático, não asseguram a obtenção de uma solução óptima.
ResponderExcluirFONTE: http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante
PROBLEMA DO CARTEIRO CHINÊS - consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução. Se um grafo tem um circuito Euleriano (ou um caminho euleriano), então um circuito Euleriano (ou caminho) visita cada aresta, e assim a solução é escolher qualquer circuito euleriano (ou caminho). Se o grafo não é Euleriano, deve conter vértices de grau ímpar. Pelo lema do aperto de mãos, deve haver um número par desses vértices. Para resolver o problema do carteiro chinês primeiro encontramos a menor junção-T. Nós fazemos o grafo virar Euleriano pela duplicação da junção-T. A solução para o problema do carteiro chinês no grafo original é obtida por encontrar um circuito Euleriano para o novo grafo.
FONTE:http://pt.wikipedia.org/wiki/Problema_da_inspe%C3%A7%C3%A3o_de_rotas
Att: RICARDO
-O problema do caixeiro viajante é um problema de otimização, investigado por cientistas, matemáticos e investigadores de diversas áreas, como: logística, genética e produção, entre outros, que procuram um caminho que possua a menor distância, começando em uma cidade qualquer,entre outras, visitando uma cidade de cada vez até seu destino final, com um menor tempo e custo.
ResponderExcluir-O Problema do carteiro chinês consiste em encontrar uma rota em que ele passe todo dia em uma só vez e com uma distância menor.
http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante
Elizandra.
Este comentário foi removido pelo autor.
ResponderExcluirO caixeiro viajante:
ResponderExcluirO objetivo é encontrar a rota de menor distância que inicie em um dado nó de um grafo, visite todos os membros de um conjunto específico de nós do grafo uma única vez e retorne ao nó inicial.
Fonte: http://arxiv.org/ftp/cs/papers/0505/0505031.pdf
O carteiro chinês
O objetivo é determinar um circuito de custo mínimo, também chamado de rota, em um grafo com ou sem restrições, tal que todos os arcos sejam atravessados apenas uma vez.
Fonte: http://www.sbmac.org.br/eventos/cnmac/cd_xxviii_cnmac/resumos%20estendidos/frederico_paes_ST18.pdf
Li em várias fontes, inclusive algumas acima, e concluí que:
ResponderExcluirTanto o caixeiro viajante como o chinês tem como objetivo passar por todos os pontos objetivando o melhor caminho possível.
A diferença é que o caixeiro viajante tenta fazer o melhor caminho passando uma única vez por cada ponto(Ex: um ônibus intermunicipal ou interestadual). Já o caixeiro chinês tenta o melhor caminho não importando se passará por um ponto em mais de uma vez(Ex: Algumas linhas de ônibus urbanos).
Sandro Mehler
Fontes Diversas
Caixeiro Viajante: é uma profissão antiga, de uma pessoa que vende produtos fora daonde eles são produzidos. Antigamente, quando não havia a facilidade do transporte entre cidades, os caixeiros-viajantes eram a única forma de transportar produtos entre diferentes regiões fora das grandes cidades.É um problema de optimização que, apesar de parecer modesto é, na realidade, muito investigado por cientistas, matemáticos e investigadores de diversas áreas, tais como: logística, genética e produção, entre outros.
ResponderExcluirpt.wikipedia.org/wikiProblema_do_caixeiro_viajante
Caixeiro chinês: Problema do carteiro chinês (PCC), circuito do carteiro ou problema da inspeção de rotas consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução.
pt.wikipedia.org/wiki/Problema_da_inspeção_de_rotas
Formulando o problema do caixeiro:
ResponderExcluirSuponha que um caixeiro viajante tenha de visitar n cidades diferentes, iniciando e encerrando sua viagem na primeira cidade. Suponha, também, que não importa a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra.
O problema do caixeiro viajante consiste em descobrir a rota que torna mínima a viagem total
http://www.mat.ufrgs.br/~portosil/caixeiro.html
A poucas variantes do Problema do Carteiro Chinês têm sido estudadas e mostraram-se NP-completas[3].
(Minimização) Problema do carteiro chinês para grafos mistos: para este problema, algumas das arestas podem ser direcionadas e só podem ser visitadas a partir de uma direção. Quando o problema é transversal mínimo de um digrafo é conhecido como o "problema da varredor de New York Street".
(Minimização) Problema do carteiro k-Chinês: encontrar todos os ciclos de k elementos a partir de um local designado de tal forma que cada aresta seja atravessada por pelo menos um ciclo. O objetivo é minimizar o custo do ciclo mais caro.
Problema do carteiro rural: é dado também um subconjunto das arestas. Encontre o mais barato ciclo hamiltoniano contendo cada uma dessas arestas (e possivelmente outras). Este é um caso especial do problema geral de roteamento mínimo que especifica com precisão quais vértices o ciclo deve conte
http://pt.wikipedia.org/wiki/Problema_da_inspe%C3%A7%C3%A3o_de_rotas
O problema do caixeiro-viajante (PCV), é um problema de otimização que, apesar de parecer modesto é, na realidade, muito investigado por cientistas, matemáticos e investigadores de diversas áreas, tais como: logística, genética e produção, entre outros.
ResponderExcluirhttp://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante
o Problema do carteiro chinês (PCC), circuito do carteiro ou problema da inspeção de rotas consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução.
http://pt.wikipedia.org/wiki/Problema_do_carteiro_chin%C3%AAs
By: Ederson weber
Um caixeiro viajante terá que visitar um numero cidades diferentes, iniciando e encerrando sua viagem na primeira cidade, não importando a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra.
ResponderExcluirO problema do caixeiro viajante consiste em descobrir a rota que torna mínima e mais curta a distancia da viagem total.
Referencia:http://www.mat.ufrgs.br/~portosil/caixeiro.html
O carteiro Chinês deve percorrer um roteiro todos os dias, identificando a melhor maneira de minimizar a distancia total percorrida.
ResponderExcluirhttp://www.munif.com.br/munif/arquivos/E1-GrafoEuler_Hamilton.pdf?id=53
Caixeiro viajante:
ResponderExcluiro objetivo é encontrar um roteiro que possua a menor distância , começando em qualquer cidade, entre várias, pasando por todas cidade uma vez e voltando à cidade inicial na menor distancia posivel.
Fonte http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante
Carteiro Chinês:
O objetivo é encontrar um roteiro de custo mínimo, também chamado de rota, pasando em todas as cidades, tal que todas as cidades sejam atendidas apenas uma vez.E votando a cidade inicial no menor custo possivel
Fonte: http://www.sbmac.org.br/eventos/cnmac/cd_xxviii_cnmac/resumos%
wilson urban
O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.
ResponderExcluirFonte: http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante
O problema do carteiro chinês consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução.
Fonte: http://pt.wikipedia.org/wiki/Problema_da_inspe%C3%A7%C3%A3o_de_rotas
Ass.: Reginaldo de Abreu Lima
o caixeiro viajante precisa passar por todas as cidades sem repetir o caminho que ja passou em um espaço de tempo menor possivel obtendo a maior lucratividade voltando ao seu ponto de partida.
ResponderExcluirja o carteiro precisa de uma rota onde possa passar uma unica vez fazendo suas entregas, assim aconomizará tempo e seu trabalho terá maior eficiencia.
CLAUDEMIR
Caixeiro Viajante: O problema do caixeiro-viajante consiste na procura de um circuito que possua a menor distância, começando em qualquer cidade, entre várias, visitando cada cidade uma vez e regressando à cidade inicial. Consiste em descobrir a rota que torna mínima a viagem total.
ResponderExcluirFonte:www.Wikipédia.org e www.mat.ufrgs.br
Carteiro Chinês: Deve percorrer um roteiro todo dia. O problema é de identificar esse roteiro de maneira a minimizar a distância total percorrida.
Fonte:www.professeurs.polymtl.ca
Att, Claudinéia
Problema do Caixeiro Viajante: Consiste em determinar o circuito mais curto que é possível efetuar entre as cidades constantes de uma determinada lista, de modo que cada cidade seja visitada uma só vez.
ResponderExcluirTrata-se de um problema de optimização «NP-completo», o que significa que, para um problema de dimensão razoável, há tantas hipóteses a considerar que não é normalmente prático procurar uma solução óptima, porque isso se torna demasiado custoso computacionalmente. Considera-se, por isso, um bom resultado a obtenção de uma "boa" solução num tempo computacional curto.
Uma rede neuronal permite determinar rapidamente soluções que, quando são válidas, estão todas entre as 30 ou 40 melhores entre as centenas de milhar de hipóteses possíveis. Se escolhermos entre elas a que corresponde à menor distância total de menor custo, obteremos rapidamente uma solução que, se não é a melhor, estará muito «perto» de o ser.
http://to-campos.planetaclix.pt/neural/hop.html.
Problema do Carteiro Chinês: Consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução.
http://pt.wikipedia.org/wiki/Problema_da_inspe%C3%A7%C3%A3o_de_rotas
O Caixeiro Viajante e o Carteiro Chinês os dois tem o objetivo de otimizar o processo tendo como objetivo de passar por todos os pontos procurando o melhor caminho. A diferença é que o Caixeiro Viajante procura estabelecer o melhor caminho passando uma única vez em cada ponto, já o Carteiro Chinês procura o melhor caminho não se importando em passar pelo mesmo ponto mais de uma vez.
ResponderExcluirRODRIGO GAIO 4FASE
O problema do caixeiro é um clássico exemplo de problema de otimização combinatória. A primeira coisa que podemos pensar para resolver esse tipo de problema é reduzí-lo a um problema de enumeração: achamos todas as rotas possíveis e, usando um computador, calculamos o comprimento de cada uma delas e então vemos qual a menor. ( É claro que se acharmos todas as rotas estaremos contando-as, daí podermos dizer que estamos reduzindo o problema de otimização a um de enumeração ).
ResponderExcluirFonte: www.mat.ufrgs.br/~portosil/caixeiro.html
Problema do carteiro chinês (PCC), circuito do carteiro ou problema da inspeção de rotas consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução.
Fonte: pt.wikipedia.org/wiki/Problema_da_inspeção_de_rotas
Douglas Peter Gielow
Caixeiro Viajante objetivo: dado um conjunto de n cidades, um vendedor deve partir de uma
ResponderExcluircidade inicial, visitar todas as demais cidades uma única vez e
regressar posteriormente à cidade de origem, de tal forma que a
distância percorrida seja mínima.
http://www2.dcc.ufmg.br/laboratorios/lapo/ensino/combinatoria/Caixeiro.pdf
Problema do carteiro chinês (PCC) Em teoria dos grafos, um ramo da matemática, o Problema do carteiro chinês (PCC), circuito do carteiro ou problema da inspeção de rotas consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo(conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução.
http://pt.wikipedia.org/wiki/Problema_da_inspe%C3%A7%C3%A3o_de_rotas
Diego Streck
Caixeiro-viajante:
ResponderExcluirConsiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.
Fonte: http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante
O carteiro chinês
O objetivo é determinar um circuito de custo mínimo, também chamado de rota, em um grafo com ou sem restrições, tal que todos os arcos sejam atravessados apenas uma vez.
Fonte: http://www.sbmac.org.br/eventos/cnmac/cd_xxviii_cnmac/resumos%20estendidos/frederico_paes_ST18.pdf
Maicon Rodrigo Fogulari
Este comentário foi removido por um administrador do blog.
ResponderExcluirDILSON LOPES:
ResponderExcluirO problema do caixeiro-viajante
Suponha que um caixeiro viajante tenha de visitar n cidades diferentes, iniciando e encerrando sua viagem na primeira cidade. Suponha, também, que não importa a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra.
O problema do caixeiro viajante consiste em descobrir a rota que torna mínima a viagem total.
Exemplificando o caso n = 4:
se tivermos quatro cidades A, B, C e D, uma rota que o caixeiro deve considerar poderia ser: saia de A e daí vá para B, dessa vá para C, e daí vá para D e então volte a A. Quais são as outras possibilidades ? É muito fácil ver que existem seis rotas possívei.
http://www.mat.ufrgs.br/~portosil/caixeiro.html
Problema do Carteiro Chinês: Consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução.
http://pt.wikipedia.org/wiki/Problema_da_inspe%C3%A7%C3%A3o_de_rotas
O problema carteiro chinês é um matemático problema da teoria dos grafos . É também conhecido como problema de verificação da rota. Suponha que haja um carteiro que precisa para entregar e-mail para um determinado bairro. Que carteiro é preguiçoso, por isso ele quer encontrar a menor rota pelo bairro, que atenda aos seguintes critérios:
É um circuito fechado (termina no mesmo ponto que começa).
Ele precisa passar por todas as ruas pelo menos uma vez.
Se o gráfico viajou possui um circuito euleriano , este circuito é a solução ideal.
Alan Goldman do National Bureau of Standards EUA primeiro cunhou 'Problema do Carteiro Chinês "o nome para este problema, como era originalmente estudada pelo matemático chinês Mei-Ku Kuan em 1962. [1]
O problema do caixeiro é um clássico exemplo de problema de otimização combinatória. A primeira coisa que podemos pensar para resolver esse tipo de problema é reduzí-lo a um problema de enumeração: achamos todas as rotas possíveis e, usando um computador, calculamos o comprimento de cada uma delas e então vemos qual a menor. ( É claro que se acharmos todas as rotas estaremos contando-as, daí podermos dizer que estamos reduzindo o problema de otimização a um de enumeração ).
ResponderExcluirhttp://www.mat.ufrgs.br/~portosil/caixeiro.html
Um chinês da pesada tenta entregar cartas eletrizantes passando por todas as ruas com uma distância mínima!
Um carteiro pega cartas no correio, entrega-as, e posteriormente retorna ao correio. Ele deve, claramente, cobrir todas as ruas de sua área pelo menos uma vez. Sujeito à tal condição, ele deseja escolher sua rota de tal forma que caminhe o mínimo possível.
http://code.google.com/p/carteirochines/
O problema do caixeiro é um exemplo de problema de otimização conbinatoria,talvez uma solução para esse problema é reduzi-lo a um problema de enumeração,analizando todas as rotas possíveis,então calculamos o comprimento de cada uma delas,assim veremos qual a menor...
ResponderExcluirhttp://www.mat.ufrgs.br/portosil/caixeiro.html
O problema do carteiro chinês consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução.
Fonte: http://pt.wikipedia.org/wiki/Problema_da_inspe%C3%A7%C3%A3o_de_rotas
Jéssica pommerening
Vamos ver, vocês comentaram que não estão conseguindo postar... Por esse motivo deixei que os comentários a essa semana semana sejam realizados até sexta, dia 30/09, ok? Mas não esqueçam de verificar também a semana sete!
ResponderExcluirAbraços a todos!
O Problema do Caixeiro Viajante
ResponderExcluirSão dadas cidades e as distâncias entre elas. O caixeiro viajante tem que visitar todas elas, mas não quer viajar demais. A tarefa consiste em encontrar a sequência de cidades que faz com que a distância percorrida seja a menor possível. Em outras palavras, o problema é achar a rota mínima.
http://www.obitko.com/tutorials/genetic-algorithms/portuguese/tsp-example.php
Problema do carteiro Chines - consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado.
pt.wikipedia.org/wiki/Problema_da_inspeção_de_rotas
Pamela Patricia
O grande desafio do caixeiro viajante e do carteiro chinês é encontrar a menor distancia entre varias cidades e retornar ao ponto de origem, comparando este desafio no transporte de hoje é encontrar esse ponto de ligação fazer esta ligação com o Maximo de agilidade e sempre utilizando o Maximo da capacidade do transporte com lotação máxima diminuindo assim fazer rotas desnecessárias e com pouca carga que iriam aumentar os gastos. Hoje o transporte representa o maior custo na logística por este motivo quanto mais eficiente maior será as vantagens. Para diminuir estes custos e necessário rotas bem planejadas visando sempre ida e a volta.
ResponderExcluirFabio Rodrigo.
O problema será solucionado através de um estudo encima das rotas utilizadas por ambos do ponto de partida ao ponto de chegada passando por várias cidades utilizando a menor distância e o menor tempo possível para realizar suas entregas aumentando sua eficiência e eficácia.
ResponderExcluirBruno Costa
FERNANDO MENDES 4ª FASE;TEC. LOGISTICA
ResponderExcluirCAIXEIRO VIAJANTE- Procura fazer um cicuito curto com uma distantancia pequena , porem alcançar varias cidades, facilitando a volta ao ponto inicial Ex:Pentagôno
CARTEIRO CHINÊS - Consiste em encontrar uma ROTA mais curta , porem que visite cada aresta de um grafo, de tal maneira que todos os arcos sejam atravessados de uma só vez.
http://pt.wikipedia.org/wiki/problema do carteiro chines
http://pt;wikipedia.org/wiki/problema caixeiroviajante
Caixeiro viajante: consiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.
ResponderExcluirFonte http://pt.wikipedia.org/wiki/Problema_do_caixeiro_viajante
Carteiro chinês: consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado.
Fonte
http://pt.wikipedia.org/wiki/Problema_do_carteiro_chin%C3%AAs
Ferdinando Busarello
O Problema do Caixeiro Viajante
ResponderExcluirO Problema do Caixeiro Viajante consiste no problema de determinar o circuito mais curto que é possível efectuar entre as cidades constantes de uma determinada lista, de modo a que cada cidade seja visitada uma e uma só vez.
http://to-campos.planetaclix.pt/neural/hop.html
carteiro chinês
consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução
http://pt.wikipedia.org/wiki/Problema_do_carteiro_chin%C3%AAs
Andreas
Olá
ResponderExcluirIsso é um teste
Assis
Olá
ResponderExcluirIsso é um teste
Assis
problema do carteiro chines consiste em encontrar um caminho mais curto ou circuito fechado que visite cada aresta de um grafo (conectado) não-direcionado. Quando o grafo possui um circuito Euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma ótima solução.
ResponderExcluirCaixeiro-viajante é uma profissão antiga, de uma pessoa que vende produtos fora daonde eles são produzidos. Antigamente, quando não havia a facilidade do transporte entre cidades, os caixeiros-viajantes eram a única forma de transportar produtos entre diferentes regiões fora das grandes cidades.
fontes:
http://pt.wikipedia.org/wiki/Problema_da_inspe%C3%A7%C3%A3o_de_rotas
http://pt.wikipedia.org/wiki/Caixeiro-viajante
O problema do caixeiro viajante é muito famoso e muito estudado.
ResponderExcluirCaixeiro viajante, partindo de sua cidade, deve visitar exatamente uma única
vez cada cidade de uma dada lista e retornar para casa tal que a distância total
percorrida seja a menor possível.
O problema do entregador viajante é uma modificação do problema do caixeiro
viajante, em que o objetivo é minimizar o tempo médio de atendimento a n cidades
ou clientes. Como pode-se notar por este enunciado, este problema se aplica nas
situações em que, não se quer minimizar é o custo de quem visita, de quem
oferece o serviço–situação do caixeiro viajante.
Raquel Kraemer
carteiro chinês consiste em encontra um caminho mais curto ou circuito fechado que visite cada aresta de um grafo não-derecionado.
ResponderExcluirhttp://pt.wikipedia.org/wiki/problema-do-carteiro-chir%c3%AAs
Caixeiro viajante
objetivo encontrou um roteiro que possua a menor distancia, entre várias,passando por todas cidade uma vez e voltando á cidade inicial na menor distâcia possível.
http://pt.wikipedia.org/wiki/problema-do-caixeiro-viajante
esquecei de colocar meu nome
ResponderExcluirno comentário
Maria José