cienciasdelacomputacion.com

Complejidad Computacional

La complidad computacional es un area de las Ciencias de la Computacion
que estudia el usos de los recursos para resolver un problema durante el calculo de los algoritmos respectivos.

Los 2 recursos principalmente analizados son:

1. Tiempo
2. Espacio (memoria)

En la actualidad las computadoras resuelven a lo sumo problemas que tienen complejidad Polinomica (Ver Ciencias de la Computacion - Complejidad)
Los problemas que no se resuelven con nuestras computadoras actuales ( no se podrian resolver en un tiempo adecuado), poseen una complejidad del Tipo Factorial o Exponencial

Fuente: Aprender Programacion

Algoritmo primero a lo Ancho

Tipos de Busqueda, Busqueda Heuristica

Tipos de búsqueda según estrategias de control:
ALGORITMO
Disponemos de información segura sobre qué operación aplicar
BUSQUEDA EXHAUSTIVA (A CIEGAS)
Exploración del árbol de búsqueda sistemáticamente pero sin información
BUSQUEDA HEURÍSTICA (INFORMADA)
información sobre el problema (información del dominio) que permite reducir la búsqueda

Del griego “heuriskein” que significa descubrir o encontrar
La heurística es una ayuda para guiar el proceso de búsqueda.

En general, con la utilización de heurísticas no se van a conseguir
siempre resultados óptimos (la mejor solución), pero si se van a conseguir resultados de buena calidad en un tiempo razonable.

Se utilizan en problemas complejos donde aparece el problema de la explosión combinatoria. En este tipo de problemas, los algoritmos de búsqueda exhaustiva tienen costos inaceptablemente altos (sólo son válidos para problemas sencillos).

Usar información “heuristica” para “adivinar” cuál nodo expandir
la heurística aparece bajo la forma de una función de evaluación basada en la información específica para el dominio o contexto relacionado con el problema
el problema de búsqueda se puede considerar como la maximización o minimización de una función.

La función de evaluación nos proporciona una manera de evaluar un nodo “localmente” basado en una estimación del costo de llegar desde el nodo actual al nodo meta.
Problemas con la Heurística
la heurística suele ser poco certera - problema abierto
puede no encontrar la mejor respuesta - superado por algoritmo A*
La heurística es una técnica la cual produce resultados, pero no siempre.

Mucho de lo que hacemos en la vida cotidiana involucra soluciones heurísticas a los problemas. Usualmente trabaja, o usualmente trabaja lo suficientemente bien, y cuando no trabaja, entonces se trata el problema de otra forma.

La palabra heurística, no solo describe los casos donde una solución podría no ser encontrada, sino que describe los casos donde deseamos encontrar la mejor solución.

La heurística podría ayudar a encontrar soluciones que pueden ser buenas, pero talvez no la mejor solución. Obviamente la medida de cuan bueno es y la evaluación de las técnicas heurísticas, es relativa al dominio, y a la tarea específica que la solución del problema será aplicada al dominio.

Como especificar un problema en IA

Para producir una especificación formal de un problema se deben definir:

• espacio de estados válidos;
• estado inicial del problema;
• estado objetivo o final;
• estado de falla
• reglas que se pueden aplicar para pasar de un estado a otro.

