Monografias.com > Tecnología
Descargar Imprimir Comentar Ver trabajos relacionados

Problemas de satisfacción de restricciones en Inteligencia Artificial




Enviado por Pablo Turmero



Partes: 1, 2


    Monografias.com

    Problemas de satisfacción de restricciones en Inteligencia Artificial

    Monografias.com

    Problemas de satisfacción de restricciones (PSRs)
    Componentes del estado = grafo de restricciones:
    Variables
    Dominios (valores posibles para las variables)
    Restricciones (binarias) entre las variables
    Objetivo: encontrar un estado (una asignación completa de valores a las variables) que satisface las restricciones.
    2
    2

    Monografias.com

    Problemas de satisfacción de restricciones (PSRs)
    Ejemplos:
    colorear mapas
    crucigramas
    n-reinas
    asignación/distribución/ubicación de recursos:
    distribución de tareas de fabricación
    ubicación de gasolineras
    ubicación de antenas de telefonía
    3
    3

    Monografias.com

    4
    Representación
    Problema: colorear mapa
    Ejemplo de estado:
    Variables (n) = etiquetas de nodos
    Dominios = contenido de nodos
    Restricciones = arcos dirigidos y etiquetados entre nodos
    4

    Monografias.com

    5
    Representación
    A cada paso hay una asignación de variable.
    Las soluciones deben ser asignaciones completas y por lo tanto, en el árbol de búsqueda, aparecen a profundidad n.
    El árbol se extiende sólo a profundidad n.
    Los algoritmos de búsqueda primero en profundidad son populares para PSRs.
    El camino que alcanza una solución es irrelevante.
    La clase más simple de PSR implica variables discretas y dominios finitos: problemas de coloreo de mapas, de n-reinas…
    5

    Monografias.com

    6
    Dominios finitos
    Si el tamaño máximo del dominio de cualquier variable es d, entonces el número de posibles asignaciones completas es O(dn), exponencial en el número de variables.
    Los PSRs con dominio finito incluyen a los PSRs booleanos, cuyas variables pueden ser verdaderas o falsas.
    En el caso peor, no se pueden resolver los PSRs con dominios finitos en menos de un tiempo exponencial.
    Evidentemente, los algoritmos para PSR resuelven problemas órdenes de magnitud más grandes que los resolubles con algoritmos de búsqueda no informada.
    6

    Monografias.com

    7
    Dominios infinitos
    Las variables discretas pueden tener dominios infinitos (p.e., el conjunto de números enteros o de cadenas).
    Con dominios infinitos, no es posible describir restricciones enumerando todas las combinaciones permitidas de valores.
    Se debe usar un lenguaje de restricción:

    Comienzo-Trabajo1 + 5 = Comienzo-Trabajo3

    Existen algoritmos para restricciones lineales sobre variables enteras.
    7

    Monografias.com

    8
    Dominios infinitos
    No existe un algoritmo general para restricciones no lineales sobre variables enteras.
    En algunos casos, se pueden reducir los problemas de dominio infinito a dominio finito simplemente acotando los valores de todas las variables, p.e.:
    fijando límites temporales para el comienzo de los trabajos.
    8

    Monografias.com

    9
    Dominios continuos
    Los PSRs con dominios continuos son muy comunes en el mundo real.
    La categoría más conocida son los problemas de programación lineal:
    las restricciones deben ser desigualdades lineales que forman una región convexa.
    Los problemas de programación lineal pueden resolverse en tiempo polinomial en el número de variables.
    9

    Monografias.com

    Algoritmos
    Basados en búsqueda
    complejidad:
    tiempo: O(exp(n))
    espacio: O(n)
    Basados en programación dinámica
    complejidad:
    tiempo: O(exp(w*+1))
    espacio: O(exp(w*))
    Donde n es el número de variables y w* es la anchura inducida del grafo de restricciones dado un orden.
    10
    10

    Monografias.com

    11
    Algoritmos basados en búsqueda
    Formulación incremental, como en un problema de búsqueda estándar:
    Estado inicial: la asignación vacía { }, en que todas las n variables no están asignadas.
    Función de sucesor: asignación de un valor d a cualquier variable no asignada, a condición de que no suponga conflicto con variables ya asignadas.
    Test objetivo: la asignación actual es completa.
    Costo del camino: un costo constante (p.e., 1) para cada paso.
    11

    Monografias.com

    12
    Algoritmos basados en búsqueda
    Formulación completa de estados:
    Cada estado es una asignación completa que satisface o no las restricciones.
    Los métodos de búsqueda local trabajan bien para esta formulación.
    12

    Monografias.com

    13
    Algoritmos basados en búsqueda
    Búsqueda heurística
    Búsqueda en profundidad con vuelta atrás cronológica

    Propagación de restricciones
    Antes de la búsqueda
    Durante la búsqueda
    13

    Monografias.com

    14
    Restricciones
    El tipo más simple es la restricción unaria, que restringe los valores de una sola variable.
    Una restricción binaria relaciona dos variables.
    Las restricciones de orden alto implican tres o más variables. Un ejemplo son los puzzles cripto-aritméticos.
    14

    Monografias.com

    15
    Puzzles cripto-aritméticos
    Variables: F T U W R O X1 X2 X3

    Dominio: {0,1,2,3,4,5,6,7,8,9}

    Restricciones:

    TodasDif (F,T,U,W,R,O)
    O + O = R + 10 · X1
    X1 + W + W = U + 10 · X2
    X2 + T + T = O + 10 · X3
    X3 = F, T ? 0, F ? 0
    15

    Monografias.com

    Búsqueda con vuelta atrás para PSR
    Si los PSRs se formulan como problemas de búsqueda, cualquiera de los algoritmos de búsqueda vistos anteriormente los pueden resolver.
    Estado inicial: la asignación vacía { }, en que todas las n variables no están asignadas.
    Función de sucesor: asignación de un valor d a cualquier variable no asignada, a condición de que no suponga conflicto con variables ya asignadas.
    Si aplicamos la búsqueda primero en anchura, notamos algo terrible:
    El factor de ramificación en el nivel superior es de nd.
    16

    Partes: 1, 2

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter