Retrocesso e ramificação

Com valores $[2,3,6,8]$ e alvo 10, incluir 2, 3 e 6 soma 11 e já ultrapassa o alvo. Como os valores restantes são positivos, nenhuma continuação desse ramo pode corrigir o excesso. O retrocesso, ou backtracking, constrói escolhas parciais, rejeita os ramos impossíveis e desfaz uma decisão antes de explorar a seguinte.

Em otimização, a ramificação e poda, ou branch and bound, compara um limite otimista para o ramo com a melhor solução completa conhecida, o incumbente. Uma poda só é segura quando nenhuma continuação do ramo pode melhorar o incumbente.

O estado e o regresso

Um estado deve conter as decisões já tomadas e a informação necessária para avaliar extensões. Num subconjunto, são o índice seguinte, a soma atual e as escolhas. Numa colocação de rainhas, são as colunas já preenchidas e as linhas e diagonais ocupadas.

procura(estado):
    se o estado é uma solução completa:
        registar solução
        regressar
    para cada decisão possível:
        se a decisão é admissível:
            aplicar decisão
            procura(estado alterado)
            desfazer decisão

Desfazer é parte da correção, porque uma marca de ocupação esquecida elimina escolhas válidas num ramo seguinte. Devolver imediatamente depois da primeira solução serve para encontrar uma; contar ou listar todas exige continuar a procura.

Distingue o estado do ramo de informação global já provada. Para encontrar uma saída num labirinto fixo, sem consumir recursos, uma DFS pode marcar cada casa permanentemente, pois as saídas dessa casa não dependem do caminho usado para chegar lá; numa grelha $n\times n$, visita até $n^2$ casas e quatro vizinhos por casa, com tempo e memória $O(n^2)$.

Para enumerar todos os caminhos simples, as casas ocupadas pertencem ao caminho atual e têm de ser desmarcadas ao regressar, pois já pode haver exponencialmente muitos caminhos. A operação de desfazer depende do significado do estado.

Soma de subconjuntos com duas podas

Assume valores estritamente positivos e alvo $T\ge0$. No estado $(i,s)$, já decidimos os elementos anteriores a $i$ e somamos $s$. Seja $R_i$ a soma de todos os valores ainda disponíveis.

• Se $s>T$, nenhuma adição positiva consegue corrigir o excesso.
• Se $s+R_i<T$, nem incluir todos os restantes chega ao alvo.

As duas são podas por impossibilidade. Precomputar somas de sufixos permite testar $R_i$ em $O(1)$.

Com valores $[2,3,6,8]$ e $T=10$, depois de incluir 2 e 3 temos $s=5$. Incluir 6 dá 11 e é rejeitado; excluí-lo deixa apenas 8, que também ultrapassa 10 se for incluído. A solução passa por excluir 3 e 6 e incluir 8, dando $2+8=10$.

A árvore mostra o ramo depois de escolher 2 e 3. Em cada nó, $i$ é o índice seguinte, $s$ a soma escolhida e $R_i$ a soma ainda disponível. Os sufixos são $[19,17,14,8,0]$.

Excluir 6 ainda passa ambos os testes, porque $5\le10$ e $5+8\ge10$. Os limites dizem apenas que o ramo não está excluído, não que existe solução nele. As duas folhas mostram que a única quantidade restante, 8, não permite chegar exatamente a 10. Temos de retroceder à escolha anterior de 3; o ramo que o exclui consegue completar $2+8$.

Se os valores estiverem ordenados e $s<T$ mas $s+a_i>T$, nenhum elemento restante cabe. Como ainda falta valor positivo, o ramo inteiro é impossível. Esta terceira poda precisa da ordenação e da positividade. Com valores negativos, nem a poda por excesso é segura.

#include <iostream>
#include <vector>

bool procura(int i, long long soma, long long alvo,
             const std::vector<int> &a, const std::vector<long long> &resto,
             std::vector<int> &escolhidos) {
    if (soma == alvo) return true;
    if (i == static_cast<int>(a.size()) || soma > alvo || soma + resto[i] < alvo)
        return false;
    escolhidos.push_back(a[i]);
    if (procura(i + 1, soma + a[i], alvo, a, resto, escolhidos)) return true;
    escolhidos.pop_back();
    return procura(i + 1, soma, alvo, a, resto, escolhidos);
}

int main() {
    int n;
    long long alvo;
    if (!(std::cin >> n >> alvo) || n < 0 || n > 30 || alvo < 0 || alvo > 30000000) {
        std::cout << "entrada invalida\n";
        return 0;
    }
    std::vector<int> a(n);
    for (int &x : a) {
        if (!(std::cin >> x) || x < 1 || x > 1000000) {
            std::cout << "entrada invalida\n";
            return 0;
        }
    }
    std::vector<long long> resto(n + 1);
    for (int i = n - 1; i >= 0; --i) resto[i] = resto[i + 1] + a[i];
    std::vector<int> escolhidos;
    if (!procura(0, 0, alvo, a, resto, escolhidos)) {
        std::cout << "sem solucao\n";
        return 0;
    }
    std::cout << "subconjunto";
    for (int x : escolhidos) std::cout << ' ' << x;
    std::cout << '\n';
}

