Revolución IA

La Inteligencia Artificial está llamada a protagonizar la próxima Revolución tecnológica

Inicio Sobre Revolucionia Temas Para saber más Contacto

Clases de algoritmos para búsqueda de soluciones

Fernando P.    06/12/2017

Temas:  Fundamentos

En artículos anteriores hemos descrito la estructura general de los problemas que se pueden resolver usando técnicas de búsqueda de soluciones y hemos visto que el concepto de árbol de búsqueda resulta de gran utilidad para describir estos problemas. Todo esto conforma lo que denominamos como aproximación clásica a los problemas de búsqueda de soluciones.

En este punto, tenemos todos los componentes para resolver problemas de esta clase. Únicamente nos falta implementar algoritmos eficientes que sean capaces de ir construyendo el árbol de búsqueda para nuestro problema, de forma que podamos localizar una secuencia de acciones que nos lleve al estado objetivo y con ello a resolver el problema.

Árbol de búsqueda y solución al problema
Cuando introdujimos el concepto de árbol de búsqueda, proporcionamos un algoritmo general que era capaz de ir construyendo el árbol de búsqueda para cualquier problema que se pueda resolver usando búsqueda de soluciones.

Este algoritmo general es capaz de resolver la cuestión de construir el árbol de búsqueda y encontrar un camino o secuencia de acciones que nos lleven desde el estado inicial del problema al estado objetivo que deseamos.

Lo que no resuelve este algoritmo es la cuestión de optimalidad. Es decir, si un problema tiene varias soluciones de distinto coste, la verdadera solución al problema es aquella de mínimo coste, o solución óptima.

Construir el árbol de búsqueda es una condición necesaria pero no suficiente para resolver uno de estos problemas. Es por ello que existen diversos algoritmos que toman como base el algoritmo general de construcción del árbol de búsqueda y lo extienden para ser capaces de localizar la solución óptima, o al menos una que sea suficientemente buena si el problema es tan complejo que encontrar la solución óptima puede ser inviable.

Tipos de algoritmos para llegar a soluciones óptimas Elección de nodos en algoritmos de búsqueda
Como ya hemos dicho, todos los algoritmos que se usan para búsqueda de soluciones parten del algoritmo general de construcción del árbol de búsqueda que ya vimos en su momento.

Para crear un algoritmo que solucione nuestro problema, tomamos este algoritmo general y lo extendemos para definir con precisión qué nodo es el que se va a explorar en la siguiente iteración del algoritmo.

Diferentes mecanismos para definir qué nodo se explora en cada iteración son los que dan lugar a distintos algoritmos.

Dicho esto, hay dos aproximaciones para definir mecanismos de selección de nodos a explorar.

Por un lado, podemos ceñirnos exclusivamente a la información que tenemos sobre la estructura del problema y por otro lado podemos tratar de obtener información adicional sobre el problema por la vía de hacer suposiciones o de adaptar información que tengamos para problemas similares.

Algoritmos de búsqueda sistemática o ciega
Hablamos de algoritmos que ejecutan una búsqueda sistemática o ciega cuando definimos un mecanismo de selección de nodos a explorar que sólo depende de la información contrastada que tenemos sobre el problema.

Calificamos a estos algoritmos como búsqueda sistemática porque son algoritmos que tienen tendencia a explorar todo el árbol de búsqueda de forma ordenada. El mismo algoritmo general de construcción del árbol de búsqueda hace algo de esto.

Por otro lado, también los calificamos como búsqueda ciega porque no sabemos ni sospechamos a priori qué nos vamos a encontrar al explorar cada nodo y todos los nodos nos parecen iguales.

Esta clase de algoritmos suelen tener capacidad de localizar la solución óptima, pero en problemas grandes su rendimiento es malo, o incluso inaceptable, porque tienen tendencia a construir árboles de búsqueda enormes.

Algoritmos de búsqueda informada o heurística
Esta clase de algoritmos se derivan de algunos algoritmos de búsqueda sistemática a los que se añade información extra que permite tener una estimación del coste en el que incurriremos si exploramos un determinado nodo de la frontera del árbol.

En los algoritmos de búsqueda ciega no podemos calcular el coste de una solución (una secuencia de acciones que nos lleva desde el nodo inicial al nodo objetivo) hasta que no hemos explorado todos los nodos del árbol de búsqueda que corresponden a esa secuencia de acciones.

La idea básica de la búsqueda informada consiste en tratar de estimar ese coste antes de explorar un nuevo nodo de forma que no se exploran nodos que a priori resultan onerosos y podemos centrarnos en explorar nodos que sean prometedores en cuanto a coste reducido.

Hablamos de búsqueda informada en el sentido de que añadimos información adicional al problema para tratar de evitar explorar nodos sobre los que tenemos sospechas de elevado coste. En general, se tratará de información incompleta o sesgada que no nos permite garantizar que vamos a poder realizar una búsqueda ordenada ni a poder localizar la solución óptima y por eso también se califican como algoritmos de búsqueda heurística.

Esta clase de algoritmos pueden llegar a ser muy eficientes en problemas que son complicados de abarcar con búsquedas sistemáticas pero, como hemos mencionado, no vamos a estar en condiciones de garantizar que se puede localizar la solución óptima. En general, localizarán soluciones razonables en problemas que sería difícil resolver de otra forma.

En artículos posteriores se estudiarán con detalle algoritmos de uno y otro tipo de forma que puedan ser implementados para resolver problemas concretos.



Los algoritmos que resuelven problemas usando búsqueda de soluciones derivan en gran medida del algoritmo genérico de construcción del árbol de búsqueda y se distinguen sólo por la estrategia y cantidad de información que usan para decidir qué nodo explorar.



Para saber más:

Libro de Stuart Russell y Peter Norvig que trata todas las técnicas de Inteligencia Artificial. No hace demasiado énfasis en cuestiones conectivistas (redes neuronales artificiales) y contiene abundante material del resto de técnicas. El capítulo 3 está completamente dedicado a problemas que pueden ser solucionados mediante técnicas de búsqueda de soluciones.



 

Inicio Powered by NetBSD
 
HTML5
 
En general, todo el contenido de este sitio web es original, salvo referencias o enlaces a otros sitios web y citas o reproducciones expresamente presentadas como tales.

No está permitida la reproducción ni la copia del contenido de este sitio web sin el permiso expreso de la propiedad del mismo.

Este sitio web no utiliza cookies ni ningún otro mecanismo para almacenar información en los navegadores de los visitantes ni para realizar seguimiento de los mismos.

2017,2018 Revolucionia.net
Sobre Revolucionia
Temas
Para saber más
Contacto