UNIDAD 2. TÉCNICAS DE BÚSQUEDA

2.1. Solución de problemas con búsquedaLa solución 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:

Unidad 2. Técnicas de Búsqueda

2.1. Solución de problemas con búsquedaLa solución 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:

1. Aquéllos en los que se utiliza un algoritmo determinista que garantiza la solución al problema

2. 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.

resolver un problema de IA cuenta con dos fases:

La generación del espacio de estados

La búsqueda del estado deseado en ese espacio

2.2. Espacios de estados.Un espacio de estados es un grafo cuyos nodos corresponden a estados del problema.

Para definir el espacio de estados o espacio de búsqueda (El conjunto de todos los nodos) no es necesario hacer una exhaustiva enumeración de todos los estado válidos, sino que es posible definirlo de manera más general.

La representación espacio estado se caracteriza por: ◦ Estado Inicial ◦ Estado Final

Ajedrez

clasificación

◦ Reglas de Producción (transición de estados u operadores )

• Las reglas de producción describen las acciones u operadores que posibilitan un transito entre estados.

• Podríamos decir que una regla tiene una parte izquierda y una derecha. La parte izquierda determina la aplicabilidad de la regla, es decir, describe los estados a los que puede aplicarse la regla. • La parte derecha describe la operación que se lleva a cabo si se aplica la regla(acción).

Reglas de Producción ◦ Son los operadores o reglas de transición de un estado a otro. patrón de match operación por aplicar

Parte Izquierda Parte Derecha

2.2.1. Determinísticos

El espacio de estados determinísticos contienen 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.Se puede describir a su vez, que un sistema es determinístico si, para un estado dado, al menos aplica una regla a él y de solo una manera.

2.2.2. No determinísticosEl 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.

En otras palabras,  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.

EL ESPACIO DE ESTADO

Para su resolución computacional, el primer paso es buscar una estructura de datos que capture la esencial de ese juego o problema, que refleje con propiedad la distribución de los elementos en un espacio se situaciones o posiciones posible.La combinación del espacio inicial y los operadores forma el espacio de estados o espacio de representación.

OscarPEDRO

AnaHECTOR

Se denomina espacio inicial aquel del que partimos, y que refleja la estructura que subyace en el problema.Desde cualquier estado se pueden aplicar una serie de operadores que modifican el estado actual para llevar al sistema a un nuevo estado.

REPRESENTACIÓNPara aplicar las estrategias de búsqueda a problemas en el espacio de estados se suele trabajar con una representación de la información mediante un grafo.Dentro del espacio de estados en un problema de búsqueda, cada nodo representa un elemento que equivale a una situación valida (nodos y estados son sinónimos)

Es importante recordar que un mismo grafo puede tener diferentes representaciones gráficas

Ejemplo:

Dos representaciones del mismo grafoG = ({a,b,c,d,e,f},{{a,b},{a,e},{a,f}{e,f},

{b,c},{c,d},{e,d},{d,f}})

Tipos de Grafos Si el orden influye en la aristas se habla de

grafos dirigidos:

En este caso a las aristas se les llama arcos y se representan como pares para indicar el orden: V = { a,b,c,d,e} A ={(e,a), (a,b), (b,a), (d,a), (c,d), (d,c),

(b,c),(c,b) }

Si se permite que haya más de una arista se habla de multígrafos:

Cuando las aristas tienen un valor numérico asociado se llama de grafos valorados:

Al valor numérico asociado se le llama coste de la arista

Representación de Grafos

Para representar los grafos a menudo se utiliza la llamada matriz de adyacencia

Se construye imaginando que en las filas y las columnas corresponden a los vértices. Se pone un 0 para indicar que 2 vértices no son adyacentes, y un 1 para indicar que sí lo son:

Para representarla en un ordenador se utilizan matriz de valores lógicos (booleanos). True hay arista, False no hay arista

En el caso de un grafo no dirigido la matriz será simétrica. No ocurre lo mismo para grafos dirigidos:

Se supone que la fila representa el vértice origen, y la columna el vértice destino del arco

En informática a menudo en lugar de la matriz se usa la lista de adyacencia

A cada vértice le corresponde una lista con sus adyacentes:

GLista de Adyacencia de G

TÉCNICAS DE BÚSQUEDA2.3.- Métodos de búsqueda

Los métodos de búsqueda son una serie de esquemas de representación del conocimiento, que mediante diversos algoritmos nos permite resolver ciertos problemas desde el punto de vista de la I.A.

Los elementos que integran los métodos de búsqueda son:

 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.

Solucionador: mecanismo que nos permite  evolucionar de un estado a otro mediante un algoritmo aplicando los siguientes pasos:

1. Elegir el estado a explorar.

2. Establecer un operador que trabaje sobre el estado elegido en el paso 1

3. Comprobar si el resultado obtenido es un estado final (es una solución del problema). Sino ir al paso 1

