Considere o grafo euclidiano completo com os pontos
. Qual é a resposta produzida para este grafo pelo algoritmo baseado na árvore geradora e pelo algoritmo do vizinho mais próximo?
Passo 1
O enunciado dá um grafo euclidiano completo cujos vértices são os pontos
. As perguntas são:
- Que solução o algoritmo baseado na árvore geradora (MST + circulação/preorder + atalho) produz para este grafo?
- Que solução o algoritmo do vizinho mais próximo (nearest neighbor) produz para este grafo?
Informações relevantes dadas: os cinco pontos (vou rotulá‑los para facilitar):
O grafo é completo e as distâncias são as distâncias euclidianas entre os pontos. A resolução começa a partir daqui.
Passo 2
Primeiro precisamos das distâncias entre todos os pares. Vou lembrar a fórmula da distância euclidiana entre dois pontos
e
:
Aplicando a fórmula aos pares relevantes (calculei todos, mostrando apenas os que usaremos depois):
Resumo das distâncias úteis (valores exatos):
aparece entre
; segmentos de comprimento
ocorrem em
; e
é
e
. Vou usar esses valores exatos para somas, e no final darei aproximações numéricas quando necessário.
Passo 3
Construção da árvore geradora mínima (MST) — explicando o método (Kruskal) de forma didática:
- Kruskal ordena todas as arestas por peso crescente e vai adicionando-as desde a menor, evitando ciclos, até conectar todos os vértices.
- Isso garante uma árvore de peso mínimo.
Ordenando arestas por comprimento (menores primeiro): todas as arestas com
(quatro arestas):
; depois arestas de comprimento
:
; depois
e
etc.
Aplicando Kruskal passo a passo:
- Adiciono
de peso . - Adiciono
de peso (não forma ciclo). - Adiciono
de peso (não forma ciclo). - Adiciono
de peso (agora todos os vértices estão conectados).
Portanto a MST escolhe exatamente as quatro arestas de comprimento
:
Peso total da MST:
Numérico:
.
Passo 4
Transformando a MST numa solução aproximada para TSP (algoritmo baseado na árvore geradora) — explicação do método:
- Uma forma clássica é fazer a “circulação do dobrou” (double tree) seguida de uma travessia em pré‑ordem (DFS) da árvore e, ao obter a sequência dos primeiros encontros dos vértices, “atalhar” pulando vértices já visitados para obter um ciclo Hamiltoniano. Isso produz um ciclo com custo ≤
vezes o da MST (graças à desigualdade triangular). - Vou escolher como vértice inicial
(o primeiro listado no enunciado), ou seja, raiz da pré‑ordem.
Fazendo a pré‑ordem na MST com raiz
:
- A árvore tem arestas
(notei que escrevo como mesma aresta ). - Pré‑ordem (visitando cada vértice na primeira vez que aparece) a partir de
: . - Fechamos o ciclo voltando a
: .
Agora calculamos o comprimento desse ciclo somando as distâncias já obtidas:
Aproximação numérica:
Observação didática: o atalho (pular visitas repetidas) não aumenta o custo porque usamos distâncias euclidianas que obedecem à desigualdade triangular; aqui, na verdade, a pré‑ordem já gerou uma sequência com arestas que existiam no grafo completo e a soma deu o valor acima.
Passo 5
Execução do algoritmo do vizinho mais próximo (nearest neighbor) — explicação do método:
- O algoritmo começa em um vértice inicial, sempre escolhe a aresta de menor comprimento para um vértice ainda não visitado, repete até visitar todos e volta ao início.
- O algoritmo depende do vértice inicial e, em caso de empate (duas arestas igualmente curtas), precisamos um critério de desempate. Vou adotar o critério natural: escolher entre os empates o vértice que aparece primeiro na ordem dada no enunciado
. (Isso é uma escolha razoável e necessária porque o problema não especificou desempate.)
Escolhendo como início
(mesma escolha que antes), passo a passo:
- Em
: distâncias aos não visitados são , , , . O mínimo é para . Vou para . - Em
: não visitados . Distâncias: , , . Há empate entre e (ambos ). Pelo critério de desempate escolho o que vem primeiro na ordem do enunciado: . Vou para . - Em
: não visitados . Distâncias: , . Escolho . - Em
: o único não visitado é ; vou para . - Finalmente volto de
para .
A sequência obtida é exatamente:
Somando distâncias (mesmo cálculo do passo anterior):
Observação: se no empate em
eu tivesse escolhido
em vez de
, o algoritmo produziria a rota
, cujo comprimento também é numericamente igual a
. Então, com qualquer desempate natural, o custo final aqui é o mesmo.
Resposta
Algoritmo baseado na árvore geradora:
com custo
.
Algoritmo do vizinho mais próximo (iniciado em
, desempate conforme ordem dada):
com custo
.