Source: http://docplayer.es/1260745-Razonamiento-con-restricciones-esquema-global-tutorial-caepia-2003-1-introduccion-definiciones-ejemplos.html
Timestamp: 2017-07-21 04:56:13+00:00

Document:
Razonamiento. con. Restricciones. Esquema Global. Tutorial CAEPIA Introducción - Definiciones - Ejemplos - PDF
Razonamiento. con. Restricciones. Esquema Global. Tutorial CAEPIA Introducción - Definiciones - Ejemplos
Download "Razonamiento. con. Restricciones. Esquema Global. Tutorial CAEPIA 2003. 1. Introducción - Definiciones - Ejemplos"
1 Esquema Global Razonamiento con Restricciones Tutorial CAEPIA 2003 Javier Larrosa Dep. LSI, UPC, Barcelona Pedro Meseguer IIIA, CSIC, Bellaterra 1. Introducción - Definiciones - Ejemplos 2. Métodos de Resolución - Búsqueda - Inferencia - Métodos híbridos 3. Modelización - Primal / dual - Restricciones globales - Programación con restricciones 4. Restricciones Blandas - Modelos - Algoritmos2 Satisfacción de Restricciones Interés de los CSP Definición: red de restricciones P = (X, D, C ) X = { X 1, X 2,..., X n } variables D = { D 1, D 2,..., D n } dominios C = { C 1, C 2,..., C e } Dada una restricción C i, var(c i ) = {X i1,..., X ik } rel(c i ) D i1 D i2... D ik restricciones relaciona k variables (restricción k-aria) tuplas de valores permitidos CSP: problema de resolver la red de restricciones Relevancia: Problemas reales como CSPs: Car sequencing problem Asignación de recursos (scheduling) Diseño de bloques (BIBDs) Para la IA: Restricciones: formal general de representación del conocimiento Satisfacción de restricciones: razonamiento automático Ejemplos:» SAT» razonamiento temporal» razonamiento basado en modelos Solución: asignación de valores a variables satisfaciendo todas las restricciones Complejidad: NP-completo algoritmos exponenciales (caso peor) Especialización: tipo de dominios: discretos / continuos finitos / infinitos tipo de restricciones: binarias / n-arias3 Car sequencing problem Cadena de montaje de coches FAROS ANTINIEBLA X X TECHO SOLAR X X X CLIMATIZADOR X X Asignación de recursos Job-shop scheduling n jobs, cada uno con m operaciones, m recursos, cada operación necesita un recurso de forma exclusiva durante un tiempo precedencia entre las operaciones de cada job, Se pueden realizar los n jobs en tiempo D? R2 R1 R3 A1 A2 A3 R1 R2 R3 0 B1 B2 B3 D Area techo solar Capacidad 3/5 Area climatizador Capacidad 2/3 R1 C1 R3 C2 R2 C3 tiempo Formulación: variables: n coches a producir dominios: modelos de coche restricciones: capacidad de las áreas Características: CSP no binario, discreto y finito Formulación: variables: operaciones dominios: tiempos de inicio de cada operacion restricciones: precedencia entre las operaciones de un job exclusividad de cada recurso en el tiempo Características: CSP binario, discreto y finito (acotado por D)4 Restricciones binarias N-reinas CSP binario: X = { X 1, X 2,..., X n } variables Definición: posicionar n reinas en un tablero de ajedrez n n, de forma que no se ataquen. D ={ D 1, D 2,..., D n } dominios discretos y finitos C = { C ij } restricciones binarias var(c ij ) = {X i, X j } n = 5 rel(c ij ) = {valores permitidos para X i y X j } = R ij n = X ; d = max i D i ; e = C Solución: asignación de valores a variables satisfaciendo todas las restricciones. Generalidad: todo problema n-ario se puede reformular como binario [Rossi et al, 90] Ejemplos: Coloreado de grafos Satisfacibilidad booleana (SAT) N-reinas, crucigramas, criptoaritmética Formulación: 1 reina por fila variables: reinas, X i reina en la fila i-ésima dominios: columnas posibles {1, 2,..., n} restricciones: no colocar dos reinas en la misma columna la misma diagonal R ij = {(a,b) a b i -j a -b } Características: CSP binario, discreto y finito existe un método de solución constructivo5 Coloreado de grafos Definición: Dado un grafo, n nodos m colores, asignar un color a cada nodo de forma que no haya dos nodos adyacentes con el mismo color. Colores Grafo de restricciones Grafo de restricciones: { X i } nodos { D i } dominios en los nodos { C ij } arcos etiquetados Coloreado de mapas azul, rojo azul, rojo, verde azul azul, verde X 3 azul, rojo, verde azul, rojo azul X 2 X 4 azul, verde X 1 Formulación: variables: nodos dominios: colores posibles restricciones: nodos adyacentes Características: CSP binario, discreto y finito 4-reinas X 1 X 2 X 3 X 4 X 1 X 2 1,2,3,4 1,2,3,4 1,2,3,4 1,2,3,4 X 3 X 46 Esquema Global Métodos de resolución: Búsqueda 1. Introducción - Definiciones - Ejemplos 2. Métodos de Resolución - Búsqueda - Inferencia - Métodos híbridos 3. Modelización - Primal / dual - Restricciones globales - Programación con restricciones 4. Restricciones Blandas - Modelos - Algoritmos Búsqueda: Explora el espacio de estados del problema (configuraciones posibles) Termina cuando: Encuentra una solución Demuestra que no hay solución Agota los recursos computacionales Búsqueda sistemática (BS): Visita todos los estados que podrían ser solución Algoritmos completos: Si hay solución, la encuentran Si no hay, demuestran que no existe Complejidad exponencial (caso peor) Búsqueda local (BL): Visita estados de forma heurística: No garantiza visitar todos los estados Puede repetir visitas al mismo estado Algoritmos incompletos: Puede haber solución y no encontrarla Complejidad: acotada por los recursos7 Búsqueda sistemática: árbol de búsqueda Espacio de estados: representable por un árbol raíz: asignación vacía a cada nivel asociamos una variable sucesores: valores de la variable del nivel rama: define una asignación Recorrido del árbol de búsqueda Recorrido primero en profundidad: preorden en cada nivel se asigna una nueva variable variable actual variables pasadas (asignadas), P futuras (sin asignar), F 4-reinas: X 1 X 1 pasadas X 2 X 2 actual X X futuras X X 4... visitada por visitar asignacion total asignacion parcial Arbol de búsqueda: contiene todos los estados recorrido exhaustivo método completo Si nodo actual inconsistente: subárbol sucesor no contiene soluciones no se visita se poda8 Backtracking BT: Código Búsqueda: primero en profundidad (DFS) En cada nodo: consistencia entre variables asignadas consistencia(p,actual): si consistente, continua DFS, sino, backtracking funcion test(i, a, pasadas):booleano para todo x j pasadas hacer si (a,valor(x j )) R ij retorna FALSO; retorna CIERTO; consistencia(p,actual): es suficiente comprobar que actual es consistente con P complejidad: espacial O(n), temporal O(d n ) pasadas actual futuras funcion BT(i, pasadas): booleano para todo a D i hacer x i := a; si test(i,a,pasadas) entonces si i=n retorna CIERTO; sino si BT(i+1,pasadas {x i }) retorna CIERTO; retorna FALSO; nodos inconsistentes nodo actual9 Backtracking: 4-reinas BT: Ejemplo x x x x nodos No hay solución con x 1 =1: 17 nodos10 Backtracking cronológico Backjumping X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 bloqueo Arbol de búsqueda: Observación: - cambiar el valor de X 5 no elimina el bloqueo - backtracking sobre una variable anterior: X 4 X 1 X 2 X 3 X 4 X 5 X BT: enumera todas las asignaciones parciales consistentes X 1 X 2 X 3 X 4 X 5 X Backjumping: - salta a una variable responsable del bloqueo - no enumera algunas asignaciones parciales que no conducen a la solución11 Backjumping dirigido por conflictos Conjunto conflicto de X j : - var pasadas incompatibles con algun valor de X j X 1 X 2 X 3 X 4 X 5 X 6 X 7 X {} {1} {1, 2} {1} {1, 2, 4} conjunto conflicto {1, 2, 3, 4} Búsqueda local Esquema: Optimización función objetivo: Proceso iterativo: min F(s) s s s s.... Estrategia greedy: F(s) F(s ) F(s ) F(s ).... hasta solución o agotar recursos Problema: mínimos locales permitir que F(s) < F(s ) movimientos aleatorios, reinicios, etc. Proceso : - backjumping (X j ) = max conjunto conflicto(x j ) X 1, X 2,..., X i,..., X j,...,x n - tras backjump de X j a X i, conjunto conflicto (X i ) = conjunto conflicto (X i ) {conjunto conflicto (X j ) - X i } - se transpasan a X i los conflictos de X j con Elementos: Función objetivo F(s): asocia a cada estado s un coste F(s) Vecindad N(s): Criterio selección: Complejidad: acotada por los recursos estados a los que puede ir desde s, en la siguiente iteración dado F(s) y N(s), elegir el siguiente estado s variables anteriores a X i12 Búsqueda local y CSP Esquema Global Estado s: asignación con todas las variables Vecindad N(s): s que difieren de s en valores de i variables normalmente 1 i 2 Función objetivo: F(s) = 0, si s es solución F(s) > 0, en otro caso Algoritmo Breakout: [Morris 92] cada restricción tiene un peso F(s) = suma pesos restricciones no satisfechas si una restricción no se satisface, su peso se incrementa 1. Introducción - Definiciones - Ejemplos 2. Métodos de Resolución - Búsqueda - Inferencia - Métodos híbridos 3. Modelización - Primal / dual - Restricciones globales - Programación con restricciones Algoritmo GSAT: [Selman et al, 92] busca un modelo en una fórmula proposicional cambia la variable que mejora más o empeora menos aleatoriedad, memoria, etc. 4. Restricciones Blandas - Modelos - Algoritmos13 Métodos de resolución: Inferencia Inferencia: Deduce nuevas restricciones implícitas P genera un P = P + restricciones implícitas P es equivalente a P, SOL(P) = SOL(P ) Completa: consistencia global sintetiza una única restricción global tuplas permitidas = soluciones resuelve completamente el problema coste exponencial Incompleta: consistencia local P es más fácil de resolver que P espacio estados P > espacio de estados P no resuelve completamente el problema, necesita búsqueda puede detectar si no hay solución coste polinómico uso: antes o durante la búsqueda Propagación de restricciones Restricciones: explícitas: definición del problema implícitas: inducidas por la acción de las explícitas Propagación: descubre ciertas restricciones implícitas X 1 R X 12 :(a,b) (b,c) 2 a, b, c a, b, c R 13 : (a,c) (c,b) a, b, c X 3 X 1 R X 12 :(a,b) (b,c) 2 a, b, c a, b, c R 13 : (a,c) (c,b) a, b, c X 3 R 23 : (b,c)14 Operaciones con restricciones: Proyección y Join Proyección: c restricción, proyección c sobre var(c) - {x}: c var(c ) = var(c) - {x} Join: rel(c ): formado por las tuplas de rel(c), x y z a b b b a c c b a c b b eliminando la componente de x proyeccion[y,z] c, c restricciones, join(c,c ) = c var (c ) = var(c) var(c ) t tupla de valores sobre var (c ), t rel(c ) ssi t [var(c)] rel(c) t [var(c )] rel(c ) x y z a b b b a c c b a c b b tal que y Inferencia Completa Sintetizar una restricción n-aria, global: que sustituya a las restricciones iniciales sus tuplas son las soluciones del CSP Es fácil: join de todas las restricciones iniciales join(c 1, C 2,, C e ) Complejidad: espacial O(d n ), temporal O(d n ) es MUY costoso!! es MAS de lo necesario para encontrar todas las soluciones del CSP!! consistencia adaptativa [Dechter, Pearl, 87] x a b b c y a a b c x a b z a c join x y z a a a b a c b b c15 Consistencia Adaptativa Eliminación de Variable Problema P, variable X, C X : restricciones sobre X IDEA: - Sustituir C X por c - c resume el efecto de C X sobre P - c no menciona X entonces X se puede eliminar eliminación de variable Para eliminar var X: Join todas las restricciones C x c Sustituir C x por c Proyectar la variable x fuera c c x x Cx c PROCESO: orden estático de variables problemas P -> P -> P ->. -> P (n-1 variables n n-1 n-2 1 Sustituir c por c Si existe c var(c ) = var(c), c c c x c SOLUCION: - S (n-1 solución de P (n-1 - S (n-2 solución de P (n-2 a partir de S (n S solución de P a partir de S Para obtener la solución: Variables se procesan en orden inverso Se asigna a X un valor consistente con variables anteriores, y con restricciones intermedias totalmente asignadas Complejidad: espacial O(nd w* ), temporal O(n(2d) w*+1 ) w* : anchura inducida del grafo por el orden de vars (máxima aridad de las restricciones intermedias)16 Ejemplo: 4-reinas (x 1 ) Ejemplo: 4-reinas (x 2 ) x 1 x 2 join x 1 x 2 proyecta x 1 x 2 x 1 x 2 join x 1 x 2 proyecta x 1 x 2 x 3 x 4 x 3 x 4 x 3 x 4 x 3 x 4 x 3 x 4 x 3 x 4 x 1 x 2 x 3 x x 1 x 2 x 3 x x 2 x 3 x x 3 x17 Ejemplo: 4-reinas (x 3 ) Ejemplo: Todas las soluciones 4-reinas join proyecta x 4 x 3 x 2 x 1 x 1 x 2 x 1 x 2 x 1 x 2 SOLUCION 1: x 3 x 4 x 3 x 4 x 3 x 4 x x 3 x x 3 x x 2 x 3 x x 1 x 2 x 3 x x 1 x 2 x 3 x18 Ejemplo: Todas las soluciones 4-reinas Inferencia incompleta: Consistencia local x 4 x 3 x 2 x 1 Subredes de 1, 2, 3 variables de P SOLUCION 2: Determinar si son consistentes: x SI, pero hay valores que no aparecen en ninguna solución de la subred, se eliminan de P - NO, P no tiene solución x 3 x x 2 x 3 x x 1 x 2 x 3 x x 1 x 2 x 3 x Niveles de inferencia: Subredes de 1 variable: Nodo consistencia Subredes de 2 variables: Arco consistencia Subredes de 3 variables: Camino consistencia.... Subredes de k variables: k-consistencia Si un dominio queda vacio: NO hay solución19 Consistencia de nodos Consistencia de arcos Variable x i es nodo consistente (NC) ssi todo valor de D i está permitido por R i P es NC ssi todas sus variables son NC Una restricción C ij es arco consistente direccional (de i a j) ssi para todo valor a D i existe b D j tal que (a, b) R ij Una restricción C ij es arco consistente si es arco consistente direccional en los dos sentidos Algoritmo NC: Un problema es arco consistente ssi todas sus restricciones lo son. procedimiento NC-1 (X,D,C) para todo x i X hacer para todo a D i hacer si a R i entonces D i := D i -{a}; a b c X k X i a a X j Equivalente a: D i := D i R i i: 1,, n b b c c20 Filtrado por consistencia de arcos Idea: si para a D i no existe b D j t.q. (a, b) R ij, se puede eliminar a de D i porque a no estará en ninguna solución. Filtrado de dominios por consistencia de arcos: se eliminan valores arco inconsistentes se itera hasta que no hay cambios Coloreado de grafos: X 2 X 1 azul, rojo azul X 4 X 3 azul, rojo, azul, verde verde X 1 Función revise(i,j) Función revise(i,j): convierte R ij en arco consistente direccional puede eliminar valores del dominio D i se ha de iterar sobre las otras restricciones funcion revise (i,j variable): bool; cambio := FALSO; para cada a D i hacer si no hay b D j tq.(a,b) R ij entonces D i := D i - {a}; cambio := CIERTO; retorna cambio; Complejidad: O(d 2 ) X azul, rojo 2 PUNTO FIJO azul X 4 X 3 azul, rojo, azul, verde verde21 AC-3: Algoritmo consistencia de arcos Consistencia de caminos a, b, c,.. X k revise(k,m) X m Un par de valores ((i, a) (j, b)), tal que (a, b) R ij, es camino consistente ssi para todo X k, i k, j k, existe c D k tal que, X p X q X r (a, c) R ik y (c, b) R kj revise(k,m) borra b y c de D k Qué arcos hay que revisitar? Aquellos que han dejado de ser arco consistentes por el borrado de b y c. (k,_): no, si era AC, lo sigue siendo tras el borrado (_,k): si, puede dejar de ser AC por el borrado Un par de variables (X i, X j ) es camino consistente ssi todo par de valores (a, b) R ij es camino consistente. Un problema P es camino consistente ssi todo par de variables es camino consistente. a b X k procedimiento AC-3 (G) Q := {(i,j) (i,j) arcos(g), i j} mientras Q Ø hacer selecciona y borra un arco (k,m) de Q si revise(k,m) entonces Q:=Q {(i,k) (i,k) arcos(g),i k,i m} X i (a,b) (b,a) a b (a,a) (b,b) (a,a) (b,b) a b X j Complejidad: O(ed 3 )22 Ejemplo PC-2 a b X k Funcion revise3(i,j,k): convierte C ij en camino consistente con x k puede eliminar pares de valores permitidos X i a b a b X k a b X j funcion revise3 (i,j,k variable): bool; cambio := FALSO; para cada (a,b) R ij hacer si c D k tq.(a,c) R ik (b,c) R jk entonces R ij := R ij - {(a,b)}; cambio := CIERTO; retorna cambio; Complejidad: O(d 3 ) PC-2: revise3 sobre todos los triangulos posibles X i a b R ij = restricción vacía a b X j procedimiento PC-2 (X,D,C) Q := {(i,j,k) 1 i<j n,1 k n,k i,k j}; mientras Q Ø hacer selecciona y borra (i,j,k) de Q; si revise(i,j,k) entonces Q:=Q {(l,i,j)(l,j,i) 1 l n,l j,l i}; no hay solución!! Complejidad: O(n 3 d 5 )23 K-Consistencia K-consistencia: Ejemplo K-Consistencia: - dado un subconjunto de k-1 variables asignadas {X 1, X 2,..., X k-1 } consistente; X 2 rojo, azul - para cualquier X k existe d D k tal que {X 1,X 2,..., X k } es consistente. X 1 X 3 K-Consistencia: generalización 1-consistencia: consistencia de nodos 2-consistencia: consistencia de arcos rojo rojo 3-consistencia: consistencia de caminos.... K-Consistencia fuerte: J-consistente, para 1 J K Algoritmos para K-consistencia fuerte: Freuder 82, Cooper 89 Complejidad: O(exp K) K-consistencia no implica K-consistencia fuerte Ejemplo: - Es 3-consistente: para cualquier par de dos variables con valores consistentes, existe un valor consistente para la tercera - No es 2-consistente: arco X2 - X124 Problemas libres de backtracking Orden de variables: { X 1, X 2,..., X n } Anchura de un nodo: # arcos a nodos anteriores Anchura de una ordenación: max i {anchura X i } Anchura de un grafo: min anchura ordenaciones X 1 X 2 X 1 X 2 X 3 X 4 X 3 X 4 anchura = 2 TEOREMA: Dado un orden de variables con anchura K, el problema se puede resolver sin backtracking si el nivel de consistencia fuerte es mayor que K. [Freuder 82] Algoritmos: K-consistencia: O(exp k). Añade arcos extras, aumenta la anchura No añade arcos para anchura 1 Los árboles tienen anchura 1 Estructura de árbol = libre de backtracking, tras consistencia de arcos Esquema Global 1. Introducción - Definiciones - Ejemplos 2. Métodos de Resolución - Búsqueda - Inferencia - Métodos híbridos 3. Modelización - Primal / dual - Restricciones globales - Programación con restricciones 4. Restricciones Blandas - Modelos - Algoritmos25 Métodos de resolución: Algoritmos híbridos Búsqueda sistemática + inferencia incompleta Algoritmo Híbrido = búsqueda + inferencia Búsqueda sistemática + inferencia incompleta: Algoritmos de anticipación Forward Checking Maintaining Arc Consistency Búsqueda sistemática + inferencia completa: Variable Elimination Search Búsqueda: BT (DFS) Inferencia incompleta: en cada nodo, consistencia local: ANTICIPACION se descuben tuplas prohibidas disminuye el tamaño del espacio aumenta la eficiencia de la búsqueda si dominio futuro = Ø no hay solución en esa rama backtracking compromiso: podemos evitar visitar #nodos exponencial coste polinómico de inferencia en cada nodo nodo actual anticipa la detección de no solución26 Anticipación: Ejemplo Anticipación: Ejemplo 6-reinas: Hay solución en los descendientes de este nodo? No hay solución. Ultima variable sin valores factibles. Anticipación: eliminar valores prohibidos de dominios futuros si dominio futuro = Ø, no hay solución27 Esquema de anticipación 1. Búsqueda: 1. Variable actual X i D i = {a, b, c} 2. Asignación X i a D i = {a } Forward Checking Forward Checking: [Haralick, Elliot, 80] búsqueda en profundidad en cada nodo, arco consistencia sobre las restricciones parcialmente asignadas 2. (Consistencia entre pasadas) 3. Tras asignar ( reducción de dominio) consistencia local parte / todo el problema nivel de consistencia si dominio futuro = Ø no hay solución en esa rama backtracking sino, se continúa (punto 1) Caso binario: se eliminan de los dominios futuros los valores incompatibles con el recién asignado C Xi : restricciones que involucran a x i Proceso: en cada nodo AC(C actual ) se acumula la poda en la rama actual Compromiso coste / beneficio coste, beneficio con tamaño parte localmente consistente nivel de consistencia compromiso óptimo: depende del problema en general, consistencia de arcos AC(C X1 ) AC(C X2 ) AC(C actual )28 FC: Código FC: Ejemplo valor asignado valor podado valor usado sin éxito funcion FC (i,past,[d i,,d n ]): booleano; para cada a D i hacer x i :=a; si i = n entonces retorna CIERTO; sino C := {C ij C ij C, i<j}; NewD:=AC({x i,..,x n },[{a},d i+1,..,d n ],C ); si NewD no contiene Ø entonces si FC(i+1,Past {x i },NewD) entonces retorna CIERTO; retorna FALSO; No hay solución con x 1 =1: 4 nodos 9 nodos29 Maintaining arc consistency MAC: [Sabin, Freuder, 94] búsqueda en profundidad en cada nodo, arco consistencia sobre todas las restricciones Arbol de búsqueda: binario en cada nivel una variable x i dos opciones: a, a se puede cambiar de variable sin agotar valores en cada nodo, AC del subproblema actual X i =a X i a X j =b X j b X k =c X k c X j =d X j d X i =f X i f MAC: Código funcion MAC (i, [D 1,,D n ]): booleano; para j:=i+1,..,n hacer D j :=D j ; para cada a D i hacer /* x i :=a *)/ D i :={a}; si i = n entonces retorna CIERTO sino NewD:=AC(X,[D 1,..,D i-1,d i,..,d n ],C); si NewD no contiene Ø entonces si MAC(i+1,NewD) entonces retorna CIERTO; /* x i : a *)/ D i := D i - {a}; D i := D i ; NewD:=AC(X,[D 1,..,D i-1,d i,..,d n ],C); si NewD contiene Ø exit bucle sino para j:=i+1,..,n hacer D j :=NewD[j]; retorna FALSO;30 MAC: AC entre Futuras MAC: Ejemplo AC (2,3) X 1 = 1 X 1 1 AC (3,4) AC (2,3) 7 nodos No hay solución con x 1 =1: 1 nodo31 Búsqueda sistemática + inferencia completa Variable Elimination Search Búsqueda sistemática + inferencia completa: X 1 DECISIÓN: a cada nueva variable x aplicamos búsqueda o eliminación si búsqueda, árbol, backtracking tras asignación x, nuevo grafo si eliminación generamos un nuevo problema X 2 X 3 X Decidimos eliminar X 2 Compromiso: coste de eliminación: exp(w* ) anchura grafo coste búsqueda: exp(#variables búsqueda) Elim(X 2 ) Elim(X 2 ) Elim(X 2 ) Elim(X 2 )32 Variable Elimination Search VES: orden estático de variables Variable actual: x Búsqueda: tras asignar x, anticipación x queda fijada en esa rama modifica la topología del grafo Eliminación: coste: d w* w* anchura de x si w* pequeña, eliminación es competitiva X 1 X 2 X 3 Ordenación de variables Ordenación estática de variables: cada nivel del árbol de búsqueda se asocia con una variable X No es necesaria para que el árbol de búsqueda sea exhaustivo. Es necesario que cada nodo se asocie con una variable para la generación de sucesores. X 1 X 4 X 3 X 2 X 3 X 4 X... 4 X X 2 X 2 X 3 X 2 X Diferentes variables en el mismo nivel: ordenación dinámica de variables33 Heurística: selección de variable Ejemplo: 6 reinas En nodo q qué variable asignar a continuación? 1. Hay solución en sucesores(q): cualquier variable es adecuada 2. No hay solución en sucesores(q): asignar la variable que antes descubre que no hay solución En general, qué situación es más frecuente? Salvo problemas triviales, situación 2 Mayor esfuerzo del algoritmo: salir de subproblemas sin solución Suponemos situación 2: asignar primero aquella variable que, aparentemente, antes nos conduce a un fallo (principio fail-first) 4 nodos Heurística dominios mínimos: asignar primero la variable con menor número de valores factibles para detectar que no hay solución con (1,2) (6,6)34 Ejemplo Heurística: selección de valor En nodo q qué valor asignar a continuación? 1. Hay solución en sucesores(q): un valor que mantenga la resolubilidad del nodo sucesor 2. No hay solución en sucesores(q): cualquier valor es adecuado Suponemos situación 1: asignar primero aquél valor que, aparentemente, antes nos conduce al éxito (principio success-first) 6 nodos Heurística anticipación valores: asignar primero el valor que es consistente con mayor número de valores factibles del resto de variables para detectar que no hay solución con (1,2) (6,6)35 Coste heurísticas Compromiso coste / beneficio: coste: suma de costes de cálculo en cada nodo beneficio en todo el árbol sale a cuenta si coste < beneficio Dominios mínimos y anticipación: Dominios mínimos: calcula #valores factibles Alg. anticipación: calculan los valores factibles obtiene dominios mínimos sin coste adicional Evaluación de las heurísticas: Evaluación empírica Esfuerzo computacional: constraint checks tiempo CPU Resultados empíricos, 20 reinas, 1ª solución BT cc FC cc FC+dom min cc36 Documentos relacionados
Esquema Global Razonamiento con Restricciones Tutorial IBERAMIA 2002 Javier Larrosa Dep. LSI, UPC, Barcelona Pedro Meseguer IIIA, CSIC, Bellaterra 1. Introducción - Definiciones - Ejemplos 2. Métodos de Más detalles Algoritmos para CSP 1
Algoritmos para CSP 1 1. Técnicas de Consistencia, o Inferenciales I. Inferencia, o consistencia completa Proceso que permite la síntesis de todas las restricciones de un problema en una única restricción Más detalles Restricciones. Inteligencia Artificial. Ingeniería Superior en Informática, 4º Curso académico: 2011/2012 Profesores: Ramón Hermoso y Matteo Vasirani
Restricciones Ingeniería Superior en Informática, 4º Curso académico: 2011/2012 Profesores: Ramón Hermoso y Matteo Vasirani 1 Tema 2: Agentes basados en Búsqueda Resumen: 2. Agentes basados en búsqueda Más detalles Satisfacción de Restricciones
Satisfacción de Restricciones Introducción Componentes del estado: Variables Dominios (valores posibles para las variables) Restricciones binarias entre las variables Objetivo: Encontrar un estado que Más detalles Tema 3: Problemas de Satisfacción de Restricciones
Tema 3: Problemas de Satisfacción de Restricciones Universidad de Granada Tema 3: Satisfacción de Restricciones Contenido Problemas de satisfacción de restricciones Métodos de búsqueda Búsqueda local para Más detalles Problemas de Satisfacción de Restricciones
Problemas de Satisfacción de estricciones José Luis uiz eina José Antonio Alonso Jiménez Franciso J. Martín Mateos María José Hidalgo Doblado Dpto. Ciencias de la Computación e Inteligencia Artificial Más detalles Tema 5: Problemas de satisfacción de restricciones
Tema 5: Problemas de satisfacción de restricciones José Luis uiz eina José Antonio Alonso Franciso J. Martín Mateos María José Hidalgo Departamento de Ciencias de la Computación e Inteligencia Artificial Más detalles Razonamiento con restricciones. Pedro Meseguer IIIA CSIC Bellaterra
Razonamiento con restricciones Pedro Meseguer IIIA CSIC Bellaterra Un poco de historia:" comienzos" mejoras algorítmicas" extensiones" CSP, ejemplos, aplicaciones" Sumario! Algoritmos de resolución: búsqueda Más detalles Programación con Restricciones Constraint Programming
Programación con Restricciones Constraint Programming Introducción basada en Roman Barták: Guide to Constraint Programming http://kti.ms.mff.cuni.cz/~bartak/constraints/index.html Constraint Programming Más detalles Problemas de satisfacción de restricciones. Javier Ramírez Rodríguez Departamento de Sistemas Universidad Autónoma Metropolitana
Problemas de satisfacción de restricciones Javier Ramírez Rodríguez Departamento de Sistemas Universidad Autónoma Metropolitana La programación con restricciones (PR) ha generado gran expectación entre Más detalles Algoritmos de planificación basados en restricciones para la sustitución de componentes defectuosos Irene Barba Rodríguez, 48861238S irenebr@us.
Algoritmos de planificación basados en restricciones para la sustitución de componentes defectuosos Irene Barba Rodríguez, 48861238S irenebr@us.es Supervised by Prof. Dr. Carmelo del Valle Sevillano Thesis Más detalles Hoja de Problemas Tema 6 Búsqueda con estados estructurados: Restricciones
Ejercicio 1: 1.1. Si se resuelve un problema de satisfacción de restricciones mediante búsqueda con asignaciones parciales, entonces (a) (b) (c) (d) (e) Un estado siempre asigna un valor a todas las variables Más detalles Problemas de satisfacción de restricciones.
Problemas de satisfacción de restricciones. In whitch we see how treating states as more than just little black boxes leads to the invention of a range of powerful new search methods and a deeper understanding Más detalles Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial ISSN: 1137-3601 revista@aepia.org
Inteligencia Artificial. Revista Iberoamericana de Inteligencia Artificial ISSN: 1137-3601 revista@aepia.org Asociación Española para la Inteligencia Artificial España Barber, Federico; Salido, Miguel Más detalles III. BÚSQUEDA Y RESOLUCIÓN DE PROBLEMAS. III.3.
III. BÚSQUEDA Y RESOLUCIÓN DE PROBLEMAS. III.3. Búsquedas con retroceso. III.3.1. Búsquedas con retroceso a ciegas. III.3.1.1. Procedimientos con retroceso. La búsqueda con retroceso, o backtracking, es Más detalles Resolución de problemas
Inteligencia en Redes de Comunicaciones Resolución de problemas Julio Villena Román jvillena@it.uc3m.es El problema de resolver problemas La resolución de problemas es uno de los procesos básicos de razonamiento Más detalles DEPARTAMENTO DE INGENIERÍA EN SISTEMAS Y COMPUTACIÓN OPCIÓN I
Introducción Resolución de Problemas La resolución de problemas es una capacidad que consideramos inteligente Somos capaces de resolver problemas muy diferentes Encontrar el camino en un laberinto Resolver Más detalles El proyecto realizado consiste en un resolutor de sudokus mediante CSP.
Introducción El proyecto realizado consiste en un resolutor de sudokus mediante CSP. El problema del sudoku fue inventado por Howard Garns en 1979 y se volvió muy popular en Japón en 1986. En España ha Más detalles Descripción inicial del sistema. Descripción final del sistema. Estado 1 Estado 2 Estado n
Búsqueda en Inteligencia Artificial Fernando Berzal, berzal@acm.org Búsqueda en I.A. Introducción Espacios de búsqueda Agentes de búsqueda Uso de información en el proceso de búsqueda Búsqueda sin información Más detalles Inteligencia Artificial. Visiones: Árboles de Búsqueda Técnicas Look-Back Técnicas Look-Ahead. Elizabeth Montero Ureta.
Inteligencia Artificial Elizabeth Montero Ureta Departamento de Informática Universidad Técnica Federico Santa María Campus Santiago 1 1er Semestre 2009 1/18 2/18 Visiones: Tiene una solución? Encontrar Más detalles Representación basada en Restricciones
Representación basada en Restricciones Asunción Gómez-Pérez asun@fi.upm.es Departamento de Inteligencia Artificial Facultad de Informática Universidad Politécnica de Madrid Campus de Montegancedo sn, 28660 Más detalles Métodos Heurísticos en Inteligencia Artificial
Métodos Heurísticos en Inteligencia Artificial Javier Ramírez rez-rodríguez Ana Lilia Laureano-Cruces Universidad Autónoma Metropolitana Métodos Heurísticos en Inteligencia Artificial Los problemas de Más detalles 1 Agencia de viajes: enunciado
Apuntes de Matemática Discreta 6. Relaciones Francisco José González Gutiérrez Cádiz, Octubre de 2004 Universidad de Cádiz Departamento de Matemáticas ii Lección 6 Relaciones Contenido 6.1 Generalidades..................................... Más detalles Búsqueda Heurística IV
Búsqueda Heurística IV Pedro Meseguer IIIA-CSIC Bellaterra, Spain pedro@iiia.csic.es 2 jugadores Búsqueda para juegos Perfecta información: cada jugador conoce toda la información del contrario no hay Más detalles Programación Lineal Entera
Programación Lineal Entera P.M. Mateo y David Lahoz 2 de julio de 2009 En este tema se presenta un tipo de problemas formalmente similares a los problemas de programación lineal, ya que en su descripción Más detalles Ampliación de Inteligencia Artificial (Curso 2014 15) Grado en Ingeniería Informática - Tecnologías Informáticas
Ampliación de Inteligencia Artificial (Curso 2014 15) Grado en Ingeniería Informática - Tecnologías Informáticas Tema 2: Problemas de satisfacción de restricciones 1. Describir en pseudocódigo un algoritmo Más detalles RAZONAMIENTO BASADO EN MODELOS: RAZONAMIENTO CUALITATIVO RAZONAMIENTO CUALITATIVO BASADO EN RESTRICCIONES
RAZONAMIENTO BASADO EN MODELOS: RAZONAMIENTO CUALITATIVO RAZONAMIENTO CUALITATIVO BASADO EN RESTRICCIONES 1 CONTENIDOS Introducción al modelado basado en restricciones La variable cualitativa y su representación Más detalles Sistemas de producción y búsqueda de soluciones. Area de Computación e Inteligencia Artificial 1
Sistemas de producción y búsqueda de soluciones Area de Computación e Inteligencia Artificial 1 Técnicas de búsqueda Resolución de problemas en Inteligencia Artificial. En general, podemos afirmar que Más detalles Secuenciación de una línea mixed-model mediante un algoritmo exacto Pág. 1. Resumen
Secuenciación de una línea mixed-model mediante un algoritmo exacto Pág. 1 Resumen En una línea de montaje de productos mixtos, aquella que es responsable de la producción de diversas variaciones de un Más detalles Capítulo 12: Indexación y asociación
Capítulo 12: Indexación y asociación Conceptos básicos Índices ordenados Archivos de índice de árbol B+ Archivos de índice de árbol B Asociación estática Asociación dinámica Comparación entre indexación Más detalles Algoritmos sobre Grafos
Sexta Sesión 27 de febrero de 2010 Contenido Deniciones 1 Deniciones 2 3 4 Deniciones sobre Grafos Par de una lista de nodos y una lista de enlaces, denidos a su vez como pares del conjunto de nodos. Más detalles Restricciones sobre dominios finitos con Gprolog
Autores: Rubén García Portal Nikolai Smirnov Restricciones sobre dominios finitos con Gprolog Introducción. Este documento explicará brevemente las funciones que se utilizan en Gprolog para resolución Más detalles ÁRBOLES GENERALES Y Y ESTRUCTURAS DE ÍNDICES DEFINICIONES Y REPRESENTACIONES DEFINICIONES Y REPRESENTACIONES. NOMENCLATURA SOBRE ÁRBOLES. DECLARACIÓN Y REPRESENTACIÓN.. CONSTRUCCIÓN.. ÁRBOLES 2-3-4. ÁRBOLES Más detalles {} representa al conjunto vacío, es decir, aquel que no contiene elementos. También se representa por.
2. Nociones sobre Teoría de Conjuntos y Lógica Para llevar a cabo nuestro propósito de especificar formalmente los problemas y demostrar rigurosamente la correctitud de nuestro programas, introduciremos Más detalles METAHEURISTICAS Ideas, Mitos, Soluciones
METAHEURISTICAS Ideas, Mitos, Soluciones OPTIMIZACION COMBINATORIA Qué es un problema de optimización combinatoria? Cómo se modela matemáticamente un problema de optimización combinatoria? Minimizar (o Más detalles Resumen de técnicas para resolver problemas de programación entera. 15.053 Martes, 9 de abril. Enumeración. Un árbol de enumeración
5053 Martes, 9 de abril Ramificación y acotamiento () Entregas: material de clase Resumen de técnicas para resolver problemas de programación entera Técnicas de enumeración Enumeración completa hace una Más detalles Desarrollo de SBC. cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 1 / 41
Desarrollo de SBC Ingeniería de los SBC Desarrollo de SBC El punto más importante del desarrollo de SBC es la extracción del conocimiento Requiere la interacción entre el Ingeniero del Conocimiento y el Más detalles Un grafo G es un par (V,E) donde V es un conjunto (llamado conjunto de vértices) y E un subconjunto de VxV (conjunto de aristas).
TEMA 5.- GRAFOS 5.1.- DEFINICIONES BÁSICAS Un grafo G es un par (V,E) donde V es un conjunto (llamado conjunto de vértices) y E un subconjunto de VxV (conjunto de aristas). Gráficamente representaremos Más detalles Estructuras de Datos. Montículos. Montículos. Montículos. Tema 3. Montículos. Definiciones básicas: Definiciones básicas:
Estructuras de Datos Tema. 1. Definiciones básicas 2. Implementación. Operaciones con montículos 4. Definiciones básicas: En un árbol binario completo todos los niveles del árbol (excepto tal vez el último) Más detalles Complejidad - Problemas NP-Completos. Algoritmos y Estructuras de Datos III
Complejidad - Problemas NP-Completos Algoritmos y Estructuras de Datos III Teoría de Complejidad Un algoritmo eficiente es un algoritmo de complejidad polinomial. Un problema está bien resuelto si se conocen Más detalles Tema 7: Optimización sobre Redes Muchos de los problemas de Investigación Operativa pueden modelizarse y resolverse sobre un grafo: conjunto de
Tema 7: Optimización sobre Redes Muchos de los problemas de Investigación Operativa pueden modelizarse y resolverse sobre un grafo: conjunto de vértices o nodos conectados con arcos y/o aristas. Diseñar Más detalles Un programa entero de dos variables. 15.053 Jueves, 4 de abril. La región factible. Por qué programación entera? Variables 0-1
15.053 Jueves, 4 de abril Un programa entero de dos variables Introducción a la programación entera Modelos de programación entera Handouts: material de clase maximizar 3x + 4y sujeto a 5x + 8y 24 x, y Más detalles Matemáticas I: Hoja 2 Cálculo matricial y sistemas de ecuaciones lineales
Matemáticas I: Hoja 2 Cálculo matricial y sistemas de ecuaciones lineales Ejercicio 1 Escribe las siguientes matrices en forma normal de Hermite: 2 4 3 1 2 3 2 4 3 1 2 3 1. 1 2 3 2. 2 1 1 3. 1 2 3 4. 2 Más detalles Arboles Binarios de Búsqueda
Arboles Binarios de Búsqueda Algoritmos y Estructuras de Datos Departamento de Electricidad y Electrónica (UPV/EHU) Arboles Binarios de Búsqueda p.1/52 Arboles Binarios Arbol binario: árbol ordenado de Más detalles ARBOLES ARBOLES BINARIOS ORDENADOS. REPRESENTACIÓN Y OPERACIONES
ARBOLES ARBOLES BINARIOS ORDENADOS. REPRESENTACIÓN Y OPERACIONES Características ARBOLES - CONCEPTOS Cada elemento del árbol se relaciona con cero o más elementos a quienes llama hijos. Si el árbol no Más detalles Guía de Modelo Relacional y Conversión de Entidad-Relación a Relacional
Guía de Modelo Relacional y Conversión de Entidad-Relación a Relacional Prof. Claudio Gutiérrez, Aux. Mauricio Monsalve Primavera de 2007 1. Problemas conceptuales 1. Qué es una relación? Qué es un esquema Más detalles INDICE GENERAL... 1 INDICE DE FIGURAS... 3
INDICE GENERAL INDICE GENERAL... 1 INDICE DE FIGURAS... 3 1. Introducción y Discusión Bibliográfica... 4 1.1 Discusión Bibliográfica... 4 1.2 Motivación... 5 1.3 Estructura de la tesis... 6 2. Análisis Más detalles Tema 2. Recursividad. Fundamentos de Programación II. Luís Rodríguez Baena (luis.rodriguez@upsam.net)
Fundamentos de Programación II Tema 2. Recursividad Luís Rodríguez Baena (luis.rodriguez@upsam.net) Universidad Pontificia de Salamanca (campus Madrid) Escuela Superior de Ingeniería y Arquitectura Naturaleza Más detalles Matemáticas 2º BTO Aplicadas a las Ciencias Sociales
Matemáticas 2º BTO Aplicadas a las Ciencias Sociales CONVOCATORIA EXTRAORDINARIA DE JUNIO 2014 MÍNIMOS: No son contenidos mínimos los señalados como de ampliación. I. PROBABILIDAD Y ESTADÍSTICA UNIDAD Más detalles 3. Consideremos el puzzle-8 descrito en clase y sea el estado objetivo, como de costumbre,
E.T.S.I. INFORMÁTICA 4º CURSO. INTELIGENCIA ARTIFICIAL. UNIVERSIDAD DE MÁLAGA Dpto. Lenguajes y Ciencias de la Computación RELACIÓN DE PROLEMAS. ÚSQUEDAS CON ÁROL.. Un móvil puede situarse en los nodos Más detalles 5. AJUSTE DE PARÁMETROS DE LA BÚSQUEDA TABÚ
5.Ajuste de parámetros de la búsqueda tabú 5. AJUSTE DE PARÁMETROS DE LA BÚSQUEDA TABÚ El algoritmo de Búsqueda Tabú (TS) utiliza un gran número de parámetros asociados a distintas etapas de la resolución. Más detalles Implementación y análisis de rendimiento de un sistema de planeamiento lineal basado en el modelo MPBH
Implementación y análisis de rendimiento de un sistema de planeamiento lineal basado en el modelo MPBH Tesis para obtener el Título Profesional de Ingeniero de Sistemas Christian Danniel Paz Trillo Miembros Más detalles Fundamentos de Investigación de Operaciones Asignación y Vendedor Viajero
Fundamentos de Investigación de Operaciones y Vendedor Viajero 23 de mayo de 2004 Si bien la resolución del problema de transporte mediante tableau parece ser muy expedita, existen ciertos tipos de problemas Más detalles Tema 10- Representación Jerárquica: Tema 10- Representación Jerárquica: Árboles Binarios
Tema 10- Representación Jerárquica: Árboles Binarios Tema 10- Representación Jerárquica: Árboles Binarios Germán Moltó Escuela Técnica Superior de Ingeniería Informática Universidad Politécnica de Valencia Más detalles Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING
Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 11 de septiembre de 2003 1. Introducción Un LP donde se requiere que todas las variables sean enteras se denomina un problema Más detalles 7. Conclusiones. 7.1 Resultados
7. Conclusiones Una de las preguntas iniciales de este proyecto fue : Cuál es la importancia de resolver problemas NP-Completos?. Puede concluirse que el PAV como problema NP- Completo permite comprobar Más detalles TÉCNICAS DE PLANIFICACIÓN Y CONTROL DE PROYECTOS 1
Técnicas de planificación y control de proyectos Andrés Ramos Universidad Pontificia Comillas http://www.iit.comillas.edu/aramos/ Andres.Ramos@comillas.edu TÉCNICAS DE PLANIFICACIÓN Y CONTROL DE PROYECTOS Más detalles Ingeniería en Informática
Departamento de Informática Universidad Carlos III de Madrid Ingeniería en Informática Aprendizaje Automático Junio 2007 Normas generales del examen El tiempo para realizar el examen es de 3 horas No se Más detalles INDICE. XVII Prólogo a la edición en español. XXI 1. Calculo proporcional 1.1. Argumentos y proporciones lógicas
INDICE Prologo XVII Prólogo a la edición en español XXI 1. Calculo proporcional 1.1. Argumentos y proporciones lógicas 1 1.1.1. Introducción 1.1.2. Algunos argumentos lógicos importantes 2 1.1.3. Proposiciones Más detalles Optimización de consultas Resumen del capítulo 14
Optimización de consultas Resumen del capítulo 14 Libro: Fundamentos de Bases de Datos Silberschatz et al. 5ed. Dr. Víctor J. Sosa Agenda 1. Visión general 2. Estimación de las estadísticas de los resultados Más detalles Razonamiento Espacial con Relaciones Cardinales Basado en Problemas de Satisfacción de Restricciones y Lógicas Modales
UNIVERSIDAD DE MURCIA Departamento de Ingeniería de la Información y las Comunicaciones Tesis Doctoral Razonamiento Espacial con Relaciones Cardinales Basado en Problemas de Satisfacción de Restricciones Más detalles Búsqueda Local. cbea (LSI-FIB-UPC) Inteligencia Artificial Curso 2011/2012 1 / 33
Introducción Búsqueda Local A veces el camino para llegar a la solución no nos importa, buscamos en el espacio de soluciones Queremos la mejor de entre las soluciones posibles alcanzable en un tiempo razonable Más detalles Cómo rastrear objetos distribuidos. Rajmohan Rajaraman. Universidad de Northeastern
Cómo rastrear objetos distribuidos Rajmohan Rajaraman Universidad de Northeastern 1 El problema del rastreo de datos Un esquema de rastreo de datos. o Encontrar una copia (cerca) del objeto solicitado. Más detalles Algoritmos: Diseño de algoritmos por inducción
Algoritmos: Diseño de algoritmos por inducción Alberto Valderruten LFCIA - Departamento de Computación Facultad de Informática Universidad de A Coruña, España www.lfcia.org/alg www.fi.udc.es Contenido Más detalles DEFINICION. Ing. M.Sc. Fulbia Torres Asignatura: Estructuras de Datos Barquisimeto 2006
ARBOLES ESTRUCTURAS DE DATOS 2006 DEFINICION Un árbol (tree) es un conjunto finito de nodos. Es una estructura jerárquica aplicable sobre una colección de elementos u objetos llamados nodos; uno de los Más detalles Búsqueda Heurística para Problemas de Scheduling *
IX Congreso de Ingeniería de Organización Gijón, 8 y 9 de septiembre de 2005 Búsqueda Heurística para Problemas de Scheduling * María Sierra Sánchez 1, Ramiro Varela Arias 2 1 Dpto. de Informática. Campus Más detalles Métodos evolutivos de Optimización. Prof. Cesar de Prada Dpto. Ingeneiria de Sitemas y Automática Universidad de Valladolid
Métodos evolutivos de Optimización Prof. Cesar de Prada Dpto. Ingeneiria de Sitemas y Automática Universidad de Valladolid Indice Introducción Método de Montecarlo Algoritmos genéticos Tabú Search Simulated Más detalles EJERCICIOS RESUELTOS PROGRAMACIÓN III
EJERCICIOS RESUELTOS PROGRAMACIÓN III Curso 2008 2009 Ejercicios resueltos de programación 3 Tema 3. Notación asintótica. Alumna: Alicia Sánchez Centro: UNED-Las Rozas (Madrid) El índice de los ejercicios Más detalles Estructuras de datos: Árboles binarios de
Estructuras de datos: Árboles binarios de búsqueda, Dep. de Computación - Fac. de Informática Universidad de A Coruña Santiago Jorge santiago.jorge@udc.es Árboles binarios de búsqueda, Table of Contents Más detalles ENTORNO PARA LA PLANIFICACION DE LA PRODUCCION DE SISTEMAS DE FABRICACION FLEXIBLES
ENTORNO PARA LA PLANIFICACION DE LA PRODUCCION DE SISTEMAS DE FABRICACION FLEXIBLES Mercedes E. Narciso Farias, Miquel Angel Piera i Eroles Unidad de Ingeniería de Sistemas y Automática. Universidad Autónoma Más detalles Metaheurísticas: una visión global *
Metaheurísticas: una visión global * Belén Melián, José A. Moreno Pérez, J. Marcos Moreno Vega DEIOC. Universidad de La Laguna 38271 La Laguna {mbmelian,jamoreno,jmmoreno}@ull.es Resumen Las metaheurísticas Más detalles Estructuras de Datos Abstractas en Lenguaje Java
Universidad de Santiago de Chile Facultad de Ingeniería Departamento de Ingeniería Industrial Estructuras de Datos Abstractas en Lenguaje Java Listas Enlazadas, Colas, Pilas y Árboles Binarios Creado por Más detalles Técnicas para el Manejo de CSPs no Binarios
Técnicas para el Manejo de CSPs no Binarios Miguel A. Salido Dpto. Ciencias de la Computación e Inteligencia Artificial Escuela Politécnica Superior Universidad de Alicante, Spain {masalido}@dccia.ua.es Más detalles Evaluación de la disponibilidad de los servicios desplegados sobre Volunteer Computing
Evaluación de la disponibilidad de los servicios desplegados sobre Volunteer Computing Antonio Escot Praena Enginyeria Informàtica i Tècnica de Gestió Dirección del TFC Ángel A. Juan, PhD. Eva Vallada Más detalles Combinación de Algoritmos Evolutivos y Técnicas Heurísticas para Problemas de Scheduling
Combinación de Algoritmos Evolutivos y Técnicas Heurísticas para Problemas de Scheduling Ramiro Varela, Javier Blanco, Camino Rodríguez, Jorge Puente y César Alonso Centro de Inteligencia Artificial. Universidad Más detalles 4.3 INTERPRETACIÓN ECONÓMICA DE LA DUALIDAD
4.3 INTERPRETACIÓN ECONÓMICA DE LA DUALIDAD El problema de programación lineal se puede considerar como modelo de asignación de recursos, en el que el objetivo es maximizar los ingresos o las utilidades, Más detalles - ERouting Final Exam - CCNA Exploration: Routing Protocols and Concepts (Versión 4.0)
1 of 20 - ERouting Final Exam - CCNA Exploration: Routing Protocols and Concepts (Versión 4.0) 1 Cuáles son las afirmaciones verdaderas con respecto al encapsulamiento y desencapsulamiento de paquetes Más detalles Operaciones Booleanas y Compuertas Básicas
Álgebra de Boole El álgebra booleana es la teoría matemática que se aplica en la lógica combinatoria. Las variables booleanas son símbolos utilizados para representar magnitudes lógicas y pueden tener Más detalles MODELOS DE PLANIFICACIÓN
MODELOS DE PLANIFICACIÓN Santiago de Compostela, Octubre 2006 1 s jk C max P Jm prmt L max NP Rm tree C j Algoritmos wj U j Uj Calendarios Fm prec w j U j Práctica CONTENIDO. Contents 1 Descripción del Más detalles Algoritmos Genéticos.
Algoritmos Genéticos. Miguel Cárdenas Montes, Antonio Gómez Iglesias Centro de Investigaciones Energéticas Medioambientales y Tecnológicas, Madrid, Spain miguel.cardenas@ciemat.es 15-19 de Octubre de 2011 Más detalles INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA
INTRODUCCIÓN A LA PROGRAMACIÓN MATEMÁTICA Dentro del campo general de la teoría de la optimización, también conocida como programación matemática conviene distinguir diferentes modelos de optimización. Más detalles ÁLGEBRA LINEAL E.T.S. DE INGENIERÍA INFORMÁTICA INGENIERÍA TÉCNICA EN INFORMÁTICA DE GESTIÓN. Apuntes de. para la titulación de
E.T.S. DE INGENIERÍA INFORMÁTICA Apuntes de ÁLGEBRA LINEAL para la titulación de INGENIERÍA TÉCNICA EN INFORMÁTICA DE GESTIÓN Fco. Javier Cobos Gavala Amparo Osuna Lucena Rafael Robles Arias Beatriz Silva Más detalles Aplicación de la inteligencia artificial a la resolución del problema de asignación de estudiantes del departamento de PDI
Aplicación de la inteligencia artificial a la resolución del problema de asignación de estudiantes del departamento de PDI Ricardo Köller Jemio Departamento de Ciencias Exactas e Ingeniería, Universidad Más detalles Tecnólogo Informático- Estructuras de Datos y Algoritmos- 2009
Árboles Ejemplos de estructuras arborescentes: con forma de árbol Regla de Alcance: los objetos visibles en un procedimiento son aquellos declarados en él mismo o en cualquier ancestro de él (cualquier Más detalles Scheduling Problem. Cuándo y dónde debo hacer cada trabajo?
Scheduling Problem Cuándo y dónde debo hacer cada trabajo? Ejemplos de problemas de asignación de recursos Fabricación de varios tipos de productos Asignación de turnos de trabajo Inversión financiera Más detalles árbol como un conjunto de nodos y líneas
ÁRBOLES CAPÍTULO 6 ÁRBOLES Desde el punto de vista conceptual, un árbol es un objeto que comienza con una raíz (root) y se extiende en varias ramificaciones o líneas (edges), cada una de las cuales puede Más detalles Problemas de 2 o Bachillerato (ciencias sociales) Isaac Musat Hervás
Problemas de 2 o Bachillerato ciencias sociales) Isaac Musat Hervás 27 de mayo de 2007 2 Índice General 1 Problemas de Álgebra 5 1.1 Matrices, Exámenes de Ciencias Sociales............ 5 1.2 Sistemas de Más detalles Curso 2012-2013 15/10/12. Inteligencia Artificial (30223) Lección 5. Juegos. Índice. Juegos. Los juegos son una forma de entorno multiagente
Inteligencia Artificial (30223) Lección 5. Juegos Curso 2012-2013 José Ángel Bañares 15/10/2013. Dpto. Informática e Ingeniería de Sistemas. Índice Juegos Decisiones optimas Poda α-β Juegos con información Más detalles Lógica Proposicional IIC2212. IIC2212 Lógica Proposicional 1 / 56
Lógica Proposicional IIC2212 IIC2212 Lógica Proposicional 1 / 56 Inicio de la Lógica Originalmente, la Lógica trataba con argumentos en el lenguaje natural. Ejemplo Es el siguiente argumento válido? Todos Más detalles MATEMÁTICAS II APUNTES DE TEORÍA CURSO ACADÉMICO 2012-13. Carlos Ivorra
MATEMÁTICAS II APUNTES DE TEORÍA CURSO ACADÉMICO 2012-13 Carlos Ivorra Índice 1 Introducción a la optimización 1 2 Programación entera 18 3 Introducción a la programación lineal 24 4 El método símplex Más detalles Tema 12: Teorema de Herbrand
Facultad de Informática Grado en Ingeniería Informática Lógica 1/12 PARTE 3: DEMOSTRACIÓN AUTOMÁTICA Tema 12: Teorema de Herbrand Profesor: Javier Bajo jbajo@fi.upm.es Madrid, España 26/11/2012 Introducción. Más detalles Apuntes de Grafos. 1. Definiciones
Apuntes de Grafos Un grafo es una entidad matemática introducida por Euler en 736 para representar entidades (vértices) que pueden relacionarse libremente entre sí, mediante el concepto de arista Se puede Más detalles Ampliación de Estructuras de Datos
Ampliación de Estructuras de Datos Amalia Duch Barcelona, marzo de 2007 Índice 1. Diccionarios implementados con árboles binarios de búsqueda 1 2. TAD Cola de Prioridad 4 3. Heapsort 8 1. Diccionarios Más detalles UNIVERSIDAD TECNOLÓGICA DE PEREIRA FACULTAD DE INGENIERÍA ELÉCTRICA PROGRAMA DE MAESTRÍA EN INGENIERÍA ELÉCTRICA
UNIVERSIDAD TECNOLÓGICA DE PEREIRA FACULTAD DE INGENIERÍA ELÉCTRICA PROGRAMA DE MAESTRÍA EN INGENIERÍA ELÉCTRICA ALGORITMOS GRASP Y SIMULATED ANNEALING COMO INICIALIZADORES DE BRANCH AND BOUND EN LA SOLUCIÓN Más detalles UNIDAD I INTRODUCCIÓN A LOS CIRCUITOS LÓGICOS 1. ÁLGEBRA DE BOOLE 2. MÉTODO DE REDUCCIÓN DE MAPAS DE KARNAUGH 1-1. R. ESPINOSA R. y P. FUENTES R.
UNIDAD I INTRODUCCIÓN A LOS CIRCUITOS LÓGICOS. ÁLGEBRA DE BOOLE 2. MÉTODO DE REDUCCIÓN DE MAPAS DE KARNAUGH - . INTRODUCCIÓN A LOS CIRCUITOS LÓGICOS. ÁLGEBRA DE BOOLE. ÁLGEBRA DE BOOLE El álgebra de Boole Más detalles Álgebras de Boole. Juan Medina Molina. 25 de noviembre de 2003
Álgebras de Boole Juan Medina Molina 25 de noviembre de 2003 Introducción Abordamos en este tema el estudio de las álgebras de Boole. Este tema tiene una aplicación directa a la electrónica digital ya Más detalles 2017 © DocPlayer.es Política de privacidad | Condiciones del servicio | Feedback

References: Resolución 
 Resolución 
 Resolución 
 Resolución 
 RESOLUCIÓN 
 RESOLUCIÓN 
 Resolución 
 Resolución 
 resolución 
 Resolución 
 resolución 
 Resolución 
 resolución 
 resolución 
 resolución 
 resolución