Escolhendo um Paradigma: Um Guia de Decisão

• Enunciar a diferença estrutural definidora entre dividir para conquistar, guloso, e programação dinâmica em termos de como cada um trata subproblemas.
• Reconhecer os sinais reveladores, no enunciado de um novo problema, que apontam para cada um dos três paradigmas.
• Explicar por que guloso exige uma prova de correção que dividir para conquistar e DP não precisam da mesma forma, e por que DP é o recurso quando essa prova falha ou não existe.
• Trabalhar através de enunciados de problema desconhecidos e justificar, com referência a propriedades estruturais em vez de semelhança superficial, qual paradigma cada um exige.
• Nomear, para cada paradigma, pelo menos um algoritmo canônico já coberto nesta disciplina que o ancora concretamente.

Esta disciplina agora construiu três formas genuinamente diferentes de transformar um problema em um algoritmo: dividir para conquistar, que divide um problema em peças independentes e combina suas respostas; guloso, que se compromete com uma escolha localmente melhor de cada vez e nunca olha para trás; e programação dinâmica, que resolve subproblemas sobrepostos uma vez cada um e reutiliza suas respostas. Cada paradigma foi introduzido com seu próprio exemplo canônico, merge sort para dividir para conquistar, seleção de atividades para guloso, Fibonacci e depois uma sequência de problemas práticos (LCS, Mochila 0/1, LIS) para programação dinâmica, e cada um ganhou seu lugar com uma prova ou demonstração real de quando se aplica e quando não: a recorrência do merge sort resolvida exatamente; a escolha gulosa de seleção de atividades validada por um argumento de troca completo; a estratégia gulosa por razão da Mochila 0/1 mostrada, concretamente, falhar.

O que este conceito de encerramento adiciona não é uma nova técnica, mas a habilidade que de fato importa uma vez que todos os três estão à mão: dado um enunciado de problema totalmente novo, sem nenhum paradigma nomeado antecipadamente, reconhecer qual exige, e, igualmente importante, reconhecer quando a resposta não é óbvia e uma prova ou um contraexemplo é necessário antes de confiar em uma abordagem específica. Essa é a habilidade mais transferível única em um curso sobre paradigmas algorítmicos, porque problemas reais nunca chegam rotulados "use programação dinâmica aqui." Chegam como uma descrição de entradas e um objetivo, e os sinais estruturais reveladores, o problema se divide em peças que nunca compartilham trabalho? uma escolha localmente melhor comprovadamente nunca precisa ser revisitada? uma solução recursiva ingênua refaz trabalho idêntico através de muitos caminhos de chamada diferentes? são o que este conceito treina diretamente.

A distinção estrutural, precisamente

Dividir para conquistar divide um problema em subproblemas menores que são resolvidos independentemente, nenhuma solução de subproblema é necessária por outro subproblema no mesmo estágio, e nenhum dois subproblemas jamais acabam sendo idênticos. As duas metades do merge sort não compartilham dados e nunca são recombinadas até o passo de merge final; a árvore de recursão não tem nenhum nó repetido em lugar nenhum. O passo de combinar (mesclar duas metades ordenadas) é onde toda a verdadeira esperteza tipicamente reside.

Guloso constrói uma solução incrementalmente, fazendo uma escolha em cada passo que parece melhor agora mesmo, e, criticamente, nunca reconsiderando essa escolha depois. Isso é rápido e simples sempre que é correto, mas sua correção nunca é algo a assumir: exige uma prova real (tipicamente um argumento de troca, como a regra de tempo-de-término-mais-cedo de seleção de atividades recebeu) mostrando que a escolha localmente melhor é sempre parte de alguma solução globalmente ótima. Sem essa prova, guloso é apenas um palpite que acontece de rodar rápido.

Programação dinâmica se aplica quando um problema tem subproblemas sobrepostos, uma solução recursiva ingênua resolveria o mesmo problema menor idêntico muitas vezes através de ramos diferentes de sua recursão, combinado com subestrutura ótima, de forma que resolver cada subproblema distinto uma vez (via memoização ou tabulação) e combinar essas respostas produz o ótimo global correto. DP é usado especificamente na situação onde guloso falha: quando nenhuma escolha localmente melhor pode ser provada segura para se comprometer irrevogavelmente, mas tentar toda combinação via recursão de força bruta seria lenta demais, a tabela (ou cache) de DP é o que torna explorar todas as combinações relevantes tratável.

