b'\n_START_ARTICLE_\nAlgoritmo DPLL\n_START_PARAGRAPH_\nO algoritmo DPLL/Davis-Putnam-Logemann-Loveland \xc3\xa9 um algoritmo completo baseado em backtracking (re-leitura ou voltar atr\xc3\xa1s) para decidir a satisfatibilidade das f\xc3\xb3rmulas de l\xc3\xb3gica proposicional na forma normal clausal, isto \xc3\xa9, para solucionar o problema SAT._NEWLINE_O algoritmo foi introduzido em 1962 por Martin Davis, Hilary Putnam, George Logemann e Donald W. Loveland, sendo um refinamento do algoritmo de Davis-Putnam mais antigo, o qual \xc3\xa9 baseado num processo de resolu\xc3\xa7\xc3\xa3o desenvolvido por Davis e Putnam em 1960. Principalmente em publica\xc3\xa7\xc3\xb5es antigas, o algoritmo de Davis-Logemann-Loveland \xc3\xa9 freq\xc3\xbcentemente referenciado como \xe2\x80\x9cO M\xc3\xa9todo Davis-Putnam\xe2\x80\x9d ou o \xe2\x80\x9cAlgoritmo DP\xe2\x80\x9d. Outros nomes comuns que mant\xc3\xa9m a distin\xc3\xa7\xc3\xa3o s\xc3\xa3o DLL e DPLL._NEWLINE_DPLL \xc3\xa9 um procedimento altamente eficiente, e forma a base para os mais eficientes solucionadores SAT e outros problemas NP-completos que podem ser reduzidos para o problema SAT, e tamb\xc3\xa9m para muitos provadores de teoremas para os fragmentos da l\xc3\xb3gica de primeira ordem.\n_START_SECTION_\nPseudoc\xc3\xb3digo\n_START_PARAGRAPH_\nO algoritmo DPLL pode ser sumarizado no seguinte pseudoc\xc3\xb3digo, onde \xce\xa6 \xc3\xa9 a f\xc3\xb3rmula na FNC e \xce\xbc uma atribui\xc3\xa7\xc3\xa3o parcial de verdade que est\xc3\xa1 inicialmente vazia:_NEWLINE__NEWLINE_fun\xc3\xa7\xc3\xa3o DPLL(\xce\xa6, \xce\xbc)_NEWLINE_   se todas as cl\xc3\xa1usulas de \xce\xa6 forem verdadeiras _NEWLINE_       ent\xc3\xa3o retorne verdadeiro;_NEWLINE_   se alguma cl\xc3\xa1usula de \xce\xa6 for falsa_NEWLINE_       ent\xc3\xa3o retorne falso;_NEWLINE_   se ocorrer uma cl\xc3\xa1usula unit\xc3\xa1ria c em \xce\xa6_NEWLINE_       ent\xc3\xa3o retorne DPLL(atribui\xc3\xa7\xc3\xa3o(c,\xce\xa6), \xce\xbc \xe2\x88\xa7 c);_NEWLINE_   se ocorrer um literal puro c em \xce\xa6_NEWLINE_       ent\xc3\xa3o retorne DPLL(atribui\xc3\xa7\xc3\xa3o(c,\xce\xa6), \xce\xbc \xe2\x88\xa7 c);_NEWLINE_   c := escolha_literal(\xce\xa6);_NEWLINE_   retorne DPLL(atribui\xc3\xa7\xc3\xa3o(c,\xce\xa6), \xce\xbc \xe2\x88\xa7 c) ou DPLL(atribui\xc3\xa7\xc3\xa3o(\xc2\xacc,\xce\xa6), \xce\xbc \xe2\x88\xa7 \xc2\xacc);_NEWLINE_No pseudoc\xc3\xb3digo acima, atribui\xc3\xa7\xc3\xa3o(c, \xce\xa6) \xc3\xa9 uma fun\xc3\xa7\xc3\xa3o que retorna uma f\xc3\xb3rmula obtida pela substitui\xc3\xa7\xc3\xa3o de cada ocorr\xc3\xaancia de c por verdadeiro, e cada ocorr\xc3\xaancia do literal oposto por falso na f\xc3\xb3rmula \xce\xa6, e em seguida, simplificando a f\xc3\xb3rmula resultante. A fun\xc3\xa7\xc3\xa3o DPLL do pseudoc\xc3\xb3digo retorna verdadeiro se a atribui\xc3\xa7\xc3\xa3o final satisfaz a f\xc3\xb3rmula ou falso se tal atribui\xc3\xa7\xc3\xa3o n\xc3\xa3o satisfaz a f\xc3\xb3rmula. Em uma implementa\xc3\xa7\xc3\xa3o real, a atribui\xc3\xa7\xc3\xa3o satisfat\xc3\xadvel tamb\xc3\xa9m \xc3\xa9 retornada no caso de sucesso (esta foi omitida para maior clareza).\n_START_SECTION_\nOutras Considera\xc3\xa7\xc3\xb5es\n_START_PARAGRAPH_\nO algoritmo de Davis-Logemann-Loveland depende da escolha do literal ramificado, que \xc3\xa9 o literal considerado na etapa de backtracking. Em conseq\xc3\xbc\xc3\xaancia, este n\xc3\xa3o \xc3\xa9 exatamente um algoritmo, mas sim uma fam\xc3\xadlia de algoritmos, um para cada maneira poss\xc3\xadvel de escolher o literal ramificado. A efici\xc3\xaancia \xc3\xa9 fortemente afetada pela escolha do literal, existem exemplos no qual o tempo de execu\xc3\xa7\xc3\xa3o \xc3\xa9 constante ou exponencial dependendo da escolha dos literais ramificados.'