Resolver problemas mediante búsqueda

resolver problemas mediante búsqueda

Resolver problemas mediante búsqueda es una forma inteligente de resolver problemas aplicando ciertas estrategias, ya que dependemos de cual sea nuestro objetivo.

Un agente con distintas opciones inmediatas de valores desconocidos puede decidir que acción tomar, examinando las diferentes secuencias de posibles acciones que le conduzcan a estados de valores conocidos y así poder escoger la mejor secuencia.

Un algoritmo de búsqueda tiene como entrada un problema y devuelve una solución, definida por la secuencia de acciones.

Definir un problema

Antes de explicar los diferentes métodos de búsqueda no informada es necesario conocer cómo se deben definir los problemas que queremos resolver mediante algoritmos de búsqueda.

Un problema puede definirse formalmente por los siguientes componentes:

  • El espacio de estados se define implícitamente por los siguientes elementos:
    • Estado inicial con el cual comienza el agente.
    • Una descripción de las posibles acciones disponibles por el agente, denominada como función sucesor. Dado un estado x, la función sucesor devolvería un conjunto de pares ordenados como {acción, sucesor}, donde cada acción es una de las acciones legales en el estado x y cada sucesor es un estado que puede alcanzarse desde x, aplicando  la correspondiente acción.
  • El test objetivo determina si un estado es objetivo o no, es decir, se comprueba si al alcanzar un estado el agente ha conseguido su objetivo.
  • Una función costo del camino que asigna un costo a cada camino para que se pueda cuantificar y reflejar la medida de rendimiento elegida.

La solución de un problema es un camino desde el estado inicial a un estado definido como objetivo. La calidad de la solución se mide por la función costo del camino (medir el rendimiento de la solución).

La solución óptima o mejor sería la que tiene el costo más pequeño del camino entre todas las soluciones encontradas.

Búsqueda de soluciones

En este apartado vamos a introducir las técnicas de búsqueda que utilizan un árbol de búsqueda explícito generado por el estado inicial y la función sucesor.

La raíz del árbol de búsqueda es el nodo de búsqueda correspondiente al estado inicial. En el caso de que este nodo no sea objetivo (comprobado con el test objetivo) tenemos que considerar otros estados e ir comprobando de nuevo si hemos alcanzado el objetivo. Esto se hace expandiendo el estado actual, es decir, aplicando la función sucesor al estado actual generando nuevos estados.

El estado a expandir depende de la estrategia de búsqueda elegida (en este artículo veremos las no informadas).

Necesitamos también representar la colección de nodos que se han generado pero todavía no se han expandido, esta colección la llamaremos frontera. Cada elemento de la frontera es un nodo hoja, en otras palabras, un nodo que todavía no tiene sucesores y que en algún momento puede expandirse o no.

Medir el rendimiento de la resolución del problema

El algoritmo de búsqueda tiene como resultado una solución o un fallo (no se ha encontrado la solución)

El rendimiento del algoritmo elegido lo podemos evaluar en las siguientes formas:

  • Completitud: garantiza si el algoritmo encuentra una solución en el caso de que esta exista
  • Optimización: garantiza si la estrategia elegida puede encontrar la solución óptima.
  •  Complejidad:
    • Temporal: tiempo que se tarda en encontrar una solución
    • Espacial: cantidad de memoria necesaria para el funcionamiento de la estrategia de búsqueda.

Deja un comentario