INTELIGENCIA ARTIFICIAL

Unidad ll. TÉCNICAS DE BÚSQUEDA.

 

2.1. Solución de problemas con búsqueda.

 

Introducción

 

Hoy en día la Ciencia de la Computación trata cada vez de resolver nuevos problemas que sean difíciles de resolver mediante las técnicas computacionales existentes.  Estos problemas generalmente no tienen solución algorítmica conocida o esta es tan compleja que no tiene una implementación práctica computacional.

 

Objetivos

Objetivo general

Interpretar la información sobre las soluciones de búsqueda y sus tipos.

Objetivos específicos

• Investigar los tipos de problemas que se  resuelven con las técnicas de búsqueda.

• Describir los tipos de búsquedas

• Investigar información sobre los métodos de búsqueda en fuentes confiables

Solución De Problemas Con Búsqueda.

de problemas es fundamental para la mayoría de las aplicaciones de IA.

existen principalmente dos clases de problemas que se pueden resolver mediante procesos computables:

• los que utiliza un algoritmo determinista que garantiza la solución al problema

• las tareas complejas que se resuelven con la búsqueda de una solución

• La solución de problemas requiere dos consideraciones:

• Representación del problema en un espacio organizado.

• La capacidad de probar la existencia del estado objetivo en dicho espacio.

• El espacio de búsqueda, se le conoce como una colección de estados. Cuenta con dos faces.

• La generación del espacio de estados

• La búsqueda del estado deseado en ese espacio.

 

Agentes

• Como actúan para alcanzar la meta

• Secuencia de acciones para alcanzarla

• Agentes para la solución de problemas

• Agente solucionador de problemas

 

Conceptos

 

 Una meta

Conjunto de medios que permiten alcanzarla 

Búsqueda

Procedimiento de exploración para determinar qué es lo que se puede obtener

• ¿Qué son las técnicas de búsqueda?

• serie de esquemas de representación del conocimiento

• mediante algoritmos nos permite resolver ciertos problemas desde un punto de vista de la I.A.

•  

Elementos de la búsqueda

• Conjunto de estados: todas las configuraciones posibles en el dominio

• Estados iniciales: estados desde los que partimos

• Estados finales: las soluciones del problema.

• Operadores: se aplican para pasar de un estado a otro

• Elementos de búsqueda

 

Formulación de metas 

•  Una meta es un conjunto de estados del mundo

•  A través de las acciones, un agente pasa de un estado a otro

 

Acciones

•  Causantes de la transición de un estado a otro

• El agente tiene que determinar qué acciones permiten obtener el estado de la meta

• Elementos de búsqueda

 

Formulación de un Problema

 

• Proceso que consiste en decidir qué acciones y estados habrán de considerarse acciones y estados habrán de considerarse

• ¿Qué condiciones son necesarias?

• ¿Qué sucede si no hay forma de discernir qué camino nos lleva a la meta?

• ¿Qué decisión tomar en tal situación?

 

Búsquedas

En términos generales, cuando un agente tiene ante si diversas opciones cuyo valor tiene ante si diversas opciones cuyo valor ignora, éstas se tienen que evaluar de alguna forma

 

Algoritmo de búsqueda

• Entrada: un problema

• Salida: solución que adopta la forma de una secuencia de acciones

•  

Una vez encontrada una solución, se procede a ejecutar las acciones.

• Agentes que Resuelven Problemas

• Formular: decidir qué acciones y estados Formular: decidir qué acciones y estados  deberán considerarse

• Buscar: proceso para hallar las secuencias de acciones que conduzcan a una meta

• Ejecutar: fase donde se llevan a cabo las  acciones que conducen a la meta.

• Análisis del problema

Luego de definir el problema formalmente, el segundo paso en la resolución del problema es el análisis del mismo. A fin de poder elegir el método más apropiado para resolver un problema particular.

 

Existen varias preguntas a responder acerca del problema:

¿Puede descomponerse el problema en subproblemas más pequeños?

¿Pueden deshacerse pasos inadecuados hacia la solución?

• Recuperables

• No recuperables

• Ignorables

• Análisis del problema

 