Tabela comparativa

Sinais reveladores, como uma lista de verificação diagnóstica

• O problema naturalmente se divide em peças que não compartilham informação ou trabalho? → provavelmente dividir para conquistar. Pergunte: se eu resolvesse cada metade completamente independentemente, combinar as duas respostas daria a resposta completa correta, sem nada perdido? Merge sort: sim. Árvore geradora mínima, considerada peça por peça: geralmente não, as peças interagem através de vértices/arestas compartilhados, que é por que algoritmos de MST usam estratégias gulosas sobre subgrafos em vez disso.
• Posso articular, e depois de fato provar, que se comprometer com uma escolha "obviamente melhor agora mesmo" nunca fecha o caminho para uma solução geral melhor? → guloso, mas só uma vez que essa prova exista. A regra de término mais cedo de seleção de atividades sobreviveu a esse teste com um argumento de troca real. Se a prova não se junta, ou pior, um pequeno contraexemplo surge em vez disso, como aconteceu para o guloso por razão da Mochila 0/1, guloso é a ferramenta errada, seja qual for seu apelo superficial.
• Uma solução recursiva ingênua continua recalculando o exato mesmo subproblema menor, alcançado via sequências diferentes de decisões? → programação dinâmica. Essa é a verificação de subproblemas sobrepostos de anteriormente nesta disciplina, e é uma propriedade mecânica, verificável: rastreie alguns níveis da recursão ingênua e procure argumentos repetidos para a mesma função.

Exemplo 1: "Dados n trabalhos cada um com um prazo e um lucro, e só um trabalho pode rodar por slot de tempo, agende trabalhos para maximizar lucro total, desistindo de qualquer trabalho que perca seu prazo completamente."

Isso se assemelha a seleção de atividades à primeira vista (agendamento sob restrições), mas olhe mais de perto: diferente de seleção de atividades, trabalhos aqui não têm horários de início/término que se sobrepõem em uma linha simples, a restrição é puramente "um trabalho por slot, deve terminar até seu prazo." Uma estratégia gulosa (ordene por lucro decrescente, atribua cada trabalho ao slot disponível mais tardio antes de seu prazo) de fato acaba tendo uma prova genuína de correção por argumento de troca para esta variante específica, então este é um problema guloso, mas a semelhança com seleção de atividades é só superficial; a justificativa real tem que ser trabalhada para a própria estrutura de restrição deste problema, não emprestada integralmente da prova de seleção de atividades. A lição mais ampla: reconhecer "isso parece um problema de agendamento, então provavelmente é guloso" é uma hipótese razoável, mas o sinal revelador que de fato confirma é a existência (ou construção) de uma prova real, não a semelhança superficial sozinha.

Exemplo 2: "Dado um conjunto de itens com pesos e valores e uma capacidade de mochila, escolha um subconjunto (cada item totalmente incluído ou excluído) maximizando valor sem exceder a capacidade."

Isso é Mochila 0/1, já coberto por completo. O sinal revelador apontando para longe de guloso e em direção a DP é exatamente o contraexemplo que esta disciplina construiu concretamente: itens (w=10,v=60), (w=20,v=100), (w=30,v=120) a capacidade 50, onde a escolha gulosa melhor-razão-primeiro (A, depois B) alcança valor 160, enquanto o verdadeiro ótimo (B + C) alcança 220. Porque uma escolha localmente melhor (pegar A primeiro) pode ser mostrada ativamente bloquear uma solução global melhor, nenhuma prova por argumento de troca para guloso pode existir aqui, isso não é "guloso pode funcionar, não provado", é "guloso está refutado, concretamente." Uma solução recursiva ingênua para este problema também visivelmente sobrepõe subproblemas (o mesmo par "primeiros i itens, capacidade restante c" recorre através de muitas decisões de inclusão de item), confirmando que DP é a ferramenta certa, com sua tabela calculando o verdadeiro 220 diretamente.

Exemplo 3: "Dado um grafo ponderado, conexo, não direcionado, encontre um subconjunto de arestas conectando todos os vértices com peso total de aresta mínimo" e "Dado um array, ordene-o usando o menor número de comparações no pior caso, garantido."

