Resumen: Introducimos y comparamos una heurística de búsqueda local estocástica para el problema de satisfactuabilidad NP-completado 3-SAT que supera drásticamente a los solucionadores existentes en el reino notoriamente difícil de instancias críticamente difíciles. Nuestra construcción se basa en la observación crucial de que los enfoques anteriores bien establecidos, como Walksat, son propensos a atascarse en los mínimos locales que se distinguen de las soluciones verdaderas por un mayor número de restricciones combinatorias sobrealimentadas. Para abordar este problema, el algoritmo propuesto, DOCSAT acuñado, disipa las limitaciones sobrealimentadas (DOC), es decir, reduce su abundancia desfavorable para que las vuelva críticas. Analizamos y comparamos nuestro algoritmo en una muestra generada aleatoriamente de casos de 3-SAT difícil pero satisfactorio con diferentes tamaños de problemas hasta N = 15000. Sorprendentemente, encontramos que DOCSAT supera tanto a Walksat como a otros algoritmos bien conocidos, incluido el Solucionador completo Kissat, incluso cuando se comparan su capacidad para resolver el quintil más duro de la muestra con el rendimiento promedio de sus competidores. La esencia de DOCSAT puede verse como una forma de aprovechar la estructura estadística más allá de la función de costo primario de un problema combinatorio para evitar o escapar de las trampas mínimas locales en la búsqueda local estocástica, que abre vías para la generalización a otros problemas de optimización.
Publicado Originalme en export.arxiv.org El 22 de junio de 2025.
Ver Fuente Original