¿Es predecible el universo del problema?

 

• Consecuencia cierta

• Consecuencia incierta

 

¿Una solución es buena de manera absoluta o relativa? La solución de un problema puede consistir en encontrar:

• Algún camino

• El mejor camino

• Análisis del problema

 

¿La solución deseada es un estado o la ruta hacia un estado? La solución de un problema puede consistir en encontrar:

• Un estado final 

•  Una ruta hacia un estado final: 

 

¿El conocimiento se necesita para resolver el problema o para restringir la búsqueda de la solución?

• Reconocer la solución

• Acotar la búsqueda

• Solitarios

• Conversacionales

 

Ejemplo:

 

Imagine un agente en la ciudad de Arad, Rumanía, disfrutando de un viaje de vacaciones. Mañana sale un vuelo a Bucarest.

• Formulación del objetivo: estar en Bucarest

• Formulación del problema:

• -estados: varias ciudades

• -acciones: conducir entre las ciudades

• Encontrar solución: secuencia de ciudades, por ejemplo, Arad, Sibiu, Fagaras, Bucarest.

• Búsquedas Árboles

Explorar las diferentes ramas de un  árbol con el de encontrar un camino desde la raíz a una hoja que represente un estado final.

 

TIPOS DE SOLUCIONADORES

 

Búsqueda ciega:

• Se hace crecer el árbol de forma sistemática.

• No se realiza análisis entre el estado obtenido y la solución.

 

Búsqueda heurística:

• El crecimiento del árbol se hace inyectando conocimiento.

• Este conocimiento permite calcular la distancia entre el estado obtenido y el estado final.

• Tipos De Solucionadores

ELEMENTOS DE BUSQUEDA

• Búsqueda ciega

• Búsqueda heurística

• Búsqueda sin información del dominio o ciega

• Búsqueda en amplitud

• Búsqueda en profundidad

• Búsqueda en profundidad progresiva

• Búsqueda bidireccional

 

DEFINICIONES

Búsqueda ciega

• Busca la primer solución sin importar que tan óptima sea

 

Ventajas:

• Tiene menor complejidad espacial que búsqueda en amplitud.

 

Desventajas:

• Se pueden encontrar soluciones que están más alejadas de        la raíz que otras.

• DEFINICIONES

 

Búsqueda heurística

• Las técnicas de búsqueda heurística usan el conocimiento del dominio para adaptar el solucionador y llegar a la solución con mayor rapidez.

 

Definiciones:

• Costo del camino

• Costo para hallar la solución

• Potencia heurística

• Busca soluciones aceptables

• Búsqueda respaldada con información

 

DEFINICIONES

Búsqueda en amplitud

• Se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel.

 

Búsqueda en profundidad

• Una búsqueda en profundidad explora cada camino posible hasta su conclusión antes de intentar otro camino. Esta técnica de búsqueda pertenece a las estrategias de búsqueda no informada

DEFINICIONES

Búsqueda en profundidad progresiva

• En la búsqueda en profundidad siempre se intenta bajar de nivel. En el momento en que no podamos hacerlo subimos a aquel nodo que nos permita seguir bajando de nivel.

 

Búsqueda bidireccional

• Se llevan a la vez dos búsquedas: una descendente desde el nodo inicial y otra ascendente desde el nodo meta.

 

 

2.2 Espacios de estados

 

Conjunto de estados que podrían obtenerse si se aplicaran todos los operadores posibles a todos los estados que se fuesen generando.

Cada estado representa una situación que se debe considerar como candidata a pertenecer a solución del problema.

Los ejemplos más característicos de esta categoría de problemas son los juegos (son universos restringidos fáciles de modelar)

El espacio de estados de un juego es un grafo cuyos nodos representan las configuraciones alcanzables (los estados válidos) y cuyos arcos explicitan las movidas posibles (las transiciones de estado).

 

• Determinísticos

El espacio de estados determinísticos contiene un único estado inicial y seguir la secuencia de estados para la solución.

 Los espacios de estados determinísticos son usados por los sistemas expertos.

 

• No determinísticos