Dois exemplos de ancoragem em um, deliberadamente escolhidos para contrastar: o problema de árvore geradora mínima é resolvido, nesta disciplina, por ambos os algoritmos de Kruskal e Prim, ambos genuinamente gulosos (sempre adicione a aresta segura mais barata; sempre estenda a árvore via a aresta mais barata saindo dela), e ambos corretos especificamente porque a "propriedade de corte" dá exatamente o tipo de prova estrutural que guloso precisa, aplicada à estrutura específica deste problema, uma prova diferente da de seleção de atividades, mas uma prova ainda assim, que é o sinal revelador real, não uma coincidência de que "problemas de grafo tendem a ser gulosos." Merge sort, em contraste, é uma resposta de dividir para conquistar para a pergunta de ordenação: divida o array pela metade, ordene cada metade completamente independentemente (nenhum trabalho compartilhado, nenhuma sobreposição entre as recursões das duas metades), e combine via um merge linear, a independência das duas metades, com nada calculado duas vezes, é exatamente o que marca isso como dividir para conquistar em vez de DP, mesmo que ordenação pudesse em princípio ser abordada de muitas outras formas.

• "Se um problema envolve escolher um subconjunto para otimizar algo, é sempre um problema de DP estilo mochila." Seleção de atividades também escolhe um subconjunto (quais atividades manter) para otimizar algo (contagem de atividades sem sobreposição), e é comprovadamente um problema guloso, não um de DP, o fator decisivo é se uma prova da segurança da escolha localmente melhor existe (existe, via o argumento de troca), não o formato superficial "escolher um subconjunto."
• "Guloso e DP são intercambiáveis, se guloso parece dar uma boa resposta em alguns casos de teste, provavelmente está bem." O contraexemplo da Mochila 0/1 mostra que guloso pode parecer completamente razoável e ainda assim estar comprovadamente, concretamente errado, alguns casos de teste passando não provam nada; só uma prova real (para guloso) ou um par demonstrado de subproblemas-sobrepostos-mais-subestrutura-ótima (para DP) fornece uma garantia real.
• "Dividir para conquistar e DP são a mesma coisa, já que ambos usam recursão e dividem problemas em peças menores." A pergunta distintiva é se os subproblemas de fato se sobrepõem. As metades recursivas do merge sort nunca se repetem; os subproblemas de Fibonacci, LCS, e Mochila se repetem, que é exatamente por que os últimos se beneficiam de um cache ou tabela e o primeiro não.
• "Uma vez que você escolheu um paradigma para um problema que se assemelha a um conhecido, a prova do conhecido se transfere automaticamente." O Exemplo 1 mostra que isso é arriscado, semelhança superficial com seleção de atividades não entrega sua prova de argumento de troca de graça; uma estrutura de restrição genuinamente diferente precisa de sua própria justificativa, mesmo quando o mesmo paradigma acaba se aplicando.

Dividir para conquistar, guloso, e programação dinâmica se distinguem por uma pergunta estrutural acima de tudo: como os subproblemas do problema se relacionam entre si? Subproblemas independentes, não sobrepostos, combinados por um passo de combinar correto apontam para dividir para conquistar (merge sort, o exemplo de ancoragem). Uma única escolha localmente melhor, feita uma vez por passo e nunca revisitada, aponta para guloso, mas só uma vez que uma prova real (um argumento de troca, como com seleção de atividades, ou a propriedade de corte, como com os algoritmos de MST de Kruskal e Prim) confirma que aquela escolha é sempre segura; na ausência de tal prova, ou diante de um contraexemplo real como a falha do guloso por razão da Mochila 0/1 (valor 160 versus o verdadeiro ótimo de 220), guloso não é um recurso que valha a pena confiar. Subproblemas sobrepostos, a mesma instância menor recorrendo através de muitos caminhos de decisão diferentes em uma solução recursiva ingênua, combinados com subestrutura ótima apontam para programação dinâmica, a ferramenta usada especificamente quando recursão de força bruta é correta mas lenta demais, e o atalho de guloso não é seguro. Reconhecer qual desses três sinais um problema novo, desconhecido, exibe, em vez de combiná-lo por padrão contra um problema superficialmente similar já resolvido, é a habilidade transferível para a qual esta disciplina inteira tem construído.