Comparação de Eficiência entre Backtracking e Branch and Bound no Problema do Caixeiro Viajante

O Problema do Caixeiro Viajante (Traveling Salesman Problem - TSP) é um desafio clássico de otimização combinatória. Este artigo analisa duas abordagens principais para sua resolução: o algoritmo de Retrocesso (Backtracking) e o algoritmo de Limitação e Ramificação (Branch and Bound), avaliando sua eficiência em diferentes escalas de complexidade.

Análise Teórica dos Algoritmos

1. Algoritmo de Retrocesso (Backtracking)

O Backtracking é uma técnica de busca exaustiva que explora o espaço de estados utilizando uma estratégia de busca em profundidade (DFS). Para o TSP, o algoritmo tenta construir um caminho visitando cidades uma a uma. Ele utiliza a técnica de "poda" para descartar caminhos que já superam o custo da melhor solução encontrada até o momento.

Espaço de Estados: Representado por uma árvore de permutação.
Poda: Se o custo parcial atual somado à próxima aresta for maior ou igual ao melhor custo global, o ramo é abandonado.

2. Algoritmo de Branch and Bound

Diferente do Backtracking, o Branch and Bound utiliza busca em largura (BFS) ou busca por prioridade (Best-First Search). Ele se baseia em estimativas de limites inferiores (Lower Bounds) e superiores (Upper Bounds) para decidir qual nó da árvore de busca deve ser expandido.

Limite Superior (UB): Geralmente calculado por uma heurística gulosa para encontrar uma solução inicial aceitável.
Limite Inferior (LB): Uma estimativa do custo mínimo para completar o ciclo a partir do nó atual.
Fila de Prioridade: Armazana os nós vivos, priorizando aqueles com menor limite inferior de custo.

Implementação e Estrutura de Código

Exemplo de Implementação: Backtracking

Abaixo, apresentamos uma estrutura em Java para o algoritmo de retrocesso com poda básica.


public class TspBacktracking {
    private int[][] matrizAdj;
    private int totalCidades;
    private int[] rotaAtual;
    private int[] melhorRota;
    private int custoMinimo = Integer.MAX_VALUE;

    public void resolver(int[][] matriz, int n) {
        this.matrizAdj = matriz;
        this.totalCidades = n;
        this.rotaAtual = new int[n];
        for (int i = 0; i < n; i++) rotaAtual[i] = i;
        this.melhorRota = new int[n];
        
        executarBusca(1, 0);
    }

    private void executarBusca(int nivel, int custoParcial) {
        if (nivel == totalCidades) {
            int custoFinal = custoParcial + matrizAdj[rotaAtual[nivel - 1]][rotaAtual[0]];
            if (custoFinal < custoMinimo) {
                custoMinimo = custoFinal;
                System.arraycopy(rotaAtual, 0, melhorRota, 0, totalCidades);
            }
            return;
        }

        for (int i = nivel; i < totalCidades; i++) {
            int custoAresta = matrizAdj[rotaAtual[nivel - 1]][rotaAtual[i]];
            if (custoAresta != -1 && custoParcial + custoAresta < custoMinimo) {
                trocar(nivel, i);
                executarBusca(nivel + 1, custoParcial + custoAresta);
                trocar(nivel, i); // Backtrack
            }
        }
    }

    private void trocar(int i, int j) {
        int temp = rotaAtual[i];
        rotaAtual[i] = rotaAtual[j];
        rotaAtual[j] = temp;
    }
}

Exemplo de Implementação: Brench and Bound

Esta versão utiliza uma fila de prioridade para expandir os nós com base em uma estimativa de custo mínimo.


import java.util.*;

public class TspBranchAndBound {
    private static class NodoBusca implements Comparable<NodoBusca> {
        int[] caminho;
        int custoAtual;
        int estimativaLB;
        int nivel;

        public NodoBusca(int[] caminho, int custo, int lb, int nivel) {
            this.caminho = caminho.clone();
            this.custoAtual = custo;
            this.estimativaLB = lb;
            this.nivel = nivel;
        }

        @Override
        public int compareTo(NodoBusca outro) {
            return Integer.compare(this.estimativaLB, outro.estimativaLB);
        }
    }

    public int calcularLimiteInferior(int[][] matriz, int[] caminho, int nivel) {
        // Implementação simplificada de LB usando a soma das arestas mínimas
        int lb = 0;
        for (int i = 0; i < matriz.length; i++) {
            int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
            for (int j = 0; j < matriz.length; j++) {
                if (i == j || matriz[i][j] == -1) continue;
                if (matriz[i][j] <= min1) {
                    min2 = min1;
                    min1 = matriz[i][j];
                } else if (matriz[i][j] < min2) {
                    min2 = matriz[i][j];
                }
            }
            lb += (min1 + min2);
        }
        return (int) Math.ceil(lb / 2.0);
    }

    public void buscar(int[][] matriz) {
        int n = matriz.length;
        PriorityQueue<NodoBusca> fila = new PriorityQueue<>();
        int[] inicial = new int[n];
        // Inicialização do nó raiz...
        // Loop de expansão de nós com poda baseada em custo acumulado e LB
    }
}