El no determinístico contiene un amplio número de estados iniciales y sigue la secuencia de estados perteneciente al estado inicial del espacio. 

Son usados por sistemas de lógica difusa. si más de una regla aplica a cualquier estado particular del sistema, o si una regla aplica a un estado particular del sistema en más de una manera, entonces el sistema es no determinístico.

 

Conclusión

 

Las estrategias de búsquedas vistas en este reporte de investigación nos dan una idea de cómo los investigadores que están enfocados en la inteligencia artificial proponen diferentes formas de solución para los problemas. Estas técnicas son clásicas de la inteligencia artificial y es por ello que deben ser conocidas por todos aquellos que están relacionados con programación de soluciones por computadora y poder entender el funcionamiento de ellas.

 

 

 

2.3. Métodos de búsqueda.

 

Introducción

 

Los problemas resueltos por medio de la búsqueda entre varias alternativas, se basan en la aplicación  del sentido común humano. Los humanos generalmente consideran un número de  estrategias alternas que las guíen a la solución de problemas. De este modo, se han establecido  diferentes alternativas o cursos de acción que conduzcan a la solución en dependencia de las  características del espacio de estados del problema a resolver.

 

Objetivo general

 

Estudiar los distintos métodos de búsqueda así como su clasificación de cada una de ellas identificar los conceptos y sus aplicaciones en la vida cotidiana.

 

TIPOS DE SOLUCIONADORES

 

Búsqueda ciega:

Se hace crecer el árbol de forma sistemática.

No se realiza análisis entre el estado obtenido y la solución.

 

Búsqueda heurística:

El crecimiento del árbol se hace inyectando conocimiento.

Este conocimiento permite calcular la distancia entre el estado obtenido y el estado final.

Elemento de búsqueda

 

Búsqueda heurística

Las técnicas de búsqueda heurística usan el conocimiento del dominio para adaptar el solucionador y llegar a la solución con mayor rapidez.

 

Definiciones:

Costo del camino

Costo para hallar la solución

Potencia heurística

Busca soluciones aceptables

Búsqueda respaldada con información

Tipos De Solucionadores
 

ELEMENTOS DE BUSQUEDA

Búsqueda ciega

Búsqueda en amplitud

Búsqueda en profundidad

Búsqueda en profundidad progresiva

Búsqueda bidireccional

Búsqueda heurística

Búsqueda sin información del dominio o ciega

Elemento de búsqueda

 

Búsqueda ciega

Busca la primer solución sin importar que tan óptima sea

 

Ventajas:

Tiene menor complejidad espacial que búsqueda en amplitud.

 

Desventajas:

Se pueden encontrar soluciones que están más alejadas de    la raíz que otras.

Métodos de búsqueda

 

2.3.1 BÚSQUEDA EN AMPLITUD O ANCHURA

 

La busqueda en anchura (o búsqueda en amplitud), llamada Breadth First Search en inglés, es un algoritmo usado para recorrer o buscar elementos en una estructura de datos como los árboles y los grafos (aunque nosotros nos centremos ahora mismo en los árboles). Pertenece al grupo de las búsquedas no informadas (sin heurísticas). Su procedimiento consiste en ir visitando todos los nodos de un nivel antes de proceder con el siguiente nivel tal y como mostramos en la siguiente figura (los números en naranja indican el orden de exploración de los nodos):

De modo que lo primero que hará será visitar la raíz, luego los hijos de la raíz, luego los hijos de cada uno de estos hijos y así sucesivamente. ¿Cómo hacemos esto para que funcione, pensaréis? La respuesta es sencilla: usar una cola como estructura de datos auxiliar

Una cola es una estructura FIFO (First In, First Out) en la que sólo disponemos de dos operaciones: insertar al final de la cola y extraer del principio de la cola. Por tanto, el elemento que entra el último será el último en salir. Como hemos elegido Java como lenguaje de programación para esta entrada, disponemos ya de la interfaz Queue<E> y la clase LinkedList<E> que nos van a brindar la funcionalidad de las colas sin programar nada.

La búsqueda primero en amplitud o en anchura es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sucesores del nodo  raíz, después sus sucesores, etc. En general, se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel.

 

