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.

• Materias:Biotecnología Minería de datos Algoritmos genéticos Cerebro - fisiopatología Neurofisiología
• Subjects:Biotechnology Data mining Genetic algorithms Brain - pathophysiology Neurophysiology
• Palabras claves:problema de satisfacción de restricciones, heurística de ordenación de variables, coste de búsqueda, mala primera decisión, ordenación de variables, rendimiento de la heurística, decisión de la heurística, primera ordenación de variables, primera decisión, evidencia
• Keywords:constraints satisfaction problem, variable ordering heuristic, search cost, bad first decision, ordering of variable, performance of heuristic, decision of heuristic, first variable ordering, first decision, evidence