Exploring the Impact of Early Decisions in Variable Ordering for Constraint Satisfaction Problems
CONTENIDO PARA USUARIOS REGISTRADOS
Inicia sesión para disfrutar este recurso. Si aún no estás afiliado a BibloRed, haz clic en el botón.
Acceder- Autor
- Año de publicación 2018
- Idioma Inglés
- Publicado por Revista VirtualPRO,
- Descripción
- Cuando se resuelven problemas de satisfacción de restricciones (CSP), es una práctica común confiar en la heurística para decidir qué variable debe ser instanciada en cada etapa de la búsqueda. Pero este ordenamiento influye en el coste de la búsqueda. Aun así, y hasta donde sabemos, ningún trabajo anterior se ha ocupado de cómo los primeros ordenamientos de las variables afectan al coste global. En este trabajo, exploramos el coste de encontrar ordenaciones de alta calidad de las variables dentro de los problemas de satisfacción de restricciones. También estudiamos las diferencias entre los ordenamientos producidos por algunas heurísticas comúnmente utilizadas y la forma en que las primeras decisiones erróneas afectan al coste de la búsqueda. Uno de los resultados más importantes de este trabajo confirma la importancia primordial de las primeras decisiones. Otra es la evidencia de que muchas de las heurísticas de ordenación de variables existentes fallan a la hora de seleccionar adecuadamente la primera variable a instanciar. Otra es la evidencia de que muchas de las heurísticas de ordenación de variables existentes no seleccionan adecuadamente la primera variable a instanciar. Proponemos un método sencillo para mejorar las primeras decisiones de las heurísticas. Al utilizarlo, el rendimiento de la heurística aumenta.
-
Citación recomendada (normas APA)
- Hindawi, "Exploring the Impact of Early Decisions in Variable Ordering for Constraint Satisfaction Problems", -:Revista VirtualPRO,, 2018. Consultado en línea en la Biblioteca Digital de Bogotá (https://www.bibliotecadigitaldebogota.gov.co/resources/3436476/), el día 2024-05-18.