Un estado es la representación de un problema en un instante dado. Para definir el espacio de estados no es necesario hacer una enumeración exhaustiva de todos los estado válidos, sino que es posible definirlo de manera más general.
El estado inicial consiste en uno o varios estados en los que puede comenzar el problema.
El estado objetivo consiste en uno o varios estados finales que se consideran solución aceptable.
Las reglas describen las acciones u operadores que posibilitan un pasaje de estados.
Una regla tiene una parte izquierda y una parte 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, es decir, como obtener el estado sucesor.
Por ejemplo, en el problema de jugar al ajedrez:
el espacio de estados son la totalidad de tableros que se puede generar en un juego de ajedrez;
el estado inicial es el tablero de 8 x 8 donde cada celda contiene un símbolo de acuerdo a las piezas situadas;
el objetivo o estado final se define como cualquier posición de tablero en la que el contrario no puede realizar ningún movimiento legal y su rey esté amenazado.
las reglas son los movimientos legales, que pueden describirse mediante una parte patrón para ser contrastado con la posición actual de tablero y otra parte que describe el cambio que debe producirse en el tablero.
dado que escribir exhaustivamente todas las reglas es imposible prácticamente, (en el ejemplo, escribir todas las posiciones

Algoritmo primero en profundidad

El algoritmo primero en profundidad funciona de la manera como lo muestra este esquema:

A continuacion, el algoritmo de busqueda Depth First:

Begin
open := [Start];
closed := [ ];
while open ? [ ] do
begin
remove leftmost state from open, call it X;
if X is a goal then returns SUCCESS
else begin
generate children of X;
put X on closed;
discard children of X if already on open or closed;
put remaining children on left end of open
end
end
return FAIL
end

A continuacion se muestra un arbol, el cual va a ser recorrido hasta encontrar el nodo U

La implementacion del algoritmo seria:

open = [A]; closed = [ ]
open = [B,C,D]; closed = [A]
open = [E,F,C,D]; closed = [B,A]
open = [K,L,F,C,D]; closed = [E,B,A]
open = [S,L,F,C,D]; closed = [K,E,B,A]
open = [L,F,C,D]; closed = [S,K,E,B,A]
open = [T,F,C,D]; closed = [L,S,K,E,B,A]
open = [F,C,D]; closed = [T,L,S,K,E,B,A]
Continua hasta encontrar U, o open = [ ].

Algoritmos de Generacion y Prueba y Breath First

Una mejora al algoritmo es asegurarse de que una solución no es probada más de una vez. Esto es sencillo si todas las soluciones son enumeradas – solo se deben probar en orden.
Si el conjunto de soluciones no se puede enumerar, otra alternativa es generar las soluciones de manera aleatoria, pero mantener una lista o arreglo con todas las soluciones probadas, y antes de probar una nueva.
El problema con esta alternativa es que toma mucho tiempo resolver un problema, la lista de soluciones probadas crece, y se podría estar invirtiendo mucho tiempo verificando si la solución fue probada antes.
Si el conjunto de soluciones posibles es grande – o infinita, lo mejor es generar las soluciones de manera aleatoria y sin verificar. La posibilidad de que una solución fue probada más de una vez es baja, y el consumo de tiempo en verificarlo es alto.

Breath First:

Algoritmo:

Begin
open := [Start];
closed := [ ];
while open ? [ ] do
begin
remove leftmost state from open, call it X;
if X is a goal then returns SUCCESS
else begin
generate children of X;
put X on closed;
discard children of X if already on open or closed;
put remaining children on right end of open
end
end
return FAIL
end

Busqueda Data driven(Conducida por datos)

Búsqueda empieza con los hechos o datos conocidos y un conjunto de movimientos legales o reglas para cambiar de estado.
La búsqueda se realiza aplicando las reglas a los datos o hechos, produciendo nuevos datos o hechos. Este proceso continua hasta generar una ruta que satisfaga la condición del objetivo.

Ddado que el sistema tiene que aprender a realizar una busqueda, esta generalmente se dara a ciegas, es decir no se conoce, por supuesto, donde se encuentra la informacion buscada. Por ende se han desarrollado estrategias de búsqueda a ciegas, como son:

• Generar y Probar
• Búsqueda primero a lo ancho
• Búsqueda primero a lo profundo
• Búsqueda de costo uniforme
• Búsqueda en profundidad limitada
• Búsqueda en profundidad iterativa
• Búsqueda bidireccional

GENERATE-AND-TEST (Generar y probar)

1. Generar una posible solución. (estado o camino)
2. Comprobar para ver si es una solución, mediante comparación con los elementos del conjunto de objetivos aceptables.
3. Si la solución ha sido encontrada salir, de otra manera, retornar al paso 1.

Goal-Driven y Busqueda a lo ancho

Conducida por el objetivo (goal driven – backward chaining)

• Tomar el objetivo que queremos resolver, establecer que reglas o movimientos legales podrían usarse para generar este objetivo y determinar que condiciones deben ser verdaderas para ser usadas.
• Estas condiciones constituyen los nuevos objetivos de la búsqueda y la búsqueda continua hacia atrás hasta encontrar los hechos del problema

BREATH FIRST.- Busqueda a lo ancho. La busqueda se realiza a lo largo del arbol o grafo, recorriendo todos los nodos de una correspondiente fila antes de pasar a la siguiente:

Este es una implementacion en pseudocodigo el cual representa el comportamiento de esta estrategia de busqueda:

Begin
open := [Start];
closed := [ ];
while open ? [ ] do
begin
remove leftmost state from open, call it X;
if X is a goal then returns SUCCESS
else begin
generate children of X;
put X on closed;
discard children of X if already on open or closed;
put remaining children on right end of open
end
end
return FAIL
end

Aplicacion en un arbol, donde el objetivo a encontrar es U
1.    open = [A]; closed = [ ]
2.    open = [B,C,D]; closed = [A]
3.    open = [C,D,E,F]; closed = [B,A]
4.    open = [D,E,F,G,H]; closed = [C,B,A]
5.    open = [E,F,G,H,I,J]; closed = [D,C,B,A]
6.    open = [F,G,H,I,J,K,L]; closed = [E,D,C,B,A]
7.    open = [G,H,I,J,K,L,M] L ya esta en open; closed =[F,E,D,C,B,A]
8.    open = [H,I,J,K,L,M,N]; closed = [G,F,E,D,C,B,A]
9.    Continua hasta encontrar U, o open = [ ].

Estrategias de Busqueda

Tipos de búsqueda según estrategias de control:

• ALGORITMO.-Disponemos de información segura sobre qué operación aplicar
• BUSQUEDA EXHAUSTIVA (A CIEGAS).- Exploración del árbol de búsqueda sistemáticamente pero sin información
• BUSQUEDA HEURÍSTICA (INFORMADA).- información sobre el problema (información del dominio) que permite reducir la búsqueda.

Estrategias de búsqueda a ciegas

• Generar y Probar
• Búsqueda primero a lo ancho
• Búsqueda primero a lo profundo
• Búsqueda de costo uniforme
• Búsqueda en profundidad limitada
• Búsqueda en profundidad iterativa
• Búsqueda bidireccional

Comenzemos con el primer tipo de búsqueda:
GENERATE-AND-TEST

• Generar una posible solución. (estado o camino)
• Comprobar para ver si es una solución, mediante comparación con los elementos del conjunto de objetivos aceptables.
• Si la solución ha sido encontrada salir, de otra manera, retornar al paso 1

Para muestra esta imagen

Estrategias y Algoritmos de Busqueda de Informacion

Existen diferencia de estrategias de búsqueda de información:

• Algoritmo Primero a lo Ancho (BREATH-FIRST)
• Algoritmo Primero en Profundidad (DEPTH-FIRST)
• Búsqueda Heurística:
• Ascenso a Colina
• Recocido Simulado
  • Búsqueda Primero el Mejor (BEST-FIRST)
  • Teorema de Admisibilidad
  • Algoritmo Guiado por Agenda

Las técnicas de solución de problemas en IA, en general, incorporan un proceso de búsqueda.
Todo proceso de búsqueda puede ser visualizado como el recorrido por un árbol en el que cada nodo representa un estado y cada rama representa las relaciones entre los estados cuyos nodos conecta.
En general, las reglas contienen en forma implícita el árbol, y se genera en forma explícita sólo aquellas partes que se decide explorar.
La dirección en la cual se conduce la búsqueda (hacia adelante o hacia atrás).
La estrategia de control, o forma de seleccionar las reglas que pueden ser aplicables. Los principales requerimientos de una buena estrategia de control son: que cause desplazamiento en el espacio de estado; y, que sea sistemático.

La forma de representar cada nodo del proceso de búsqueda (representación del conocimiento).

Muchas veces, tratar el proceso como búsqueda en un grafo en lugar de una búsqueda en un árbol, puede reducir el esfuerzo que se gasta en explorar senderos, esencialmente iguales, varias veces. Sin embargo, los requisitos asociados, son:
Cada vez que se genere un nodo se debe chequear para ver si ha sido generado antes.

Se deben introducir procedimientos especiales para que la búsqueda no quede atrapada en algún lazo.

Existen dos formas de conducer las busquedas:

Conducida por el objetivo (goal driven – backward chaining)

Tomar el objetivo que queremos resolver, establecer que reglas o movimientos legales podrían usarse para generar este objetivo y determinar que condiciones deben ser verdaderas para ser usadas.Estas condiciones constituyen los nuevos objetivos de la búsqueda y la búsqueda continua hacia atrás hasta encontrar los hechos del problema.
Conducida por los datos (data driven – forward chaining)

Búsqueda empieza con los hechos o datos conocidos y un conjunto de movimientos legales o reglas para cambiar de estado.La búsqueda se realiza aplicando las reglas a los datos o hechos, produciendo nuevos datos o hechos. Este proceso continua hasta generar una ruta que satisfaga la condición del objetivo.