Implementación del algoritmo GSAT: ¿cómo seleccionar qué literal voltear?

El algoritmo GSAT es, en su mayor parte, directo: obtienes una fórmula en forma conjuntiva normal y cambias los literales de las cláusulas hasta que encuentres una solución que satisfaga la fórmula o alcances el límite max_tries / max_flips y no encuentres solución.

Estoy implementando el siguiente 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

Tengo problemas para interpretar la siguiente línea:

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

¿No es el número máximo de cláusulas satisfechas lo que estamos buscando? Me parece que estamos tratando de usar la solución o aproximaciones para encontrar la solución.

He pensado en algunas formas de hacer esto, pero sería bueno escuchar otros puntos de vista (la suposición es que una vez que la variable se voltea una vez que se selecciona):

• Genere un espacio de estado con todos los cambios posibles y busque en el espacio un literal que resulte en la mejor aproximación al estado del objetivo.
• Seleccione al azar la variable que voltearé comenzando con los literales que son más comunes.
• Elige un literal al azar.

¿No es el número máximo de cláusulas satisfechas lo que estamos buscando?

Sí, estamos buscando una tarea que satisfaga el número máximo de cláusulas (es decir, todas ellas, preferiblemente). Y para ese fin nos preguntamos "¿Qué variable única nos acercará más a este objetivo cuando lo volteemos?" y luego voltéalo.

Me parece que estamos tratando de usar la solución o aproximaciones para encontrar la solución.

Usar la solución sería si preguntamos "¿Qué combinación de varias vueltas daría el mejor resultado?" o simplemente "¿Qué tarea sería la mejor?". Sin embargo, eso no es lo que estamos haciendo, solo estamos mirando un paso adelante. Usar una aproximación de la solución parece una descripción precisa. Sin embargo, no hay nada de malo en eso. Así funcionan las estrategias codiciosas.

Genere un espacio de estado con todos los cambios posibles y busque en el espacio un literal que resulte en la mejor aproximación al estado del objetivo.

Correcto.