⏮ Más apuntes

Resumen IA

Elias Hernandis - 09 Dec 2019

Búsqueda

Búsqueda ciega e informada

Búsqueda genérica en árbol

function búsqueda-en-árbol (problema, estrategia)
;; devuelve solución o fallo
;; lista-abierta contiene los nodos de la frontera del árbol de búsqueda
Inicializar árbol-de-búsqueda con nodo-raíz
Inicializar lista-abierta con nodo-raíz
Iterar
  If (lista-abierta está vacía) then return fallo
  Elegir de lista-abierta, de acuerdo a la estrategia, un nodo a expandir.
  If (nodo satisface test-objetivo)
    then return solución (camino desde el nodo-raíz hasta el nodo actual)
    else eliminar nodo de lista-abierta
      expandir nodo
      añadir nodos hijo a lista-abierta

Búsqueda en grafo o con eliminación de estados repetidos: añadir una lista de cerrados que contiene los nodos ya explorados (= expandidos). No se introducen en la lista de abiertos aquellos nodos que ya estén en la lista de cerrados.

La estrategia determina la ordenación de la lista abierta:

¿Qué queremos?

Coste computacional

Tiempo Memoria Completa? Óptima?
en anchura \(O(b^d)\) \(O(b^d)\) 1 2
en profundidad \(O(b^m)\) \(b\cdot m + 1\) No No
Dijkstra \(O(b^{\lceil C^\ast/\varepsilon\rceil})\) \(O(b^{\lceil C^\ast/\varepsilon\rceil})\) Sí (\(\varepsilon > 0\))
avariciosa \(O(b^m)\) \(O(b^m)\) No No
\(A^\ast\) \(O(b^{\lceil C^\ast/\varepsilon\rceil})\) \(O(b^{\lceil C^\ast/\varepsilon\rceil})\) Sí* Sí*

Búsqueda entre adversarios

Clasificación de problemas de búsqueda (= juegos)

Minimax

Lógica de predicados

Formalización:

Hay que acordarse de:

Ejercicios

Hoja 2, 2018: ejercicio 2

  1. Dos nodos son hermanos si, siendo distintos, tienen el mismo padre.

    \[\forall x,y [(\lnot I(x,y) \land I(padreDe(x), padreDe(y))) \iff H(x, y)]\]

  2. Un camino entre dos nodos es una secuencia de uno o varios enlaces entre dichos nodos.

    \[\forall x,y,c [C(c, x, y) \iff (I(c, enlace(x,y)) \lor \exists z,m,n (\lnot I(m,n) \land C(m, x, z) \land C(n, z, y)]\]

Parcial 1, 2014-2015: ejercicio 3

  1. Ejemplo
  2. Se puede diseñar una máquina de Turing para computar la solución de cualquier problema que pueda ser resuelto mediante la aplicación de un algoritmo sobre unos datos de entrada.
  3. Una máquina de Turing universal puede simular la acción de cualquier máquina de Turing sobre los datos almacenados en su cinta

    \[\forall u [Universal(u) \implies \forall t, d (comp(t, d) = comp(u, descr(t_2, d))]\]

Incertidumbre

Problema: dado un conjunto de pares (atributos, clase) donde atributos es un vector, elaborar un modelo que permita asignar una clase de entre un conjunto de clases a otros vectores de atributos.

Definiciones:

Modelos:

Un modelo de predicción nos asigna una clase a un vector de atributos dado en base a los datos (pares (atributos, clase)) de los que partimos.

Nota: si tenemos clases uniformes, es decir, si \(P(\text{clase}_i) = P(\text{clase}_j)\) para toda clase de nuestro problema, entonces MAP y ML predicen siempre la misma clase (no necesariamente con la misma probabilidad).

Aprendizaje automático

Construir de manera automática modelos para clasificación.

Dado un conjunto de entrenamiento formado por pares (atributos, clase) donde atributos es un vector, generar un modelo que permita asignar una clase de entre un conjunto de clase a otros vectores de atributos.

Árboles de decisión

Dos algoritmos muy parecidos:

k-NN = k vecinos más próximos


  1. Búsqueda en anchura solo es completa y óptima si el coste es una función no decreciente de la profundidad.

  2. Búsqueda en anchura solo es completa y óptima si el coste es una función no decreciente de la profundidad.