Como provar que o algoritmo guloso está correto

Eu tenho um algoritmo ganancioso que suspeito estar correto, mas não tenho certeza. Como verifico se está correto? Quais são as técnicas a serem usadas para provar que um algoritmo ganancioso está correto? Existem padrões ou técnicas comuns?

^{Espero que isso se torne uma pergunta de referência que possa ser usada para apontar iniciantes; daí seu escopo mais amplo que o usual. Tome cuidado para fornecer respostas gerais, apresentadas didaticamente, ilustradas por pelo menos um exemplo, mas, no entanto, abrangem muitas situações. Obrigado!}

Por fim, você precisará de uma prova matemática de correção. Vou abordar algumas técnicas de prova para isso abaixo, mas primeiro, antes de mergulhar nisso, deixe-me economizar algum tempo: antes de procurar uma prova, tente testes aleatórios.

Teste aleatório

Como primeiro passo, recomendo que você use testes aleatórios para testar seu algoritmo. É incrível como isso é eficaz: na minha experiência, para algoritmos gananciosos, o teste aleatório parece ser irracionalmente eficaz. Gaste 5 minutos codificando seu algoritmo, e você pode economizar uma ou duas horas tentando criar uma prova.

A idéia básica é simples: implemente seu algoritmo. Além disso, implemente um algoritmo de referência que você saiba que está correto (por exemplo, um que tente exaustivamente todas as possibilidades e faça o melhor). Tudo bem se o seu algoritmo de referência for assintoticamente ineficiente, pois você só executará isso em pequenas instâncias de problemas. Em seguida, gere aleatoriamente um milhão de pequenas instâncias de problemas, execute os dois algoritmos em cada uma e verifique se o seu algoritmo candidato fornece a resposta correta em todos os casos.

Empiricamente, se o seu algoritmo ganancioso candidato estiver incorreto, normalmente você o descobrirá durante testes aleatórios. Se parece correto em todos os casos de teste, você deve seguir para o próximo passo: apresentar uma prova matemática de correção.

Provas matemáticas de correção

OK, precisamos provar que nosso algoritmo ganancioso está correto: que ele gera a solução ideal (ou, se houver várias soluções ótimas igualmente boas, que gera uma delas).

O princípio básico é intuitivo:

Princípio: Se você nunca fizer uma má escolha, estará bem.

Algoritmos gananciosos geralmente envolvem uma sequência de opções. A estratégia básica de prova é que tentaremos provar que o algoritmo nunca faz uma má escolha. Os algoritmos gananciosos não podem voltar atrás - uma vez que fazem uma escolha, eles são comprometidos e nunca desfazem essa escolha - por isso é fundamental que eles nunca façam uma má escolha.

O que seria uma boa escolha? Se houver uma única solução ideal, é fácil ver o que é uma boa escolha: qualquer escolha que seja idêntica àquela feita pela solução ideal. Em outras palavras, tentaremos provar que, em qualquer estágio da execução dos algoritmos gananciosos, a sequência de escolhas feitas pelo algoritmo até agora corresponde exatamente a algum prefixo da solução ideal. Se houver várias soluções ótimas igualmente boas, uma boa opção é consistente com pelo menos uma das ótimas. Em outras palavras, se a sequência de opções do algoritmo até agora corresponde ao prefixo de uma das soluções ideais, tudo está bem até agora (nada deu errado ainda).

Para simplificar a vida e eliminar as distrações, vamos nos concentrar no caso em que não há vínculos: existe uma solução ideal única e única. Todo o equipamento será transferido para o caso em que pode haver vários ótimos igualmente bons, sem alterações fundamentais, mas é preciso ter um pouco mais de cuidado com os detalhes técnicos. Comece ignorando esses detalhes e concentrando-se no caso em que a solução ideal é única; isso ajudará você a se concentrar no essencial.

Há um padrão de prova muito comum que usamos. Trabalharemos duro para provar a seguinte propriedade do algoritmo:

Reivindicação: Seja a saída da solução pelo algoritmo e seja a solução ótima. Se é diferente de , então podemos ajustar para obter outra solução que é diferente de e estritamente melhor do que .O S O O O ∗ O $S$$O$$S$$O$$O$$O^*$$O$$O$

Observe por que isso é útil. Se a afirmação for verdadeira, segue-se que o algoritmo está correto. Isso é basicamente uma prova por contradição. Ou é igual a ou é diferente. Se for diferente, podemos encontrar outra solução que seja estritamente melhor que - mas isso é uma contradição, pois definimos como a solução ideal e não pode haver nenhuma solução que seja melhor que isso. Então somos forçados a concluir que não pode ser diferente de ; deve sempre ser igual aS S * S S S S S $S$$O$$O^*$$O$$O$$S$$O$$S$$O$, ou seja, o algoritmo ganancioso sempre gera a solução correta. Se pudermos provar a afirmação acima, provamos que nosso algoritmo está correto.

Bem. Então, como podemos provar a alegação? Pensamos em uma solução como um vetor que corresponde à sequência de escolhas feitas pelo algoritmo e, da mesma forma, pensamos na solução ideal como um vetor correspondente à sequência de escolhas que levaria a . Se é diferente de , deve existir algum índice que ; vamos nos concentrar no menor tal . Então, vamos ajustar alterando um pouco no( S 1 , … , S n$S$$(S_1,\dots,S_n)$O ( O 1 , … , O n ) O S O i S i ≠ O i i O O i S i O i O $n$$O$$(O_1,\dots,O_n)$$O$$S$$O$$i$$S_i \ne O_i$$i$$O$$O$$i$na posição correspondente a , ou seja, ajustaremos a solução ótima alterando a escolha para a escolhida pelo algoritmo guloso, e depois mostraremos que isso leva a uma solução ainda melhor. Em particular, definiremos como algo como$S_i$$O$$i$$O^*$

exceto que muitas vezes teremos que modificar a parte ligeiramente para manter a consistência global. Parte da estratégia de prova envolve alguma inteligência na definição adequada de . Então, a base da prova será, de alguma forma, usar fatos sobre o algoritmo e o problema para mostrar que é estritamente melhor que ; é aí que você precisará de informações específicas sobre problemas. Em algum momento, você precisará mergulhar nos detalhes do seu problema específico. Mas isso dá uma idéia da estrutura de uma prova típica de correção para um algoritmo ganancioso.$O_{i+1},O_{i+2},\dots,O_n$$O^*$$O^*$$O$

Um exemplo simples: subconjunto com soma máxima

Isso pode ser mais fácil de entender, trabalhando com um exemplo simples em detalhes. Vamos considerar o seguinte problema:

Entrada: Um conjunto de números inteiros, um inteiro Saída: Um conjunto de tamanho cuja soma é o maior possível$U$$k$
$S \subseteq U$$k$

Existe um algoritmo ganancioso natural para esse problema:

1. Defina .$S := \emptyset$
2. Para : $i := 1,2,\dots,k$
   • Seja o maior número em que ainda não foi escolhido (ou seja, o ésimo número em ). Adicionar a .$x_i$$U$$i$$U$$x_i$$S$

O teste aleatório sugere que isso sempre fornece a solução ideal, então vamos provar formalmente que esse algoritmo está correto. Observe que a solução ideal é única, portanto não precisaremos nos preocupar com laços. Vamos provar a reivindicação descrita acima:

Reivindicação: Let ser a saída de solução por este algoritmo na entrada , e a solução óptima. Se , então pode-se construir uma outra solução de cuja soma é ainda maior do que .$S$$U,k$$O$$S \ne O$$O^*$$O$

Prova. Suponha , e deixá- ser o índice da primeira iteração onde . (Esse índice devo existir, já que assumimos e, pela definição do algoritmo, temos .) Como (por suposição) é mínimo, deve ter e, em particular, tem o formato , onde os números estão listados em ordem decrescente. Observando como o algoritmo escolhe$S \ne O$$i$$x_i \notin O$$i$$S \ne O$$S=\{x_1,\dots,x_k\}$$i$$x_1,\dots,x_{i-1} \in O$$O$$O=\{x_1,x_2,\dots,x_{i-1},x'_i,x'_{i+1},\dots,x'_n\}$$x_1,\dots,x_{i-1},x'_i,\dots,x'_n$$x_1,\dots,x_i$, vemos que devemos ter para todos os . Em particular, . Portanto, defina , ou seja, obtemos excluindo o ésimo número em e adicionando . Agora, a soma dos elementos de é a soma dos elementos de mais e , então a soma de é estritamente maior que a soma deIsso prova a afirmação. $x_i > x'_j$$j\ge i$$x_i > x'_i$$O^ = O \cup \{x_i\} \setminus \{x'_i\}$$O^*$$i$$O$$x_i$$O^*$$O$$x_i-x'_i$$x_i-x'_i>0$$O^*$$O$$\blacksquare$

A intuição aqui é que, se o algoritmo ganancioso fizer uma escolha inconsistente com , podemos provar que poderia ser ainda melhor se ele fosse modificado para incluir o elemento escolhido pelo algoritmo ganancioso nesse estágio. Como é ótimo, não pode haver maneira de torná-lo ainda melhor (isso seria uma contradição), então a única possibilidade restante é que nossa suposição esteja errada: em outras palavras, o algoritmo ganancioso nunca fará uma escolha que é inconsistente com .$O$$O$$O$$O$

Esse argumento geralmente é chamado de argumento de troca ou lema de troca . Encontramos o primeiro lugar em que a solução ótima difere da solução gananciosa e imaginamos trocar esse elemento de pela opção gananciosa correspondente (trocado por ). Algumas análises mostraram que essa troca só pode melhorar a solução ideal - mas, por definição, a solução ideal não pode ser melhorada. Portanto, a única conclusão é que não deve haver lugar onde a solução ideal seja diferente da solução gananciosa. Se você tiver um problema diferente, procure oportunidades para aplicar esse princípio de troca em sua situação específica.$O$$x'_i$$x_i$

Vou usar o seguinte algoritmo de classificação simples como exemplo:

repeat:
  if there are adjacent items in the wrong order:
     pick one such pair and swap
  else
     break

Para provar a exatidão, utilizo dois passos.

• Primeiro, mostro que o algoritmo sempre termina.
• Então eu mostro que a solução onde termina é a que eu quero.

Para o primeiro ponto, escolho uma função de custo adequada para a qual posso mostrar que o algoritmo a aprimora em cada etapa.

Neste exemplo, escolho o número de inversões na lista de entrada. Uma inversão em uma lista é um par de entradas , tal que mas . O número de inversões é sempre não negativo e uma lista classificada possui 0 inversões.$A$$A[i]$$A[j]$$A[i] > A[j]$$i<j$

A troca clara de dois itens adjacentes , que estão na ordem errada remove a inversão mas não deixa nenhuma outra inversão afetada. Portanto, o número de inversões é reduzido a cada iteração.$A[i]$$A[i+1]$$A[i],A[i+1]$

Isso prova que o algoritmo termina eventualmente.

O número de inversões em uma lista classificada é 0. Se tudo der certo, o algoritmo reduzirá o número de inversões para zero. Só precisamos mostrar que ele não fica preso no mínimo local.

Eu costumo provar isso por contradição. Presumo que o algoritmo parou, mas a solução não está correta. No exemplo, isso significa que a lista ainda não está classificada, mas não há itens adjacentes na ordem errada.

Se a lista não estiver classificada, deve haver pelo menos dois itens que não estão na posição correta. Seja e , , sejam dois desses itens e a diferença entre e é mínima. Como o algoritmo não parou, eles não são adjacentes, então . Porque assumimos a minimaidade, e , mas depois e temos uma contradição.$A[i]$$A[j]$$i<j$$A[i]>A[j]$$i$$j$$i+1 < j$$A[i]<A[i+1]$$A[i+1]<A[j]$$A[i]<A[j]$

Isso prova que o algoritmo para apenas quando a lista é classificada. E, portanto, terminamos.