Características De Amplitud o Anchura

- Procedimientos de búsqueda nivel a nivel.

- Para cada uno de los nodos de un nivel se aplican todos los posibles operadores.

- No se expande ningún nodo de un nivel antes de haber expandido todos los del nivel anterior.

- Se implementa con una estructura FIFO.

 

Ventajas de la búsqueda en anchura:

Es completo: siempre encuentra la solución si existe.

Es óptimo si el coste de cada rama es constante: en Inteligencia Artificial puede que cada nodo sea un estado de un problema, y que unas ramas tengan un coste diferente a las demás.

Inconvenientes de la búsqueda en anchura

Complejidad exponencial en espacio y tiempo (incluso peor la del espacio que la del tiempo).

 

2.3.2 BÚSQUEDA EN PROFUNDIDAD

 

La busqueda en profundidad, llamada Depth First Search en inglés, es un algoritmo usado para recorrer o buscar elementos en un árbol o un grafo y pertenece al grupo de las búsquedas no informadas (sin heurísticas). Su procedimiento consiste en visitar todos los nodos de forma ordenada pero no uniforme en un camino concreto, dejando caminos sin visitar en su proceso. Una vez llega al final del camino vuelve atrás hasta que encuentra una bifurcación que no ha explorado, y repite el proceso hasta acabar el árbol (esto se conoce como backtracking). En la siguiente figura mostramos el orden de visita, siendo los números en naranja dicho orden:

Una búsqueda primero en profundidad explora cada camino posible hasta su conclusión (meta) antes de intentar otro camino. Esta técnica de búsqueda pertenece a las estrategias de búsqueda no informada, es decir la búsqueda no utiliza más que la información proporcionada por la definición del problema. En cambio existen otros tipos de búsqueda (véase por ejemplo sección 7) en la cual las estrategias saben si un estado no objetivo es más prometedor que otro, a este último se le conoce como búsquedas informadas o búsquedas heurísticas.

 

Características de profundidad

 

- La búsqueda se realiza por una sola rama del árbol   hasta encontrar una solución o hasta que se tome la   decisión de terminar la búsqueda por esa dirección.

      - Terminar la búsqueda por una dirección se debe a no     haber posibles operadores que aplicar sobre el nodo       hoja o por haber alcanzado un nivel de profundidad          muy grande.

      - Si esto ocurre se produce una vuelta atrás            (backtracking) y se sigue por otra rama hasta visitar        todas las ramas del árbol si es necesario.

 

Ventajas de la búsqueda en profundidad:

 

Es completa si no existen ciclos repetidos.

Tiene menor complejidad en espacio que la búsqueda en anchura, porque solo mantenemos en memoria un camino simultáneamente.

Inconvenientes de la búsqueda en profundidad

No es óptima.

Puede no encontrar la solución aunque exista si hay caminos infinitos. Luego no es completa.

Búsqueda En Amplitud

Elementos de Búsqueda ciega

 

Búsqueda en profundidad progresiva

 

En la búsqueda en profundidad siempre se intenta bajar de nivel. En el momento en que no podamos hacerlo subimos a aquel nodo que nos permita seguir bajando de nivel. Para poder hacer esto se utiliza una estructura tipo pila. En el libro de problemas aparecen varios problemas tipo de este algoritmo. La búsqueda en profundidad progresiva consiste en repetir una búsqueda en profundidad, aumentando de uno en uno el límite de profundidad con que se realiza la búsqueda en profundidad anterior.

características

- Se define una profundidad predefinida.
     

- Se desarrolla el árbol realizando una búsqueda en     profundidad hasta el límite definido en el punto       anterior.

 - Si se encuentra la solución à FIN

      - En caso contrario, se establece un nuevo límite y             volvemos al segundo paso.

 

Búsqueda bidireccional

 

Se llevan a la vez dos búsquedas: una descendente desde el nodo inicial y otra ascendente desde el nodo meta. Al menos una de estas dos búsquedas, debe ser en anchura para que el recorrido ascendente y descendente pueda encontrarse en algún momento.