O programa devolve subconjunto 2 8. Lê até 30 valores positivos, cada um até um milhão; o alvo está entre 0 e 30 milhões. Para alvo zero, o conjunto vazio é válido. Se não encontra solução, escreve sem solucao.

No pior caso, as podas podem não eliminar quase nada e continuam a existir $O(2^n)$ nós. A memória auxiliar é $O(n)$ para escolhas, sufixos e pilha. Uma boa poda melhora instâncias concretas, mas não prova custo polinomial.

Rainhas e restrições locais

Coloca uma rainha por coluna num tabuleiro $n\times n$. Ao escolher linha $r$ na coluna $c$, rejeita-a se já houver uma rainha na mesma linha ou numa diagonal. Duas posições $(r_1,c_1)$ e $(r_2,c_2)$ partilham diagonal quando

Também podemos marcar diagonais pelos identificadores $r-c$ e $r+c$, ajustando o primeiro para índices não negativos. Essas marcas dão teste de admissibilidade constante.

A colocação $[2,4,1,3]$ é válida. As linhas são distintas, os valores $r-c$ são $1,2,-2,-1$ e os valores $r+c$ são $3,6,4,7$, também distintos. Isto verifica todas as restrições, sem depender de olhar para o desenho.

Escolher só linhas ainda livres dá no máximo $n!$ permutações completas antes das podas diagonais. Testar cada escolha contra todas as anteriores acrescenta trabalho por nó; não anuncies um limite apenas a contar folhas sem explicar essa implementação. Com conjuntos de marcas, o espaço é $O(n)$.

Coloração e alocação de registos

Para colorir um grafo com $k$ cores, escolhe um vértice ainda sem cor e experimenta cada cor diferente das dos seus vizinhos já coloridos. Se nenhuma servir, retrocede. A validade de uma coloração completa é local a cada aresta, mas encontrar uma com poucas cores é um problema global.

A escolha de vértices de maior grau ou com mais cores vizinhas já usadas pode reduzir a procura. Continua a ser uma regra de ordenação da exploração, não uma prova de que o primeiro resultado usa o mínimo de cores.

Contar atribuições de cores

Num grafo com $n$ vértices e $k$ cores rotuladas, há $k^n$ atribuições completas antes de testar as arestas: cada vértice tem $k$ escolhas, mesmo que vários partilhem cor. Não são $k!$ permutações. As cores não são objetos que tenham de aparecer exatamente uma vez.

Enumerar cada atribuição e verificar os $n$ rótulos e as $m$ arestas dá $O(k^n(n+m))$ tempo. Em retrocesso, podemos rejeitar uma igualdade de cores assim que ambos os extremos estejam atribuídos, evitando parte dessa enumeração. O pior caso continua exponencial.

Para procurar o número cromático, testa $k=1,2,\ldots,n$ e para no primeiro valor que admite coloração. Para um grafo simples sem laços, $n$ cores chegam sempre. A enumeração completa de todos esses valores fica limitada por $O(n^{n+1}(n+m))$, um limite superior suficiente para mostrar o crescimento. A prova do mínimo exige ter excluído os valores anteriores; uma primeira coloração de quatro cores, por si só, não prova que três sejam impossíveis.

Uma clique oferece um certificado útil no sentido oposto: se encontrarmos quatro vértices ligados dois a dois, qualquer coloração precisa de quatro cores. Uma coloração de quatro cores e essa clique certificam juntas $\chi(G)=4$.

Vivacidade antes e depois de uma instrução

Um valor está vivo num ponto se pode ser usado numa continuação antes de ser substituído por uma nova definição. Não basta contar as variáveis escritas numa instrução. Para uma instrução $u$, use[u] contém os valores lidos e def[u] os escritos; succ(u) contém as instruções que podem executar a seguir.

Uma análise de vivacidade usa

out guarda os valores necessários depois da instrução. in acrescenta os usados agora e retira os valores que a instrução redefine. Em x = x + 1, use e def contêm ambos x: ler o valor antigo e escrever o novo são operações distintas.

Itera a partir de conjuntos vazios até não haver alterações. Os conjuntos só crescem num domínio finito, por isso termina. Com ciclos no fluxo de controlo, uma só passagem para trás pode não chegar.

Considera esta sequência, sem outros usos depois de ret:

1: a = 1
2: b = 2
3: c = a + b
4: ret c

