Algoritmo Christofides (manualmente)
On Fevereiro 1, 2021 by adminEstou seguindo este exemplo de algoritmo: https://en.wikipedia.org/wiki/Christofides_algorithm#example
The graph:
[! [insira a descrição da imagem aqui] [1]] [1]
Calculate minimum spanning tree T:
[! [Insira a descrição da imagem aqui] [2]] [2]
Calculate the set of vertices O with odd degree in T
O mesmo que “o árvore geradora mínima T “porque o grau de todos os vértices é ímpar.
Form the subgraph of G using only the vertices of O
(como todos eram ímpares, isso deve nos dar o gráfico original) [! insira a descrição da imagem aqui] [1]] [1]
Construct a minimum-weight perfect matching M in this subgraph
( Não tenho certeza se eu fez isso direito ) [! [insira a descrição da imagem aqui] [3]] [3]
Unite matching and spanning tree T ∪ M to form an Eulerian multigraph
[! [insira a descrição da imagem aqui] [4]] [4]
Isso definitivamente não está certo.
O que deu errado?
Comentários
- Observação: todas as imagens da postagem parecem ter desaparecido. O autor tem os originais?
Resposta
Na verdade, você acertou o tempo todo . No entanto, você ainda não concluiu o algoritmo de Christofides.
A próxima etapa é “Calcular passeio de Euler”.
Na a última imagem , você obteve um multigrafo cujos vértices têm graus pares. Portanto, deve haver um caminho Euleriano. Por exemplo, vamos selecionar o caminho Euleriano A -> F -> A -> C -> B -> D -> E -> D -> A.
A última etapa é “Remover vértices repetidos , fornecendo a “saída” do algoritmo.
Removendo o segundo A e o segundo D nesse caminho acima, obtemos uma saída desejada, A -> F -> C -> B -> D -> E -> A . Pronto.
Observe que não é muito significativo aplicar o algoritmo de Christofides no gráfico fornecido.
“O algoritmo de Christofides é um algoritmo para encontrar soluções aproximadas para o problema do caixeiro viajante , em casos em que as distâncias formam um espaço métrico (são simétricas e obedecem à desigualdade do triângulo “. As distâncias fornecidas não obedecem à desigualdade do triângulo, uma vez que d (B, D) + d (D, E) = 1 + 4 < 6 = d (B , E). Além disso, a distância (direta) entre A e B não é fornecida, levantando dúvidas se este é um problema de caixeiro viajante.
Comentários
- Eu sou novo nisso, então, obrigado pelas notas laterais! Eu tenho algumas perguntas: 1. Cada vértice precisa estar conectado a outro vértice para ser um TSP válido? Quero dizer, ainda é possível criar uma rota " TSP " mesmo com a falta dessa rota, então eu diria que é válido – mas Eu estive errado antes. 2. Você acha (ou sabe) se é possível aumentar os pesos de alguns dos vértices do meu gráfico de forma que ele obedeça a desigualdade do triângulo ? Acho que gráficos com aparência mais confusa são melhores para representar cenários de mapas do mundo real, ' é por isso que os criei como são.
- 1. Você pode tratá-lo como um TSP se assumir, por exemplo, todas as distâncias diretas ausentes entre as cidades são grandes o suficiente ou simplesmente infinitas. Dessa forma, essas distâncias ausentes não afetarão a solução. No entanto, ainda não é um espaço métrico. 2. Para obedecer à desigualdade do triângulo, você pode apenas adicionar 10 a cada distância especificada e deixar que todas as distâncias ausentes sejam 20.
- Isso não é verdade: " Na última imagem , você obteve um multigrafo cujos vértices têm graus pares. " – Os vértices E, D, A e F têm um grau ímpar.
- " Você obteve um multigraph ", um gráfico que pode ter várias arestas, ou seja, arestas que têm o mesmo nós finais. Existem duas arestas entre D e E. Existem duas arestas entre A e F.
- Você também pode verificar o exemplo na Wikipedia . " Esse não é um caminho Euleriano, já que você visita um vértice mais de uma vez nesse caminho ". O caminho Euleriano consiste em visitar cada borda exatamente uma vez. Você está falando sobre caminho hamiltoniano.
Deixe uma resposta