El camino solución es la suma de los caminos hallados por cada búsqueda desde el nodo mencionado hasta el nodo inicial y hasta el nodo meta.

 

- Se llevan a la vez dos búsquedas: una descendente    desde el nodo inicial y otra ascendente desde el nodo          meta.

      - Al menos una de estas dos búsquedas debe ser en           anchura para que el recorrido ascendente y       descendente puedan encontrarse en algún momento.

      - Cuando se llegue a un nodo que ya había sido      explorado con el otro tipo de búsqueda, el algoritmo acaba.

     - El camino solución es la suma de los caminos       hallados por cada búsqueda desde el nodo mencionado         hasta el nodo inicial y hasta el nodo meta.

 

Búsqueda en profundidad limitada (depth-limited search)

 

Búsqueda limitada por profundidad Con esta búsqueda se eliminan las dificultades de la búsqueda preferente por profundidad, al imponer un límite a la profundidad máxima de una ruta. El establecer este límite es difícil, ya que no conocemos mucho sobre el espacio de estados. La búsqueda limitada puede no ser completa ni óptima: un límite de profundidad muy pequeño puede que no contenga la solución, y uno muy grande puede que contenga soluciones no óptimas que son encontradas primero.

 

Ventajas y desventajas

La búsqueda en profundidad iterativa aprovecha ventajas de la búsqueda en anchura y de la búsqueda en profundidad:

El requerimiento limitado de memoria.

La uniformidad al expandir los nodos, que garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna.

 

Búsqueda por profundización iterativa (IDS)

Búsqueda por profundización iterativa Elimina la dificultad de elegir un límite adecuado de profundidad en la búsqueda limitada por profundidad.

Lo anterior lo hace probando todos los límites de profundidad posibles, primero la profundidad 0, luego la 1, luego la 2, etc. En la profundización iterativa se combinan las ventajas de las búsquedas preferente por profundidad y preferente por amplitud.

Es óptima y completa, como la búsqueda preferente por amplitud, pero la memoria que necesita es la de la búsqueda preferente por profundidad.

 

Ventajas y Desventajas

El requerimiento limitado de memoria.

 La uniformidad al expandir los nodos, que garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna.

El inconveniente puede ser la redundancia de que se vuelve a inspeccionar cada nodo ya comprobado con cada nueva iteración.

 

Conclusión

En conclusión podemos decir que la búsqueda en profundidad y la búsqueda en anchura son técnicas para la solución de problemas. La resolución de problemas en IA requiere, normalmente, determinar una secuencia de acciones o decisiones.

Esta secuencia será ejecutada posteriormente por un agente con el fin de alcanzar un objetivo a partir de  una situación inicial dada. Queda más claro que no todos los métodos a utilizar para la resolución de un problema tienen el mismo coste y en consecuencia la misma complejidad. Siendo los métodos de búsqueda informados más idóneos para el tipo de problema expuesto en esta ocasión.

 

 

2.3.3. Grafos O.

2.3.4. Grafos A.

 

Introducción

 

Hoy en día podemos ver muchas cosas que nos pueden parecer de lo mas cotidianas, carreteras, líneas telefónicas, líneas de televisión por cable, el transporte colectivo metro, circuitos eléctricos de nuestras casas, automóviles, y tantas cosas mas; lo que no pensamos frecuentemente es que estos forman parte de algo que en matemáticas se denomina como grafos.

 

¿Que es un grafo?

 

Es un conjunto de puntos (vértices o nodos) unidos por líneas (Aristas o Arcos).

Un grafo consta de dos cosas:

 

 Un conjunto N cuyos elementos se llaman nodos, puntos o vértices.

Un conjunto S de parejas no ordenadas de nodos diferentes, llamadas segmentos, aristas o arcos.

 

Ejemplo

Podemos representar: Red de computadoras, Conexiones de vuelos de una aerolínea, carreteras que unen ciudades, Actividades de un proyecto, circuitos eléctricos, así como la representación de un mapa (GPS)

 

Aplicaciones

 Recorrer cada carretera exactamente una vez y regresar al punto de partida.

Recorrer cada ciudad una vez y regresar a la ciudad de origen y todo al menor costo posible.

