Resumen

Recientemente se ha propuesto la consistencia bidireccional de arco único (BiSAC), que es una extensión de la consistencia de arco único (SAC). La primera contribución de este artículo es proponer y demostrar teóricamente dos teoremas de BiSAC (uno es una propiedad de BiSAC y el otro es la propiedad de permitir la eliminación de algunos valores BiSAC-inconsistentes). En segundo lugar, basándonos en estas propiedades presentamos dos algoritmos, denominados BiSAC-DF y BiSAC-DP, para aplicar BiSAC. También demostramos que son correctos y analizamos en detalle su complejidad espacial y temporal. Además, para circunstancias especiales, mostramos que BiSAC-DF admite una complejidad temporal en el peor de los casos en O(en2d4) y una mejor en O(en2d3) cuando el problema ya es un BiSAC, mientras que BiSAC-DP también tiene la misma mejor cuando la estrechez es pequeña. Por último, los experimentos con una amplia gama de casos de CSP muestran que BiSAC-DF y BiSAC-DP suelen ser un orden de magnitud más rápidos que el BiSAC-1 existente. Para algunos casos especiales, BiSAC-DP es aproximadamente dos órdenes de magnitud más eficiente.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:bisac, consistencia de arco único bidireccional, consistencia de arco único ampliada, complejidad caso-tiempo, magnitud, propiedad, instancias csp, primera contribución, valores inconsistentes, circunstancias especiales
• Keywords:bisac, bidirectional singleton arc consistency, extended singleton arc consistency, case time complexity, magnitude, property, csp instances, first contribution, inconsistent values, special circumstances