Como provar que o algoritmo guloso está correto

29

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!

DW
fonte
Podemos provar que um algoritmo ganancioso está correto usando um matroide ou um greedoide?
zdm 19/11

Respostas:

24

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 OSOSOOOOO

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 SSOOOOSOSO, 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(S1,,Sn)O ( O 1 , , O n ) O S O i S iO i i O O i S i O i O nO(O1,,On)OSOiSiOiiOOina 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 comoSiOiO

O=(O1,O2,,Oi1,Si,Oi+1,Oi+2,,On),

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.Oi+1,Oi+2,,OnOOO

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ívelUk
SUk

Existe um algoritmo ganancioso natural para esse problema:

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

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 .SU,kOSOOO

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 escolheSOixiOiSOS={x1,,xk}ix1,,xi1OOO={x1,x2,,xi1,xi,xi+1,,xn}x1,,xi1,xi,,xnx1,,xi, 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. xi>xjjixi>xiO=O{xi}{xi}OiOxiOOxixixixi>0OO

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 .OOOO

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.Oxixi

DW
fonte
Esta é uma pergunta antiga, mas é o primeiro resultado do Google para mim. A linha then we can tweak O to get another solution O∗ that is different from O and strictly better than Ome confunde. Se houver várias soluções ótimas, é possível ter S != Oe ambas ainda são ótimas; podemos emenda O ser "mais como" S (criando O *) e ainda ser tão bom como (não strictly better than) O.
citelao
@ Citelao, lamento ouvir que isso te confundiu. Infelizmente, não sei como explicá-lo mais claramente. Sim, pode haver várias soluções ideais, todas com o mesmo valor. Está correto. O que você escreveu e o que eu escrevi são válidos; não há contradição. A diferença é que o que você escreveu não ajuda a provar que um algoritmo ganancioso está correto; o que eu escrevi faz. Só posso sugerir que repasse o que escrevi novamente e veja se você consegue descobrir como o que escrevi é útil. Se isso não ajudar, talvez encontre um artigo diferente. Eu percebo que é complicado e confuso.
DW
11
Obrigado pela resposta rápida! Perdi o ponto em que você se concentra em provar o algoritmo, se houver apenas a single, unique optimal solution. Como esta pergunta é sobre como provar que qualquer algoritmo guloso está correto, eu gostaria de fornecer uma resposta para casos em que várias soluções ótimas possam existir. Já faz um tempo desde que estudei tudo isso, mas não basta provar que você pode trocar cada elemento O_i em qualquer solução ótima O que difere do alg. solução S com S_i e ainda tem uma solução O 'que não é pior que O?
citelao 8/09/18
@ citelao, a técnica também se aplica a casos em que existem várias soluções ideais. Sugeri focar no caso em que a solução ideal é única apenas porque, na primeira vez em que você vê isso, é mais fácil entender como essas provas funcionam nesse cenário. Mas a mesma estratégia funciona mesmo se houver várias soluções ideais. Sugiro estudar isso, certificando-se de entender como ele funciona quando houver uma única solução ideal e aplicá-la ao caso geral. Também acho que pode ajudar você a estudar algumas provas de exemplo para algoritmos gananciosos.
DW
Para responder à sua última pergunta, não, isso não é suficiente. Isso não prova que S é o ideal. (Se você exige apenas que O 'não seja pior que O, há casos em que S é subótimo, ainda assim é possível fazer esse tipo de troca. Portanto, provando que é possível obter um O' que não é pior que O não prove qualquer coisa sobre se S é o ideal e não prova que o algoritmo guloso está correto. Sugiro estudar um pouco mais o método descrito na resposta. É complicado. Prova de contradição geralmente é difícil de entender.)
DW
14

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.AA[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<jA[i]>A[j]iji+1<jA[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.

adrianN
fonte
As técnicas explicadas são tão gerais que praticamente não têm nada em particular sobre o algoritmo ganancioso, o tópico desta questão.
precisa saber é o seguinte