Source: http://docplayer.es/798364-Resolucion-de-problemas.html
Timestamp: 2017-04-29 04:31:16+00:00

Document:
Tomás Godoy Torres
1 Inteligencia en Redes de Comunicaciones Resolución de problemas Julio Villena Román El problema de resolver problemas La resolución de problemas es uno de los procesos básicos de razonamiento que la inteligencia artificial trata de abordar El objetivo consiste en lograr que la máquina ayude a un experto humano a encontrar la solución a un determinado problema (de forma más rápida, más exacta, más fiable...) Pero... cómo expresar el problema de forma computacional? cómo puede resolverlo la máquina de forma eficiente? IRC JVR - 2 12 Índice Formalización Estrategias de búsqueda de soluciones Búsquedas sin información del dominio Búsquedas heurísticas Problemas de satisfacción de restricciones Juegos IRC JVR - 3 El problema de resolver problemas La resolución de problemas es una búsqueda en un espacio de estados, siendo: Estado = <Q, R, C> Q : estructura de datos que describen al estado R : reglas u operaciones que describen las transiciones en el espacio de estados C : estrategia de control de tal forma que encontrar la solución consiste en encontrar una secuencia de reglas r 1 r n que conduzcan desde el estado inicial q o al estado final q f IRC JVR - 4 23 Definición formal de un problema Pasos: Definir un espacio (conjunto) de estados Especificar uno o más estados iniciales Especificar uno o más estados finales (meta/objetivo) Definir reglas sobre las acciones disponibles (abstracción del mundo real a un modelo simbólico) El problema se resuelve usando las reglas en combinación con una estrategia de control La estrategia de control establece el orden de aplicación de las reglas y resuelve los conflictos IRC JVR - 5 El problema del viajante de comercio La Coruña Bilbao León Burgos Zaragoza Barcelona Cáceres Badajoz Madrid Sevilla Toledo Murcia Valencia Cádiz IRC JVR - 6 34 Tipos de problemas Problemas de un estado inicial (single-state) q 0 = {Madrid} Problemas de múltiples estados iniciales (multiple-state) q 0 = {Madrid, Barcelona, Sevilla} Problemas de contingencia (contingency) q 0 = {Madrid} pueden fallar los vuelos Problemas de exploración (online) viajar sin mapa IRC JVR - 7 Soporte computacional: Definiciones Un grafo es una estructura de información compuesta de nodos (piezas de información) + arcos (uniones entre ellos) Hojas: nodos sin descendientes (los últimos) Camino: sucesión de nodos siguiendo los arcos Ciclo: camino cerrado (bucle) Grafo dirigido: los arcos indican el sentido de la relación Grafo acíclico: no tiene ciclos Grafo conexo: entre dos nodos siempre hay un camino Un árbol es un grafo dirigido acíclico conexo en el que: Hay un único nodo raíz Cada nodo tiene un único padre Para cada nodo existe un único camino que lo conecta con el nodo raíz Coste de un nodo: coste de llegar al nodo desde la raíz a lo largo del mejor camino IRC JVR - 8 45 Soporte computacional: Árboles Para modelar los problemas de búsqueda se usan árboles, en los que: nodos: estados intermedios arco: aplicación de un operador (movimientos válidos) a un estado IRC JVR - 9 El problema de euros y dólares Situación inicial: $ $ Objetivo: $ $ Estado: serie de monedas Reglas: r 1 : desplazar $ al hueco de la derecha r 2 : desplazar al hueco de la izquierda r 3 : saltar $ a la derecha r 4 : saltar a la izquierda Card(Q) = 27 ( sirve una búsqueda exhaustiva) IRC JVR6 El problema del puzzle Estado: matriz Reglas: r 1 : hueco a la derecha r 2 : hueco a la izquierda r 3 : hueco arriba r 4 : hueco abajo Card(Q) = 9! = ( sirve una búsqueda exhaustiva) IRC JVR - 11 El problema del puzzle Card(Q) = 16! ~ ya no sirve una búsqueda exhaustiva!!! IRC JVR7 Complejidad La resolución de problemas en IA es un problema NP-completo (No-Determinista Polinómico, con crecimiento asintótico) IRC JVR - 13 Estrategias de búsqueda En definitiva, no sólo basta plantear los problemas de una manera formal, sino que hace falta encontrar la forma apropiada de decidir las reglas a aplicar desde el estado inicial para llegar al estado final y el orden en que éstas se aplican: las estrategias de búsqueda IRC JVR8 Algoritmo general de búsqueda A partir del nodo inicial, se expande el nodo i-ésimo, ejecutando todas sus transiciones: Si el nodo destino no existe en el árbol, se añade Si el nodo destino ya existe: expandir el nodo i-ésimo apuntando al nodo existente si se está registrando el mejor camino, comprobar si el nuevo camino es mejor Si el nodo destino es un nodo final, devolver como solución el camino seguido desde el nodo inicial hasta llegar a él IRC JVR - 15 Algoritmo general de búsqueda (2) Q, V: lista de nodos S: nodo inicial 1) Inicializar Q = {S}, V = {S}, coste S =0 2) Si Q está vacía, devolver SIN_SOLUCIÓN 3) Sacar un nodo N de Q 4) Si N es nodo final, devolver N como solución 5) Para todos los descendientes N i de N: - Enlazar N i con N - Si N i no está en V: coste Ni =coste N +coste N Ni añadir N i a Q añadir N i a V - En otro caso: Si coste Ni_anterior >coste N +coste N Ni coste Ni =coste N +coste N Ni añadir N i a Q En otro caso, no hay que hacer nada 6) Volver a 2 IRC JVR9 Estrategias de búsqueda Las estrategias de búsqueda definen el orden para la expansión de nodos (qué N se extrae, dónde se inserta N i ) Cada estrategia hay que evaluarla según: la completitud de la solución encuentra la solución, si ésta existe? la complejidad temporal cuántos nodos se han generado? la complejidad espacial cuántos nodos como máximo se han guardado en memoria? la optimalidad de la solución encuentra la solución de menor coste? Parámetros de evaluación: Factor de ramificación (b), profundidad de la solución (d), máxima profundidad (m) IRC JVR - 17 Tipos de estrategias de búsqueda Estrategias sin información del dominio o búsqueda a ciegas (uninformed strategies) Sólo emplean la información en la definición del problema Fuerza bruta Estrategias con información del dominio o estrategias heurísticas (informed strategies) Emplean información del espacio de búsqueda para evaluar cómo va el proceso La idea es utilizar una función de evaluación (heurístico) de cada nodo (del coste de llegar a él) IRC JVR10 Búsquedas sin información del dominio Búsqueda en anchura breadth-first search Búsqueda en profundidad depth-first search Búsqueda de coste uniforme uniform-cost search Búsqueda en profundidad limitada depth-limited search Búsqueda en profundidad progresiva iterative deepening search IRC JVR - 19 El mundo de los bloques SOAR (a general cognitive architecture for developing systems that exhibit intelligent behavior) IRC JVR11 Búsqueda en anchura (algoritmo) Expandir el nodo más superficial no expandido (FIFO: extraer por el principio de Q e insertar al final) IRC JVR - 21 Búsqueda en anchura (evaluación) Solución completa Complejidad temporal O(b d ): exponencial Complejidad espacial O(b d ): exponencial (guarda todos los nodos en memoria) No es la estrategia óptima (en general) El espacio es el principal problema IRC JVR12 Búsqueda en profundidad (algoritmo) Expandir el nodo más profundo no expandido (LIFO: extraer e insertar por el principio de Q) IRC JVR - 23 Búsqueda en profundidad (evaluación) Solución no completa En espacios con ciclos puede haber bucles infinitos Es necesaria una comprobación de estados repetidos Complejidad temporal O(b m ): enorme si profundidad máxima >> profundidad de la solución Sin embargo, el algoritmo es rápido si el espacio de soluciones es denso Complejidad espacial O(bm): lineal No es la estrategia óptima (en general) IRC JVR13 Búsqueda de coste uniforme (algoritmo) Expandir el nodo con menos coste no expandido (Q: cola con prioridad) IRC JVR - 25 Búsqueda de coste uniforme (evaluación) Solución completa Complejidad temporal: nº de nodos con coste <= coste de la solución óptima Complejidad espacial: nº de nodos con coste <= coste de la solución óptima Estrategia óptima Pesos positivos: algoritmo de Dijkstra Pesos negativos: algoritmo de Bellman-Ford IRC JVR14 Búsqueda en profundidad limitada Expandir el nodo más profundo no expandido, hasta una profundidad L IRC JVR - 27 Búsqueda en profundidad progresiva (algoritmo) FOR L=0 to inf Aplicar búsqueda_en_profundidad_limitada(l) Si el resultado es válido, se devuelve NEXT L IRC JVR 15 Búsqueda en profundidad progresiva (evaluación) Solución completa Complejidad temporal O(b d ): exponencial (similar a otras estrategias) Complejidad espacial O(bd): lineal Estrategia óptima si el coste = 1 Puede modificarse para utilizar búsqueda de coste uniforme IRC JVR - 29 IRC JVR16 Las Torres de Hanoi IRC JVR - 31 Búsquedas heurísticas Se dice de aquel truco o regla empírica que ayuda a encontrar la solución de un problema (pero que no garantiza que se encuentre) IRC JVR17 Búsquedas heurísticas Primero el mejor (best-first) Búsqueda avariciosa (greedy search) Búsqueda A* Método del gradiente (hill-climbing) Simulated annealing IRC JVR - 33 Primero el mejor Se utiliza una función de evaluación (heurística) para cada nodo y se expande el nodo mejor evaluado no expandido (misma idea que en la búsqueda de coste uniforme) Tema complejo y muy abierto a la idea feliz Casos especiales: búsqueda avariciosa (greedy search) búsqueda A* IRC JVR18 Greedy search La función de evaluación estima el coste del nodo-i hasta la meta, con lo que se expande el nodo que parece estar más cerca de la meta (ejemplo: línea recta) Una buena función de evaluación puede mejorar drásticamente la búsqueda PROBLEMA: puede atascarse en bucles infinitos IRC JVR - 35 Búsqueda A* La idea es evitar expandir caminos que ya son muy costosos Función de evaluación: f(n) = g(n) + h(n) g(n): coste sufrido hasta alcanzar n h(n): coste estimado desde n hasta la meta f(n): coste estimado total hasta la meta pasando por n Se demuestra que la búsqueda A* alcanza la solución óptima, siempre que se utilice un heurístico admisible (que no sobreestime el coste real): h(n) <= h*(n) (el coste real) IRC JVR19 Ejemplos de heurísticos Por ejemplo, se podría usar: número de cuadros fuera de su sitio distancia Manhattan (número de cuadros desde el sitio correcto de cada cuadro) IRC JVR - 37 Hill-climbing Trata de ir decidiendo el camino con menor coste hasta la meta Para ello se queda en cada salto con el nodo destino mejor valorado y sigue expandiendo por él PROBLEMA: puede atascarse en máximos locales, según el estado inicial Máximo global Máximo local IRC JVR20 Simulated annealing La idea es escapar de los máximos locales permitiendo movimientos incorrectos, pero reduciendo gradualmente su tamaño y frecuencia Se utiliza como parámetro la temperatura T del proceso Si la temperatura se reduce suficientemente despacio, se alcanza la solución óptima Fue desarrollado en 1953 para modelado de procesos físicos IRC JVR - 39 Problemas de satisfacción de restricciones Constraint satisfaction problem (CSP) Objetivo: descubrir un estado del problema que satisfaga un conjunto de restricciones Los CSPs son problemas especiales en los que: los estados están definidos por los valores asignados a un conjunto de variables el objetivo está definido por restricciones en los valores de las variables IRC JVR21 Ejemplo clásico: 4 reinas Poner cuatro reinas (damas) sin que ninguna pueda atacar a las demás ( sin que haya dos en la misma columna y no estén en diagonal) Variables: Q 1, Q 2, Q 3, Q 4 Dominio: {1,2,3,4} Restricciones: Q i!= Q j Q i - Q j!= i - j Significado: (Q 1, Q 2 ) pueden valer (1,3) (1,4) (2,4) (3,1) (4,1) (4,2) Q Q Q Q IRC JVR - 41 Ejemplo: Sudoku IRC JVR22 Otros ejemplos menos lúdicos Planificación de horarios de clase Configuración de hardware compatible Planificación de rutas Planificación de producción Problemas de asignación de recursos Evaluación de riesgos en inversiones IRC JVR - 43 Búsqueda en CSP (enfoque inicial) El enfoque inicial es abordar una búsqueda normal Estado inicial: variables sin asignar Operadores: asignar valores a variables no asignadas Objetivo: todas las variables asignadas, todas las restricciones cumplidas Estrategia: (por ejemplo) búsqueda en profundidad DESVENTAJAS: Baja eficiencia porque el orden de asignación es irrelevante y no se comprueban las restricciones no cumplidas IRC JVR23 Búsqueda con retroceso (backtracking) Igual que el anterior, empleando búsqueda en profundidad pero: fijando el orden de asignación de variables comprobando violación de restricciones permitiendo sólo sucesores válidos Este es el algoritmo básico sin información del dominio para los CSPs Es capaz de resolver hasta 15-reinas IRC JVR - 45 Comprobación hacia delante (forward checking) Idea: recordar los valores válidos que quedan para las variables no asignadas detener la búsqueda cuando no quedan valores válidos para una variable La comprobación hacia delante evita a priori asignaciones erróneas Es capaz de resolver hasta 30-reinas IRC JVR24 Búsqueda heurística en CSPs Idea: tomar decisiones más inteligentes sobre: qué valor asignar a la siguiente variable qué variable asignar la siguiente El uso de heurísticos inteligentes mejora significativamente el proceso de búsqueda Se puede resolver hasta 1000-reinas... y más de eso? IRC JVR - 47 Juegos Problemas de búsqueda donde interviene al menos un adversario Tus movimientos por sí solos no aseguran la victoria: es necesaria una estrategia de oposición En general, el tiempo disponible para cada movimiento impone soluciones aproximadas (no sirve la fuerza bruta) Dos tipos de juegos: Deterministas: no interviene el azar (4-en-raya, ajedrez, damas) No deterministas: el azar está presente (backgammon, parchís, monopoly ) Por qué gustan tanto en IA? Divertidos Difíciles Fáciles de formalizar y con un número pequeño de acciones (Los juegos son para la IA como la F1 es para la ingeniería del automóvil) IRC JVR25 Estrategia Minimax Consiste en elegir el mejor movimiento para uno mismo (MAX) suponiendo que el adversario (MIN) escogerá el mejor para sí mismo (que también juega a ganar) Pasos: Generar el árbol de juego, alternando movimientos (ply) de MAX y MIN y asignándoles los valores apropiados (MAX>0, MIN<0) Calcular la función de utilidad de cada nodo final, recorriendo recursivamente los nodos hasta el estado inicial Elegir como jugada a realizar aquel primer movimiento que conduce al nodo final con mayor función de utilidad IRC JVR - 49 Las 3 en raya IRC JVR26 Posible árbol de búsqueda (2-ply) f(n)= (nº de filas, columnas o diagonales abiertas para MAX) (nº de filas, columnas o diagonales abiertas para MIN) IRC JVR - 51 Problema de minimax El número de estados del juego es exponencial al número de movimientos (esto es, en la mayoría de juegos, generar el árbol completo es inviable en recursos de memoria) Solución: no examinar todos los estados Generar un árbol parcial (anticipar sólo los N movimientos siguientes) Usar heurísticos: Memoria de partidas anteriores Movimientos preferidos Poda alfa-beta (alpha-beta pruning) Alfa = valor de la mejor jugada hasta el momento para MAX Beta = valor de la mejor jugada hasta el momento para MIN No expandir (podar) los caminos que no proporcionen mejoras sobre el mejor camino hasta el momento IRC JVR 27 Las 4 en Raya IRC JVR - 53 Las Damas IRC JVR28 Juegos con varios jugadores La función de utilidad se convierte en un vector de valores IRC JVR - 55 Juegos con azar Se modelan las probabilidades de la jugada mediante un jugador ficticio (CHANCE) Por tanto, el valor de la función de utilidad es simplemente aproximado IRC JVR29 Juegos con suma no nula Minimax se puede aplicar a juegos con suma cero y en los que el oponente juega a ganar la ganancia o pérdida de MAX se equilibra exactamente con las pérdidas o ganancias de MIN Sin embargo, muchas de las situaciones del mundo real habitualmente tienen suma no nula los participantes pueden beneficiarse o perder al mismo tiempo Ejemplos: ciclismo, las actividades económicas, la guerra En estas situaciones, la moraleja es que resulta mejor maximizar el beneficio conjunto IRC JVR - 57 Paradigma: El dilema del prisionero La policía arresta a dos sospechosos. No hay pruebas suficientes para condenarles, y tras haberles separado, les visita a cada uno y les ofrece el mismo trato: Estrategia dominante: confesión independientemente de lo que decida el otro, puedes reducir tu condena confesando Sin embargo, el resultado no es óptimo Estrategia óptima: colaboración (equilibrio de Nash) Variaciones: La decisión en realidad depende de la matriz de costes Dilema del prisionero iterado IRC JVR Documentos relacionados
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 Búsqueda heurística Prof. Constantino Malagón
Búsqueda heurística Prof. Constantino Malagón Area de Computación e Inteligencia Artificial 1 Búsqueda heurística Los métodos de búsqueda heurística disponen de alguna información sobre la proximidad de Más detalles Resolución de Problemas
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 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 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 Juegos deterministas. Ajedrez, damas, Go, Othello. barquitos
Árboles de juegos Análisis y Diseño de Algoritmos Tipos de juegos Juegos deterministas Juegos de azar Con información perfecta Con información imperfecta Ajedrez, damas, Go, Othello barquitos Backgammon, Más detalles Inteligencia Artificial Búsqueda entre adversarios
Inteligencia Artificial Búsqueda entre adversarios Primavera 27 profesor: Luigi Ceccaroni Juegos En los entornos multiagente (cooperativos o competitivos), cualquier agente tiene que considerar las acciones 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 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 Juegos deterministas. Ajedrez, damas, Go, Othello. barquitos
Búsqueda con adversario: Juegos Fernando Berzal, berzal@acm.org Tipos de juegos Juegos deterministas Juegos de azar Con información perfecta Con información imperfecta Ajedrez, damas, Go, Othello barquitos 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 Tema 5: Problemas de satisfacción de restricciones
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 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 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 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 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 Análisis de algoritmos basados en colonia de hormigas en problemas de camino mínimo
UNIVERSIDAD CARLOS III DE MADRID ESCUELA POLITÉCNICA SUPERIOR INGENIERÍA INFORMÁTICA PROYECTO FIN DE CARRERA Análisis de algoritmos basados en colonia de hormigas en problemas de camino mínimo Jesús Rodríguez 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 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 Juegos. Esquema. Introducción: juegos como búsqueda Decisiones perfectas Decisiones imperfectas Poda α β
Juegos Transparencias IA (F29) M.Marcos, 2002 (Figuras c S.Russell & P.Norvig, 1998) 1 Esquema Introducción: juegos como búsqueda Decisiones perfectas Decisiones imperfectas Poda α β Transparencias IA Más detalles Análisis de los datos
Universidad Complutense de Madrid CURSOS DE FORMACIÓN EN INFORMÁTICA Análisis de los datos Hojas de cálculo Tema 6 Análisis de los datos Una de las capacidades más interesantes de Excel es la actualización 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 Si el comando Solver no aparece en el menú Herramientas, deberá instalar la macro automática Solver como sigue:
El Solver de Excel El Solver se utiliza para determinar el valor máximo o mínimo de una celda modificando otras celdas; por ejemplo, el beneficio máximo que puede generarse modificando los gastos de publicidad. Más detalles Curso: Inteligencia Artificial. Unidad III: Solución de problemas por búsqueda. M. en I.A. Daniel Alejandro García López
Curso: Inteligencia Artificial Unidad III: Solución de problemas por búsqueda M. en I.A. Daniel Alejandro García López 19 de enero de 2009 Resumen La resolución de problemas se describe a menudo como una 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 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 Contenido. Prólogo... Capítulo 1. Algoritmos y estructuras de datos... 1. Introducción... 24
Contenido Prólogo... vii Capítulo 1. Algoritmos y estructuras de datos... 1 Introducción... 2 1.1. Tipos de datos... 2 1.1.1. Tipos primitivos de datos... 3 1.1.2. Tipos de datos compuestos y agregados... 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 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 1. Juegos de suma cero con dos jugadores
Teoría de juegos Jesús López Fidalgo Esta teoría está íntimamente relacionada con la teoría de la decisión. Lo que diferencia una de otra es el rival contra el que se entra en juego. En la teoría de la 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 Problemas indecidibles
Capítulo 7 Problemas indecidibles 71 Codificación de máquinas de Turing Toda MT se puede codificar como una secuencia finita de ceros y unos En esta sección presentaremos una codificación válida para todas 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 En este capitulo se presentan los métodos y algoritmos utilizados para el desarrollo del
33 En este capitulo se presentan los métodos y algoritmos utilizados para el desarrollo del sistema de procesamiento de imágenes para controlar un robot manipulador y se describen en la forma como serán 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 Tipos de conocimiento en resolución n de problemas. Humanos. Ingeniería a del Conocimiento (Primer Parcial) Conocimiento
Tema 1: Introducción n a los Sistemas Basados en el Conocimiento Modelo computacional Origen Conocimiento y Técnicas Heurísticas Definición de SBC Tipos de Conocimiento Experto Ventajas e Inconvenientes Más detalles TEORÍA DE JUEGOS (2da. Parte) M. En C. Eduardo Bustos Farías
TEORÍA DE JUEGOS (2da. Parte) M. En C. Eduardo Bustos Farías 1 TEORIA DE JUEGOS: ANTECEDENTES 1928: Von Newman Desarrolla la Teoría de Juegos. 1944 PUBLICACION DE Theory and Practice of Games and Economical Más detalles Razonamiento. con. Restricciones. Esquema Global. Tutorial CAEPIA 2003. 1. Introducción - Definiciones - Ejemplos
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 Más detalles Algoritmos. Autor: José Ángel Acosta Rodríguez
Autor: 2006 ÍNDICE Página Índice 1 Problema 1. Movimiento de figuras geométricas.2 Problema 2. Conversión decimal a binario....3 Problema 3. Secuencias binarias..4 Problema 4. Conversión a binario a octal... 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 Nombre de la asignatura: Inteligencia Artificial. Créditos: 2-2 - 4. Aportación al perfil
Nombre de la asignatura: Inteligencia Artificial Créditos: 2-2 - 4 Aportación al perfil Diseñar e implementar interfaces hombre- máquina y máquinamáquina para la automatización de sistemas. Identificar 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 Capítulo 2 Silueta. Figura 2.1 Tetera capturada por la cámara con la silueta resaltada
Capítulo 2 Silueta 2.1 Silueta La silueta de un objeto es muy importante porque es lo que nos da las pistas visuales de cómo es que está formado, nos dice dónde están sus límites y ayuda a diferenciar Más detalles CONSEJOS PARA JUGAR AL AJEDREZ
Se supone que al llegar a este documento ya conoces los rudimentos del ajedrez, es decir, a colocar el tablero (cuadro blanco a la derecha, la dama sobre su color ), colocar las fichas, cómo se mueven, Más detalles ESTUDIO DE TÉCNICAS HEURISTICAS PARA JUGAR AL GO
ESCUELA TÉCNICA SUPERIOR DE INGENIEROS INDUSTRIALES Y DE TELECOMUNICACIÓN Titulación: INGENIERO TÉCNICO EN INFORMÁTICA DE GESTIÓN Título del proyecto: ESTUDIO DE TÉCNICAS HEURISTICAS PARA JUGAR AL GO TÍTULO 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 OPTIMIZACIÓN CON MODELOS DE RED EN HOJA DE CÁLCULO
Optimización con Modelos de Red en Hoja de Cálculo OPTIMIZACIÓN CON MODELOS DE RED EN HOJA DE CÁLCULO Bernal García, Juan Jesús juanjesus.bernal@upct.es Martínez María-Dolores, Soledad María soledad.martinez@upct.es 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 APLICACIONES CON SOLVER OPCIONES DE SOLVER
APLICACIONES CON SOLVER Una de las herramientas con que cuenta el Excel es el solver, que sirve para crear modelos al poderse, diseñar, construir y resolver problemas de optimización. Es una poderosa herramienta Más detalles 1 Agencia de viajes: enunciado
1 AGENCIA DE VIAJES: ENUNCIADO 1 1 Agencia de viajes: enunciado Una agencia de viajes mantiene una base de datos con exactamente N clientes y M destinos turísticos. En una situación real, estos valores 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 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 Algoritmos Genéticos Y
Algoritmos Genéticos Y Optimización n Heurística Dr. Adrian Will Grupo de Aplicaciones de Inteligencia Artificial Universidad Nacional de Tucumán awill@herrera.unt.edu.ar Operadores de Mutación El operador Más detalles Modelado de flujo en redes. Jhon Jairo Padilla A., PhD.
Modelado de flujo en redes Jhon Jairo Padilla A., PhD. Conceptos básicos Demanda o volumen de Demanda: Es el tráfico que están requiriendo los usuarios de una red. Para transportar el volumen de demanda 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 Desarrollar y aplicar estrategias para resolver problemas Determinar si un gráfico es lineal dibujando puntos en una situación dada
MANEJO DE DATOS Analizar gráficos o diagramas de situaciones dadas para identificar información específica Recoger datos, dibujar los datos usando escalas apropiadas y demostrar una comprensión de las Más detalles Guías Excel 2007 Matrices Guía 77
MATRICES Las hojas de cálculo poseen prestaciones interesantes la gestión de matrices de tipo matemático. Unas consisten en facilitar los cálculos matriciales y otras están orientadas a cálculos estadísticos. 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 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 ECONOMIA DE LA INFORMACION Y DE LA INCERTIDUMBRE EJERCICIOS (TEORIA DE JUEGOS)
ECONOMIA DE LA INFORMACION Y DE LA INCERTIDUMBRE EJERCICIOS (TEORIA DE JUEGOS) Ejercicio 1. Aplicando el concepto de estrategias estrictamente dominadas al siguiente juego, qué estrategias podemos estar Más detalles Tema 6: Problemas Especiales de Programación Lineal
Tema 6: Problemas Especiales de Programación Lineal Transporte Asignación Transbordo Tienen una estructura especial que permite modelizar situaciones en las que es necesario: Determinar la manera óptima Más detalles Sin embargo, lo que los Profundos ignoran es que uno de los estudiantes pudo escapar y no va a marcharse sin sus compañeros...
La huida de Innsmouth Un juego de Twilight Creations Durante el verano de 1926, una expedición de campo de la universidad de Miskatonic se perdió en una excursión a través de Nueva Inglaterra, yendo a Más detalles TEMA 3. FUNDAMENTOS DE TEORÍA DE JUEGOS PARA EL ANÁLISIS ESTRATÉGICO. 1. Introducción a la teoría de juegos. 5. Limitaciones de la teoría de juegos
TEMA 3. FUNDAMENTOS DE TEORÍA DE JUEGOS PARA EL ANÁLISIS ESTRATÉGICO 1. Introducción a la teoría de juegos 2. Juegos estáticos 3. Juegos dinámicos 4. Juegos repetidos 5. Limitaciones de la teoría de juegos 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 Búsqueda Heurística I
Búsqueda Heurística I Pedro Meseguer IIIA-CSIC Bellaterra, Spain pedro@iiia.csic.es Introducción Temario curso Búsqueda sistemática Búsqueda ciega Búsqueda informada: primero el mejor, A* Búsqueda en memoria Más detalles &$3Ì78/2 $/*25,7026 (92/87,926 $9$1=$'26 3$5$ 763 6.1. INTRODUCCIÓN
&$3Ì78/2 6.1. INTRODUCCIÓN Los primeros avances para solucionar el TSP, por medio de Algoritmos Evolutivos han sido introducidos por Goldberg y Lingle en [68] y Grefenstette en [72]. En éste área muchos Más detalles DEPARTAMENTO DE INGENIERÍA EN SISTEMAS Y COMPUTACIÓN OPCIÓN I
1INSTITUTO TECNOLÓGICO DE CIUDAD MADERO DEPARTAMENTO DE INGENIERÍA EN SISTEMAS Y COMPUTACIÓN OPCIÓN I TESIS: Desarrollo de Algoritmos de Retroceso Aplicados a la solución del Problema del Diseño de la 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 Una heurística para la asignación de máquinas a trabajos fijos
VIII Congreso de Ingeniería de Organización Leganés, 9 y 10 de septiembre de 2004 Una heurística para la asignación de máquinas a trabajos fijos José Manuel García Sánchez, Marcos Calle Suárez, Gabriel Más detalles Inteligencia Artificial Búsqueda entre adversarios
Inteligencia Artificial Búsqueda entre adversarios 1. [Russell & Norvig 6.3] Considera el juego bipersonal siguiente: El diagrama muestra la posición inicial del tablero. A B 1 2 3 4 El jugador A comienza Más detalles Ingeniería Técnica en Informática de Gestión
Departamento de Informática Universidad Carlos III de Madrid Ingeniería Técnica en Informática de Gestión Inteligencia Artificial Febrero 2006. 1 a parte Normas generales del examen El tiempo para realizar Más detalles forma de entrenar a la nuerona en su aprendizaje.
Sistemas expertos e Inteligencia Artificial,Guía5 1 Facultad : Ingeniería Escuela : Computación Asignatura: Sistemas expertos e Inteligencia Artificial Tema: SISTEMAS BASADOS EN CONOCIMIENTO. Objetivo Más detalles CÁLCULO PARA LA INGENIERÍA 1
CÁLCULO PARA LA INGENIERÍA 1 PROBLEMAS RESUELTOS Tema 3 Derivación de funciones de varias variables 3.1 Derivadas y diferenciales de funciones de varias variables! 1. Derivadas parciales de primer orden.! Más detalles Los Hipódromos. Contenido
desarrollar hábiles tácticas, esto es jugar a TurfMaster. La carrera esta indecisa hasta que se cruza la línea de meta. En la última curva, a la entrada de la línea recta final, hay que encontrar la posición Más detalles TEORÍA DE JUEGOS. 1 Definiciónes y Conceptos Básicos. 1.1 Definición: 1.2 Elementos de un juego. 1.3 Representación de un juego.
TEORÍA DE JUEGOS 1 Definiciónes y Conceptos ásicos. 1.1 Definición: La teoría de juegos es una herramienta de análisis económico usada para estudiar problemas caracterizados por la interacción estratégica Más detalles Dualidad y Análisis de Sensibilidad
Universidad de Chile Facultad de Ciencias Físicas y Matemáticas Departamento de Ingeniería Industrial IN34A: Clase Auxiliar Dualidad y Análisis de Sensibilidad Marcel Goic F. 1 1 Esta es una versión bastante Más detalles 1. (2 puntos) En la V Caminata Madrileño Manchega, los participantes caminan de Madrid
Matemática Discreta Segundo de Ingeniería Informática UAM Curso 2006-2007 Solucionario del examen final del 26-1-2007 Nota bene: A continuación exhibimos algunas de las distintas maneras de abordar los Más detalles 1. Sea A una matriz cuadrada n x n, conteniendo la siguiente información en cada fila i. para 1 j k n para k
. Sea A una matriz cuadrada n x n, conteniendo la siguiente información en cada fila i Ai [, j] = 0 para j k n para k i i < j n Construya un algoritmo "Divide y Vencerás" que ordene las filas de la matriz Más detalles Tema 2. Espacios Vectoriales. 2.1. Introducción
UNIVERSIDAD POLITÉCNICA DE CARTAGENA PRUEBAS DE ACCESO A LA UNIVERSIDAD DE LOS MAYORES DE 25 AÑOS CONVOCATORIA 2014 CRITERIOS DE EVALUACIÓN Matemáticas GENERALES: El examen constará de dos opciones (dos Más detalles Alumnos: Familiarizarse con el código y su uso y resolver las cuestiones planteadas utilizando el intérprete de LISP.
Práctica IA- Búsqueda Nº 1 Equipo nº: Alumnos: Semana 8 Dic.2000 Familiarizarse con el código y su uso y resolver las cuestiones planteadas utilizando el intérprete de LISP. Nota: hay que entregar los Más detalles CÓMO APROVECHAR EL JUEGO DE DOMINÓ EN LAS CLASES DE MATEMÁTICA
CÓMO APROVECHAR EL JUEGO DE DOMINÓ EN LAS CLASES DE MATEMÁTICA Traducción Adriana Rabino Original Fran Tapson 2004, ver http://www.cleavebooks.co.uk/trol/trolxe.pdf La idea es utilizar un material en general Más detalles Universidad Carlos III de Madrid Teoría de Juegos Lista de Ejercicios de Juegos Repetidos y Bayesianos
Sesión 1: 1, 2, 3, 4 Sesión 2: 5, 6, 8, 9 Universidad Carlos III de Madrid Teoría de Juegos Lista de Ejercicios de Juegos Repetidos y Bayesianos 1. Considere el siguiente juego en forma normal: Jugadora Más detalles EN INFORMÁTICA DE SISTEMAS
INGENIERÍA TÉCNICA EN INFORMÁTICA DE SISTEMAS Curso Académico 2009/2010 Proyecto Fin de Carrera PLANIFICACIÓN CUALITATIVA DE CAMINOS DE ROBOTS MÓVILES EN ENTORNOS POLIGONALES BASADA EN LA TEORÍA DE MATROIDES 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 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 Tema 3: Juegos bipersonales
Tema 3: Juegos bipersonales Resumen: 3. Juegos bipersonales 3.1. Juegos bipersonales básicos (con información perfecta) 3.2. Juegos bipersonales con elementos de azar 3.3 Juegos bipersonales con información Más detalles Teoría de las decisiones y de los juegos 2007-2008 Grupo 51 Ejercicios - Tema 3 Juegos dinámicos con información completa (0, 2) 2 D (3, 0) 1 B I
Teoría de las decisiones y de los juegos 007-008 rupo 5 Ejercicios - Tema 3 Juegos dinámicos con información completa. Considere el siguiente juego en su forma extensiva. I (0, ) D (3, 0) I (, ) D (, 3) 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 Aprendizaje por refuerzo
Inteligencia Artificial Aprendizaje por refuerzo Ing. Sup. en Informática, 4º Curso académico: 2011/2012 Profesores: Ramón Hermoso y Matteo Vasirani Aprendizaje Resumen: 3. Aprendizaje automático 3.1 Introducción Más detalles Ejemplos de conversión de reales a enteros
Ejemplos de conversión de reales a enteros Con el siguiente programa se pueden apreciar las diferencias entre las cuatro funciones para convertir de reales a enteros: program convertir_real_a_entero print Más detalles DOMINIO Y RANGO DE UNA FUNCIÓN I N D I C E. martilloatomico@gmail.com. Página. Titulo:
Titulo: DOMINIO Y RANGO I N D I C E Página DE UNA FUNCIÓN Año escolar: 4to. Año de Bachillerato Autor: José Luis Albornoz Salazar Ocupación: Ing Civil. Docente Universitario País de residencia: Venezuela Más detalles En cualquier caso, tampoco es demasiado importante el significado de la "B", si es que lo tiene, lo interesante realmente es el algoritmo.
Arboles-B Características Los árboles-b son árboles de búsqueda. La "B" probablemente se debe a que el algoritmo fue desarrollado por "Rudolf Bayer" y "Eduard M. McCreight", que trabajan para la empresa Más detalles Ejemplo: Resolvemos Sin solución. O siempre es positiva o siempre es negativa. Damos un valor cualquiera Siempre + D(f) =
T1 Dominios, Límites, Asíntotas, Derivadas y Representación Gráfica. 1.1 Dominios de funciones: Polinómicas: D( = La X puede tomar cualquier valor entre Ejemplos: D( = Función racional: es el cociente Más detalles Con el fin de obtener los datos, se procede con las siguientes instrucciones:
Capitulo 3. La predicción de beneficios del mercado bursátil Este segundo caso de estudio va más allá en el uso de técnicas de minería de datos. El dominio específico utilizado para ilustrar estos problemas 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 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 INSTRUCCIONES AJEDREZ
INSTRUCCIONES AJEDREZ EL TABLERO El juego se libra por dos jugadores, con un juego de piezas cada uno de ellos, normalmente unas blancas y otras negras, sobre un tablero cuadrado de 64 casillas: 32 de Más detalles Fundamentos de Investigación de Operaciones Investigación de Operaciones 1
Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 1 de agosto de 2003 1. Introducción Cualquier modelo de una situación es una simplificación de la situación real. Por lo tanto, 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