Considere o grafo euclidiano completo com os pontos (1,1),(1,3),(2,2),(3,3),(4,2). 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 (1,1),(1,3),(2,2),(3,3),(4,2). 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):
A=(1,1),\quad B=(1,3),\quad C=(2,2),\quad D=(3,3),\quad E=(4,2).
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 (x_1,y_1) e (x_2,y_2):
\text{dist}=\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}.
Aplicando a fórmula aos pares relevantes (calculei todos, mostrando apenas os que usaremos depois):
\begin{aligned} \text{dist}(A,B)&=\sqrt{(1-1)^2+(3-1)^2}=\sqrt{0+4}=2,\\\ \text{dist}(A,C)&=\sqrt{(2-1)^2+(2-1)^2}=\sqrt{1+1}=\sqrt{2},\\\ \text{dist}(A,D)&=\sqrt{(3-1)^2+(3-1)^2}=\sqrt{4+4}=2\sqrt{2},\\\ \text{dist}(A,E)&=\sqrt{(4-1)^2+(2-1)^2}=\sqrt{9+1}=\sqrt{10},\\\ \text{dist}(B,C)&=\sqrt{(2-1)^2+(2-3)^2}=\sqrt{1+1}=\sqrt{2},\\\ \text{dist}(B,D)&=\sqrt{(3-1)^2+(3-3)^2}=\sqrt{4+0}=2,\\\ \text{dist}(B,E)&=\sqrt{(4-1)^2+(2-3)^2}=\sqrt{9+1}=\sqrt{10},\\\ \text{dist}(C,D)&=\sqrt{(3-2)^2+(3-2)^2}=\sqrt{1+1}=\sqrt{2},\\\ \text{dist}(C,E)&=\sqrt{(4-2)^2+(2-2)^2}=\sqrt{4+0}=2,\\\ \text{dist}(D,E)&=\sqrt{(4-3)^2+(2-3)^2}=\sqrt{1+1}=\sqrt{2}. \end{aligned}
Resumo das distâncias úteis (valores exatos): \sqrt{2} aparece entre (A,C),(B,C),(C,D),(D,E); segmentos de comprimento 2 ocorrem em (A,B),(B,D),(C,E); e \sqrt{10} é (A,E) e (B,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 \sqrt{2} (quatro arestas): (A,C),(B,C),(C,D),(D,E); depois arestas de comprimento 2: (A,B),(B,D),(C,E); depois 2\sqrt{2} e \sqrt{10} etc.
Aplicando Kruskal passo a passo:
  • Adiciono (A,C) de peso \sqrt{2}.
  • Adiciono (B,C) de peso \sqrt{2} (não forma ciclo).
  • Adiciono (C,D) de peso \sqrt{2} (não forma ciclo).
  • Adiciono (D,E) de peso \sqrt{2} (agora todos os vértices A,B,C,D,E estão conectados).
Portanto a MST escolhe exatamente as quatro arestas de comprimento \sqrt{2}:
\text{MST}=\{(A,C),(B,C),(C,D),(D,E)\}.
Peso total da MST:
\text{peso(MST)}=4\sqrt{2}.
Numérico: 4\sqrt{2}\approx 4\cdot1,41421356\approx 5,656854.

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 ≤ 2 vezes o da MST (graças à desigualdade triangular).
  • Vou escolher como vértice inicial A=(1,1) (o primeiro listado no enunciado), ou seja, raiz da pré‑ordem.
Fazendo a pré‑ordem na MST com raiz A:
  • A árvore tem arestas A-C, C-B, C-D, D-E (notei que escrevo C-B como mesma aresta B-C).
  • Pré‑ordem (visitando cada vértice na primeira vez que aparece) a partir de A: A \to C \to B \to D \to E.
  • Fechamos o ciclo voltando a A: A\to C\to B\to D\to E\to A.
Agora calculamos o comprimento desse ciclo somando as distâncias já obtidas:
\begin{aligned} L_{\text{MST-alg}}&=\text{dist}(A,C)+\text{dist}(C,B)+\text{dist}(B,D)+\text{dist}(D,E)+\text{dist}(E,A)\\\ &=\sqrt{2}+\sqrt{2}+2+\sqrt{2}+\sqrt{10}\\\ &=3\sqrt{2}+2+\sqrt{10}. \end{aligned}
Aproximação numérica:
L_{\text{MST-alg}}\approx 3\cdot1,41421356 + 2 + 3,16227766 \approx 9,404918.
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 (A,B,C,D,E). (Isso é uma escolha razoável e necessária porque o problema não especificou desempate.)
Escolhendo como início A=(1,1) (mesma escolha que antes), passo a passo:
  • Em A: distâncias aos não visitados são \text{dist}(A,C)=\sqrt{2}, \text{dist}(A,B)=2, \text{dist}(A,D)=2\sqrt{2}, \text{dist}(A,E)=\sqrt{10}. O mínimo é \sqrt{2} para C. Vou para C.
  • Em C: não visitados \{B,D,E\}. Distâncias: \text{dist}(C,B)=\sqrt{2}, \text{dist}(C,D)=\sqrt{2}, \text{dist}(C,E)=2. Há empate entre B e D (ambos \sqrt{2}). Pelo critério de desempate escolho o que vem primeiro na ordem do enunciado: B. Vou para B.
  • Em B: não visitados \{D,E\}. Distâncias: \text{dist}(B,D)=2, \text{dist}(B,E)=\sqrt{10}. Escolho D.
  • Em D: o único não visitado é E; vou para E.
  • Finalmente volto de E para A.
A sequência obtida é exatamente:
A\to C\to B\to D\to E\to A.
Somando distâncias (mesmo cálculo do passo anterior):
L_{\text{NN}}\;=\;\sqrt{2}+\sqrt{2}+2+\sqrt{2}+\sqrt{10}=3\sqrt{2}+2+\sqrt{10}\approx 9,404918.
Observação: se no empate em C eu tivesse escolhido D em vez de B, o algoritmo produziria a rota A\to C\to D\to E\to B\to A, cujo comprimento também é numericamente igual a 3\sqrt{2}+2+\sqrt{10}. Então, com qualquer desempate natural, o custo final aqui é o mesmo.

Resposta

Algoritmo baseado na árvore geradora: A\to C\to B\to D\to E\to A com custo 3\sqrt{2}+2+\sqrt{10}\approx 9,404918.
Algoritmo do vizinho mais próximo (iniciado em A, desempate conforme ordem dada): A\to C\to B\to D\to E\to A com custo 3\sqrt{2}+2+\sqrt{10}\approx 9,404918.

Exercícios relacionados