Encontrar el camino más corto entre 2 ciudades cualesquiera

 

Grafo 0

 

Este algoritmo, combina las ventajas de los algoritmos primero en profundidad y primero en amplitud. Sigue un sendero a la vez, pero puede cambiarse a otro sendero que parece más prometedor que el que está siguiendo.

En este sentido, puede considerarse que es un algoritmo que realiza su proceso de búsqueda en un grafo de tipo O, ya que todos sus ramales representan una alternativa de solución.

Para su operación, el algoritmo necesita dos listas de nodos y una función heurística que estime los méritos de cada nodo que se genere:

 

ABIERTOS: Es una variable que contiene los nodos que han sido generados.

CERRADOS: Es una variable que contiene los nodos que han sido examinados. Es necesario tener esta información, para que la búsqueda sea en un grafo y no en un árbol.

FUNCIÓN HEURÍSTICA: Permite que el algoritmo busque primero por senderos que son o parecen más prometedores.

 

Ejemplo

 

Grafo A

 

Metodología: Ponderar a la vez lo cerca que estamos del nodo meta y lo lejos que estamos del nodo inicial.

 

Tipo: tentativo.

 

Ventajas: soluciones más cercanas a la raíz.

Inconvenientes: la función de evaluación se complica.​      

Ejemplo

 

Conclusión

 

Los grafos se utilizan para modelar situaciones en las que se relacionan entre sí pares de objetos de una determinada colección. Gráficamente, el modelo consiste en puntos que representan los objetos y líneas que unen dichos puntos.

 

 

2.4. Satisfacción de restricciones.

 

Introducción

 

La programación por restricciones es una metodología software utilizada para la descripción y posterior resolución efectiva de cierto tipo de problemas, típicamente combinatorios y de optimización.

 

Satisfacción de restricciones

La programación de restricciones puede dividirse en dos ramas claramente diferenciadas:

 

la “satisfacción de restricciones” y la “resolución de restricciones”. Ambas comparten la misma terminología, pero sus orígenes y técnicas de resolución son diferentes.

La satisfacción de restricciones trata con problemas que tienen dominios finitos, mientras que la resolución de restricciones está orientada principalmente a problemas sobre dominios infinitos o dominios más complejos.

Los conceptos clave en esta metodología corresponden a los aspectos de:

La modelización del problema, que permite representar un problema mediante un conjunto finito de variables, un dominio de valores finito para cada variable y un conjunto de restricciones que acotan las combinaciones válidas de valores que las variables pueden tomar.

 

Técnicas inferenciales que permiten deducir nueva información sobre el problema a partir de la explícitamente representada. Estas técnicas también permiten acotar y hacer más eficiente el proceso de búsqueda de soluciones.

Técnicas de búsqueda de la solución, apoyadas generalmente por criterios heurísticos, bien dependientes o independientes del dominio.

 

Definición de un Problema de Satisfacción de Restricciones

 

Un problema de satisfacción de restricciones puede ser representado mediante una terna (X;D;C) donde:

X es un conjunto de n variables fx1; : : : ; xng.

² D =< D1; :::;Dn > es un tupla de dominios finitos donde se interpretan las variables X, tal que la i-ésima componente Di es el dominio que contiene los posibles valores que pueden asignarse a la variable xi. La cardinalidad de cada dominio es di = jDij.

² C = fc1; c2; : : : ; cpg es un conjunto finito de restricciones. Cada restricción k- aria ci está definida sobre un conjunto de k variables var(ci) µ X, denominado su ámbito, y restringe los valores que dichas variables pueden simultáneamente tomar. Particularmente, una restricción es binaria cuando relaciona únicamente a dos variables xiyxj , y se suele denotar como cij . Todas las restricciones definidas en un CSP son conjuntivas, de manera que una solución debe de satisfacer a todas ellas.

La instanciación de una variable es un par variable-valor (x; a) que representa la asignación del valor a a la variable x (x = a).

Un valor ai 2 Di es un valor consistente para xi si existe al menos una solución del CSP en la cual xi = ai.

