La implementación del algoritmo GSAT - Cómo seleccionar el literal para voltear?

Question

El algoritmo GSAT es, en su mayor parte, sencillo: Se obtiene una fórmula en forma normal conjuntiva y da la vuelta a los literales de las cláusulas hasta que encuentre una solución que satisface la fórmula o que llegue a la max_tries / limitan max_flips y encontrar ninguna solución.

estoy poniendo en práctica el algoritmo siguiente:

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

Estoy teniendo 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 satisfechos de lo que estamos buscando? Me parece que estamos tratando de utilizar la solución o aproximaciones a ella para encontrar la solución.

He pensado en algunas maneras de hacer esto pero sería bueno escuchar otros puntos de vista (La suposición es que una vez que se voltea la variable una vez que se ha seleccionado.):

• Generar un espacio de estado con todos los posibles saltos y buscar el espacio para un literal que da como resultado la mejor aproximación al estado de la meta.
• seleccionar la variable aleatoria que voy a dar la vuelta a partir de los literales que son más comunes.
• Pick a literal aleatorio.

Answer 1

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

Sí, estamos buscando una asignación que satisface el número máximo de cláusulas (que es todo de ellos, preferentemente). Y con ese fin nos preguntamos "¿Qué sola variable nos traerá más cercano a este objetivo cuando darle la vuelta?" y luego darle la vuelta.

Me parece que estamos tratando de utilizar la solución o aproximaciones a ella para encontrar la solución.

El uso de la solución sería si nos preguntamos "¿Qué combinación de múltiples saltos daría el mejor resultado?" o, simplemente, "¿Qué asignación sería el mejor?". Sin embargo eso no es lo que están haciendo, sólo estamos buscando un paso por delante. Usando una aproximación de la solución parece ser una descripción exacta. Sin embargo no hay nada de malo en eso. Así es como las estrategias codiciosos trabajo.

Generar un espacio de estado con todos los posibles saltos y buscar el espacio para un literal que da como resultado la mejor aproximación al estado de la meta.

derecho.