2.3.1- PRIMERO EN ANCHURA (BREADTH-FIRST)

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: Si existe la solución, la encuentra en la menor profundidad posible.

Desventajas: Explosión combinatoria aparece frecuentemente debido a la alta complejidad

espacial y temporal de esta técnica.

2.3.2- PRIMERO EN PROFUNDIDAD (DEPTH-FIRST)

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: 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 Existe el riesgo de presencia de bucles infinitos.

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.

2.3.3- GRAFOS OEste 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:

1. ABIERTOS - Es una variable que contiene los nodos que han sido generados. La función heurística ha sido aplicada a ellos, pero todavía no han sido examinados, es decir no se han generado sus sucesores. ABIERTOS puede considerarse como una COLA DE PRIORIDADES en la que los elementos con mayor prioridad son los que tienen los valores más prometedores, dados por la función heurística.

2. 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.

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

      Para muchas aplicaciones, es conveniente definir esta función f', como la suma de dos, que se las llamará g y h'. La función g es una medida del costo de llegar desde el nodo inicial al nodo actual. La función h' es una estimación del costo adicional para llegar desde el nodo actual al estado objetivo. Aquí es donde se explota el conocimiento que se dispone sobre el dominio del problema.

     Es decir, la función combinada f' representa una estimación del costo de llegar desde el estado inicial hasta el estado objetivo, siguiendo el sendero que ha generado el nodo actual. Si el nodo actual ha generado más de un sendero, el algoritmo deberá dejar registrado sólo el mejor.

El algoritmo, en la forma que fue formulado, se aplica a grafos. Puede ser simplificado para aplicarse a árboles, si no se preocupa de comprobar si un nuevo nodo está en ABIERTOS o en CERRADOS. Esto aceleraría la generación de nodos y la búsqueda, para casos en que es poco probable que se repitan nodos.

           Usualmente, el costo de ir de un nodo a su sucesor, g, se fija en una constante igual 1, cuando se desea encontrar un sendero a la solución, que involucre el menor número de pasos. Si por el contrario nos interesa encontrar el camino menos costoso y algunos operadores cuestan más que otros, se asume un valor de g, que refleje esos costos. Un valor de g igual a cero significaría que simplemente nos interesa llegar a alguna solución, de cualquier manera.

VERIFICACIÓN DE RESTRICCIONES

QUE SON?

Son una forma de representar una parte del conocimiento que tenemos de un problema. Estas restricciones pueden ser de gran ayuda en la búsqueda ya que restringen el espacio de soluciones y reducen el número que hay que recorrer para encontrar una solución factible.

Ejemplos: colorear mapas crucigramas n-reinas

Junto con las anteriores aproximaciones, se puede enunciar en el planteamiento de un problema una serie de requisitos que deben cumplir las soluciones para que sean viables.

El enunciado de un problema de búsqueda con restricciones tiene tres términos:

Las variables del problema Los dominios de esas variables o conjunto de valores que pueden

asignarse El conjunto de restricciones que deben ser satisfechas

LAS RESTRICCIONES PUEDEN SER:

Monarias o Unarias: cuando constriñen los valores de un salo variable.

Binaria: cuando limitan un par de variables, etc. Absolutas o hard constraints: que realmente determinan la

solución. Preferenciales o soft constraints: que orientan hacia un tipo de

solución pero que admiten tolerancia en su cumplimiento.

En muchos casos las restricciones dan lugar a retrocesos en la búsqueda para encontrar una solución que las satisfaga(backtracking).

Se trata de deshacer el camino andado ya que se ha llegado a una incompatibilidad, e ir rastreando hacia arriba hasta llegar a la variable que no es compatible y asignarle un nuevo valor.

La verificación anticipada puede suponer un ahorro de tiempo ya que consiste en probar la consistencia de algunos valores antes de asignarlo a las variables correspondientes.

TEORÍA DE JUEGOS

La teoría de juegos es un área de la matemática aplicada que utiliza modelos para estudiar interacciones en estructuras formalizadas de incentivos (los llamados «juegos») y llevar a cabo procesos de decisión.

La teoría de juegos es un área de la matemática aplicada que utiliza modelos para estudiar interacciones en estructuras formalizadas de incentivos (los llamados «juegos») y llevar a cabo procesos de decisión.

La teoría de juegos se usa actualmente en muchos campos: biología sociología politologia psicología filosofía ciencias de la computación.

A raíz de juegos como el dilema del prisionero, en los que el egoísmo generalizado perjudica a los jugadores, la teoría de juegos ha atraído también la atención de los investigadores en informática, usándose en inteligencia artificial y cibernética.

Tu confiesas Tu lo niegasEl confiesa Los dos condenados

a 6 añosEl sale libre y tu eres condenado a 10 años

El lo niega El es condenado a 10 años y tu sales libre

Los dos son condenados a 6 mese