Consulta Teoría CPS

[jose manzo]

Hola Profes, buenas tardes

Tengo la siguiente definición sobre las Heurísticas Genéricas

     1. Variables más restringidas primero.

     2. Las restricciones con menos variables.

¿Es lo mismo que?

~ la siguiente...

~ Minimun remaining values (MRV): elige la variable más restringida primero.

~ Grado heurístico: variable con mayor apariciones en restricciones primero. Se usa generalmente para desempatar luego de aplicar MRV.

~ Least constraining value (LCV): elige primero el valor que menos opciones quita al resto de las variables.

¿estas últimas también son heurísticas genéricas o no?

estuve buscando el libro de "Artificial Intelligence - A Modern Approach (3rd Edition)" y no encontré una definición clara sobre las Heurísticas Genéricas. 

¿Hay más Heurísticas Genéricas? ¿Hay algo mas de información que deba agregar a las 2 que ya tengo? 

Saludos. 

[Ariel Rossanigo]

Buenas, las heurísticas que se mencionan en el libro son:

Para backtracking, selección de la próxima variable a asignar (pág 216):

• Minimum Remaining Value (MRV): el libro aclara que también se la puede conocer cómo Most Constrained Variable.. en resumen,elige la variable que tenga menos valores en el dominio primero. La idea es que el algoritmo falle lo antes posible.
• Degree heuristic o grado heurístico: elige la variable que está involucrada en mayor cantidad de restricciones.

Entiendo que el punto 1 que vos señalas es MRV, no entiendo que es el punto 2.

Para backtracking, una vez elegida la variable, qué valor asignar primero (pág 217):

• Least constraining value (LCV): va probando primero con los valores que menos restringen a las demás variables que falten asignar. 

En búsqueda local, para elegir el valor  una vez elegida la variable a modificar (pág 220):

• Min conflicts: elige el valor que menor cantidad de conflictos provoca.

No hay una definición como si fuese un diccionario (como sí ocurre con otros conceptos), pero el nombre se introduce en la intro al capítulo: 

CSP search algorithms take advantage of the structure of states and use general-purpose

rather than problem-specific heuristics to enable the solution of complex problems. The main
idea is to eliminate large portions of the search space all at once by identifying variable/value
combinations that violate the constraints.

Igual de ahí podés derivar la idea: una heurística en un sentido amplio es algo que te da un conocimiento extra... y es genérica (o de propósito genérico) porque es independiente del problema particular que estás tratando resolver. Al respecto, recordá que en búsqueda informada tenías que idear/escribir una heurística por cada problema que querías resolver. 

Estas 4 son las que se explican de forma más clara en el libro, luego hay ideas que podrían llevar a generar otras heurísticas, algunas tienen que ver con hacer más rápida la inferencia, otras con darle distintos pesos a las restricciones en la búsqueda... La respuesta  a "hay más" es que "si", la respuesta a "me exigen saber alguna más" es no. :)

Saludos!

--
You received this message because you are subscribed to the Google Groups "UCSE IA" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ucse-ia+u...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ucse-ia/1a13cbcc-23e3-4ec0-9d40-29f381fbfaf9n%40googlegroups.com.