Una solución a un CSP es una asignación (a1; a2; : : : ; an) de valores a todas sus variables, de tal manera que se satisfagan todas las restricciones del CSP.

Un CSP es consistente, si tiene al menos una solución, es decir una tupla consistente.

Dos CSPs son equivalentes si ambos representan el mismo conjunto de soluciones.

Ejemplo: Para el problema de las 4-Reinas, existen solamente dos soluciones, que se detallan a continuación . Asumiendo que las variables fx1; x2; x3; x4g representan las columnas, y sus dominios son las posibles filas f1; 4g donde colocar las reinas, tenemos que: (x1; 3) es una instanciación de la variable x1, y ((x1; 2); (x2; 4), (x3; 1); (x4; 3)) es una solución del CSP, por lo que el CSP es consistente. El valor 3 es un valor consistente para x1, pero el valor 1 no lo es. El dominio mínimo de x2 es f1; 4g.

Una vez modelado el problema como un CSP, los objetivos del CSP consisten en la satisfabilidad del mismo, es decir, obtener una o varias soluciones, sin preferencia alguna, o bien obtener una solución óptima, o al menos una buena solución, en base a una función objetivo previamente definida en términos de algunas o todas las variables. En este caso particular, se trata de un Problema de Satisfacción y Optimización de  Restricciones, o por su acrónimo en inglés, CSOP (Constraint Satisfaction and Optimization Problem).

 

Conclusión

 

El conocimiento de las técnicas CSP permite disponer de un conjunto de técnicas que permiten abordar la resolución de un amplio tipo de problemas. La resolución de problemas se puede llevar acabo en diferentes lenguajes, particularmente C++, Java o Lisp. En el cual CSP permiten la edición de la especificación del problema (definición de las variables, sus dominios y restricciones) e incluyen potentes métodos de inferencia y búsqueda que nos devuelven una, varias, o todas las soluciones al problema.

 

2.5. Teoría de juegos.

 

 

¿Qué es?

 

La teoría de los juegos es una rama de la matemática con aplicaciones a la economía, sociología, biología y psicología, que analiza las interacciones entre individuos que toman decisiones en un marco de incentivos formalizados (juegos).

La teoría de juegos es una herramienta que ayuda a analizar problemas de optimización interactiva.

Estrategia

 

Una estrategia es un plan de acciones completo que se lleva a cabo cuando se juega el juego.

Cuando un jugador tiene en cuenta las reacciones de otros jugadores para realizar su elección, se dice que el jugador tiene una estrategia.

 

Representación de juegos

Están Clasificados en:

Forma normal de un juego

Forma extensiva de un juego

 

Forma normal de un juego

 

La forma normal (o forma estratégica) de un juego es una matriz de pagos, que muestra los jugadores, las estrategias, y las recompensas.

Hay dos tipos de jugadores.

• Uno elige la fila

• Otro la columna.

Cada jugador tiene dos estrategias, que están especificadas por el número de filas y el número de columnas, las cuales son:

• El primer número es la recompensa recibida por el jugador de las filas

• El segundo es la recompensa del jugador de las columnas

 

Forma extensiva de un juego

 

• La representación de juegos en forma extensiva modela juegos con algún orden que se debe considerar.

• Los juegos se presentan como árboles.

• Cada vértice o nodo representa un punto donde el jugador toma decisiones.

• El jugador se especifica por un número situado junto al vértice. Las líneas que parten del vértice representan acciones posibles para el jugador. Las recompensas se especifican en las hojas del árbol.

 

 

Tipos de juegos y ejemplos

 

La teoría clasifica los juegos en muchas categorías que determinan qué métodos particulares se pueden aplicar para resolverlos (y, de hecho, también cómo se define "resolución" en una categoría particular). Las categorías comunes incluyen:

Juegos simétricos y asimétricos

Juegos de suma cero y de suma distinta de cero

Juegos cooperativos

Juegos Simultáneos y secuenciales

Juegos de información perfecta

Juegos de longitud infinita (SuperJuegos)

Juegos simétricos y asimétricos

 

Un juego simétrico es un juego en el que las recompensas por jugar una estrategia en particular dependen sólo de las estrategias que empleen los otros jugadores y no de quien las juegue.

