Biblioteca73.326 documentos en línea

Artículo

Exploring the Impact of Early Decisions in Variable Ordering for Constraint Satisfaction ProblemsExploración del impacto de las decisiones tempranas en el ordenamiento de variables para problemas de satisfacción de restricciones

Resumen

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.

  • Tipo de documento:
  • Formato:pdf
  • Idioma:Inglés
  • Tamaño: Kb

Cómo citar el documento

Esta es una versión de prueba de citación de documentos de la Biblioteca Virtual Pro. Puede contener errores. Lo invitamos a consultar los manuales de citación de las respectivas fuentes.

Este contenido no est� disponible para su tipo de suscripci�n

Información del documento