Retrocesso e ramificação

Estado e regresso

Estado traz decisões tomadas e dados para extensões. Desfazer marcas do ramo atual é obrigatório; esquecer elimina válidas seguintes. Primeira solução serve para existência; todas exigem continuar.

• Labirinto sem consumo: marca permanente chega, pois saídas não dependem do caminho. Até $n^2$ casas em grelha.
• Caminhos simples: casas do caminho atual desmarcam ao regressar; pode haver exponencialmente muitos.

Podas por impossibilidade

Com positivos e alvo $T$, no estado $(i,s)$ com restante $R_i$:

• $s>T$ poda por excesso.
• $s+R_i<T$ poda por insuficiência.

Somas de sufixos dão $R_i$ em $O(1)$. Com negativos, excesso não poda.

Limites para otimização

Para maximizar, o incumbente é um limite inferior $L$ e cada nó tem um teto $U$ para as suas continuações; se $U\le L$, o ramo não pode melhorar e poda. Para minimizar, o incumbente é um teto e poda o nó que não promete melhoria. Para listar todos os ótimos, conserva os empates em vez de podar.

• A relaxação fracionária ou LP dá um teto em maximização e um piso em minimização, porque alarga o conjunto admissível.
• Ramifica a variável fracionária de valor $a$ em dois ramos, $x\le\lfloor a\rfloor$ e $x\ge\lceil a\rceil$.
• Cada corte conserva todos os pontos inteiros e exclui a solução fracionária atual; arredondar a solução fracionária pode sair do poliedro ou piorar o objetivo.

Rainhas, coloração e TSP usam mesma estrutura: viabilidade local, teste completo no fim e limite que nunca exclui melhor possível.

Somas, rainhas e limites.