Si las identidades de los jugadores pueden cambiarse sin que cambien las recompensas de las estrategias, entonces el juego es simétrico.

 

Ejemplos

Las representaciones estándar del juego de la gallina, el dilema del prisionero y la caza del ciervo son juegos simétricos.

 

 

 

Juegos de suma cero y de suma distinta de cero

 

En los juegos de suma cero el beneficio total para todos los jugadores del juego, en cada combinación de estrategias, siempre suma cero (en otras palabras, un jugador se beneficia solamente a expensas de otros).

Criterios maximin y minimax

 

Los criterios maximin y minimax establecen que cada jugador debe minimizar su pérdida máxima:

Criterio maximin: el jugador A, elige que su cobro mínimo posible sea el mayor.

Criterio minimax: el jugador B elige que el pago máximo a A sea el menor posible.

 

Equilibrio de Nash.

 

Los equilibrios de las estrategias dominantes están muy bien cuando aparecen en los juegos, pero desafortunadamente, eso no ocurre con frecuencia.

Un par de estrategias es un equilibrio de Nash si la elección del jugador A es óptima, dada elección de B, y la de B es óptima, dada la de A.

Ejemplos

El go, el ajedrez, el póker y el juego del oso son ejemplos de juegos de suma cero, porque se gana exactamente la cantidad que pierde el oponente.

 

Juegos cooperativos

 

Un juego cooperativo se caracteriza por un contrato que puede hacerse cumplir.

La teoría de los juegos cooperativos da justificaciones de contratos plausibles.

La plausibilidad de un contrato está muy relacionada con la estabilidad.

Ejemplos

EL ENREDO

¡QUE NO CAIGA EL BALÓN!

TRANSPORTE DEL BALÓN

 

Juegos Simultáneos y Secuenciales

 

Un subconjunto importante de los juegos secuenciales es el conjunto de los juegos de información perfecta.

 

Un juego es de información perfecta si todos los jugadores conocen los movimientos que han efectuado previamente todos los otros jugadores; así que sólo los juegos secuenciales pueden ser juegos de información perfecta, pues en los juegos simultáneos no todos los jugadores (a menudo ninguno) conocen las acciones del resto.

 

Ejemplos

 

En los juegos de azar

Los conocidos juegos de pares o nones

Piedra, papel o tijera.

 

Juegos de información perfecta

Los juegos simultáneos son juegos en los que los jugadores mueven simultáneamente o en los que éstos desconocen los movimientos anteriores de otros jugadores.

Los juegos secuenciales (o dinámicos) son juegos en los que los jugadores posteriores tienen algún conocimiento de las acciones previas.

 

Ejemplos

El juego del ultimátum

El juego del ciempiés

El ajedrez

El go

 

Juegos de longitud infinita (SuperJuegos)

 

Por razones obvias, los juegos estudiados por los economistas y los juegos del mundo real finalizan generalmente tras un número finito de movimientos.

Los juegos matemáticos puros no tienen estas restricciones y la teoría de conjuntos estudia juegos de infinitos movimientos, donde el ganador no se conoce hasta que todos los movimientos se conozcan.

 

Conclusión

 

La teoría de juegos tiene la característica de ser un área en que la sustancia subyacente es principalmente una categoría de matemáticas aplicadas, pero la mayoría de la investigación fundamental es desempeñada por especialistas en otras áreas.

 

Economía y negocios

 

Los economistas han usado la teoría de juegos para analizar un amplio abanico de problemas económicos, incluyendo subastas, duopolios, oligopolios, la formación de redes sociales, y sistemas de votaciones.

 

 

Biología

 

En biología, la teoría de juegos se emplea para entender muchos problemas diferentes. Se usó por primera vez para explicar la evolución (y estabilidad) de las proporciones de sexos  (mismo número de machos que de hembras).

Informática y lógica

 

La teoría de juegos ha empezado a desempeñar un papel importante en la lógica y la informática. Muchas teorías lógicas se asientan en la semántica de juegos. Además, los investigadores de informática han usado juegos para modelar programas que interactúan entre sí.