Investigación sobre particionamiento del espacio de búsqueda basado en abstracción y resolución de problemas de satisfacibilidad
Autores: Huang, Yuexin; Niu, Qinzhou; Song, Yanfang
Idioma: Inglés
Editor: MDPI
Año: 2025
Acceso abierto
Artículo científico
2025
Investigación sobre particionamiento del espacio de búsqueda basado en abstracción y resolución de problemas de satisfacibilidad
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Problemas de satisfactibilidad
Espacios de búsqueda
Estrategias de particionamiento
Algoritmos de resolución
Método de abstracción
Particionamiento del espacio de búsqueda
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 27
Citaciones: Sin citaciones
Resolver problemas de satisfacibilidad es fundamental en muchas áreas de la informática, incluyendo la inteligencia artificial y la optimización. Resolver eficientemente problemas de satisfacibilidad requiere explorar vastos espacios de búsqueda, donde la partición del espacio de búsqueda juega un papel clave en mejorar la eficiencia de la resolución. Este documento define los espacios de búsqueda y su partición, centrándose en la relación entre las estrategias de partición y la resolución de problemas de satisfacibilidad. Al introducir un método de abstracción para la partición del espacio de búsqueda, diferente de los enfoques tradicionales basados en asignaciones, el documento propone algoritmos de resolución secuenciales, paralelos y híbridos. Los resultados experimentales muestran que el enfoque híbrido, que combina abstracción y asignación, acelera significativamente la resolución en la mayoría de los casos. Además, se presenta un método unificado para la partición del espacio de búsqueda, definiendo particiones independientes y completas. Este método ofrece una nueva dirección para mejorar la eficiencia de la resolución de problemas SAT y proporciona una base para futuras investigaciones en el campo.
Descripción
Resolver problemas de satisfacibilidad es fundamental en muchas áreas de la informática, incluyendo la inteligencia artificial y la optimización. Resolver eficientemente problemas de satisfacibilidad requiere explorar vastos espacios de búsqueda, donde la partición del espacio de búsqueda juega un papel clave en mejorar la eficiencia de la resolución. Este documento define los espacios de búsqueda y su partición, centrándose en la relación entre las estrategias de partición y la resolución de problemas de satisfacibilidad. Al introducir un método de abstracción para la partición del espacio de búsqueda, diferente de los enfoques tradicionales basados en asignaciones, el documento propone algoritmos de resolución secuenciales, paralelos y híbridos. Los resultados experimentales muestran que el enfoque híbrido, que combina abstracción y asignación, acelera significativamente la resolución en la mayoría de los casos. Además, se presenta un método unificado para la partición del espacio de búsqueda, definiendo particiones independientes y completas. Este método ofrece una nueva dirección para mejorar la eficiencia de la resolución de problemas SAT y proporciona una base para futuras investigaciones en el campo.