Implementando o algoritmo GSAT - Como selecionar qual literal virar?

O algoritmo GSAT é, em grande parte, direto: você obtém uma fórmula na forma normal conjuntiva e inverte os literais das cláusulas até encontrar uma solução que satisfaça a fórmula ou atingir o limite max_tries / max_flips e não encontra solução.

Estou implementando o seguinte algoritmo:

procedure GSAT(A,Max_Tries,Max_Flips)
  A: is a CNF formula
  for i:=1 to Max_Tries do
    S <- instantiation of variables
    for j:=1 to Max_Iter do
      if A satisfiable by S then
        return S
      endif
      V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
      S <- S with V flipped;
    endfor
  endfor
  return the best instantiation found
end GSAT

Estou tendo problemas para interpretar a seguinte linha:

V <- the variable whose flip yield the most important raise in the number of satisfied clauses;

Não é o número máximo de cláusulas satisfeitas o que estamos procurando? Parece-me que estamos tentando usar a solução ou aproximações para encontrar a solução.

Eu pensei em algumas maneiras de fazer isso, mas seria bom ouvir outros pontos de vista (a suposição é que uma vez que a variável é invertida, uma vez que é selecionada.):

• Gere um espaço de estado com todos os lançamentos possíveis e procure no literal um espaço que resulte na melhor aproximação ao estado do objetivo.
• Selecione aleatoriamente a variável que irei inverter, começando pelos literais mais comuns.
• Escolha um literal aleatório.

Não é o número máximo de cláusulas satisfeitas o que estamos procurando?

Sim, estamos procurando uma tarefa que satisfaça o número máximo de cláusulas (ou seja, todas elas, de preferência). E, para esse fim, nos perguntamos "Qual variável única nos aproximará mais desse objetivo ao lançá-lo?" e depois vire.

Parece-me que estamos tentando usar a solução ou aproximações para encontrar a solução.

Usar a solução seria se perguntássemos "Qual combinação de múltiplos lançamentos daria o melhor resultado?" ou simplesmente "Qual tarefa seria a melhor?". No entanto, não é isso que estamos fazendo, estamos apenas olhando um passo à frente. Usar uma aproximação da solução parece uma descrição precisa. No entanto, não há nada de errado nisso. É assim que as estratégias gananciosas funcionam.

Gere um espaço de estado com todos os lançamentos possíveis e procure no literal um espaço que resulte na melhor aproximação ao estado do objetivo.

Certo.