$a$ e $b$ coexistem antes da instrução 3 e precisam de registos distintos. Depois de ler esses operandos, os seus valores deixam de ser necessários; o registo de $a$ pode receber $c$. Neste modelo, que permite reutilizar um registo de operando para o resultado, duas cores chegam. Uma restrição específica da máquina teria de ser acrescentada ao modelo.

De intervalos a webs e interferências

Uma web reúne intervalos de vivacidade da mesma variável que se sobrepõem, incluindo sobreposições transitivas. Duas vidas separadas da variável podem formar webs distintas e receber registos diferentes. Os vértices do grafo de interferências representam essas webs; uma aresta significa que os dois valores precisam de coexistir.

Por exemplo, intervalos de x que cobrem os pontos $\{1,2,3\}$ e $\{3,4,5\}$ fundem-se numa web $\{1,2,3,4,5\}$. Um terceiro intervalo $\{8,9\}$ fica separado se não houver outro que os ligue. As listas representam pontos do fluxo de controlo: não substituas uma lista pelos números entre o seu mínimo e máximo, pois podes inventar pontos que ela não contém.

O instante dentro da instrução também conta. Uma web que termina por leitura e outra que começa pela escrita do resultado na mesma instrução podem não interferir, como $a$ e $c$ no exemplo. A marca de fim não deve ser tratada como se o valor anterior ainda precisasse de sobreviver depois da escrita.

A coloração atribui uma cor, ou registo, a cada web, com cores diferentes nos extremos de cada aresta. Para $k$ registos, remove um vértice com grau atual menor que $k$ e empilha-o. Depois de colorir o restante, recoloca-o: tem menos de $k$ vizinhos já coloridos, logo existe uma cor livre. É o grau no grafo restante que conta.

Quando não há tal vértice, a simplificação não prova impossibilidade, porque um ciclo de quatro vértices tem todos os graus iguais a 2 e, mesmo assim, admite duas cores. Podes tentar outra procura ou transferir uma web para memória, o spill. Dividir uma web, ou splitting, pode reduzir interferências, mas exige preservar o valor nas transições entre as partes; retirar arestas arbitrariamente alteraria o programa.

O segundo projeto de 2025/26 fornece os intervalos de vivacidade como entrada. A análise in/out explica a sua origem, mas não acrescenta ao enunciado uma obrigação de construir um compilador ou calcular esses intervalos. O trabalho algorítmico inclui juntar intervalos em webs, construir interferências e comparar coloração, spilling e splitting. Os formatos e limites das variantes pertencem ao enunciado dessa edição.

Branch and bound: direção do limite

Para maximizar, o incumbente é um limite inferior $L$, pois já sabemos obter esse valor. Cada nó tem um limite superior $U$ sobre todas as suas continuações. Se $U\le L$, podemos podar quando basta devolver um ótimo. Para minimizar, o incumbente é um limite superior e cada nó precisa de um limite inferior; poda-se quando o limite inferior já é pelo menos o incumbente.

O limite deve ser otimista. Para a mochila 0-1, permitir frações alarga as soluções admissíveis e dá um limite superior válido para maximização. Usar o valor de outro guloso 0-1 como limite superior é perigoso, porque esse valor pode ficar abaixo de uma solução do ramo.

Com capacidade 10 e objetos $A=(6,12)$, $B=(5,9)$, $C=(5,9)$, conhecemos o incumbente $B+C$, valor 18. No ramo que inclui $A$, sobram 4 unidades. A relaxação fracionária permite $4/5$ de $B$, dando limite 19,2. Não podemos podar esse ramo por esse limite, mesmo que a solução inteira real fique em 12. Um limite pode ser seguro e pouco apertado.

TSP com um limite inferior

Numa procura de circuitos, o estado guarda o último vértice, os ainda não visitados e o custo percorrido. Rejeita arestas inexistentes e, na folha, inclui o custo de regressar à origem. O custo de um caminho aberto não é o custo do circuito.

Num TSP dirigido com pesos não negativos, um limite inferior simples soma ao custo atual a menor saída permitida de cada vértice que ainda precisa de sair: o último atual e os não visitados. Pode permitir destinos repetidos ou ciclos prematuros na conta do limite, porque isso relaxa as restrições. Toda a continuação válida tem essas saídas, pelo que não pode custar menos que a soma dos mínimos.

Se já conhecemos um circuito de custo 20 e um ramo tem custo parcial 8 mais saídas mínimas de soma 15, o limite inferior é 23 e o ramo pode ser podado. Se não houver saída possível para algum vértice que precisa dela, o ramo é inviável. Pesos negativos tornam inválida a poda que usa apenas o custo parcial; precisamos de contabilizar o possível custo negativo futuro.

DFS usa pouca memória e pode encontrar cedo um incumbente. Explorar primeiro o melhor limite pode cortar mais ramos, mas exige uma fila de nós. Nenhuma ordem substitui a prova da poda. Para enumerar todos os ótimos, não cortes os nós cujo limite apenas empata com o incumbente.