Tratar de encontrar la solución óptima para WEIGHTED-MAX-3SAT, la versión ponderada del problema de optimización 3-SAT, es NP-hard. De hecho, incluso aproximar la versión no ponderada de MAX-SAT arbitrariamente es probablemente NP-duro por el teorema de PCP.
Un algoritmo canónico para aproximar WEIGHTED-MAX-3SAT es MAX-WalkSAT. Al mirar alrededor, encontré información sobre otros algoritmos (es decir, el algoritmo DPL de ramificación y unión) que se usan comúnmente para encontrar soluciones a 3-SAT o MAX-3SAT (no ponderado), pero no vi ninguna discusión sobre cómo bueno, estos funcionarían para la versión ponderada. Intuitivamente, sin estar adaptados, no funcionarían tan bien.
Me pregunto qué otros algoritmos se usan comúnmente para aproximar WEIGHTED-MAX-SAT, si hay solucionadores WEIGHTED-MAX-SAT conocidos, y la calidad relativa de estos algoritmos / solucionadores.
fuente
Respuestas:
Bueno, esto puede formularse como el problema de encontrar el estado fundamental de un hamiltoniano similar a Ising con términos de 3 locales. Esto no ocurre naturalmente, pero es de esperar que se enfríen de manera similar a otros sistemas, por lo que el recocido simulado debería funcionar bien para la versión ponderada.
fuente
Creo que se puede reducir simplemente duplicando las fórmulas de acuerdo con su peso y, por lo tanto, los resultados de límite superior e inferior para 3-SAT no ponderados también se aplican a las versiones ponderadas, con pérdidas arbitrariamente pequeñas. Y de acuerdo con un resultado clásico de Johan Håstad, es NP-difícil aproximar 3-SAT más allá de 7/8, que es el desempeño de asignar valores aleatorios.
No estoy seguro del rendimiento de los algoritmos utilizados en la práctica.
fuente