CAPITULO 3: SEGUNDA PARTE-ARITMETICA

 ARITMETICA 

 Definicion de la sucesión de Fibonacci

 

Leonardo de Pisa, más conocido como Fibonacci, construyó por primera vez la sucesión que lleva su nombre: 

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765..., 

Cada término a partir del tercero, se obtiene sumando los dos anteriores.

El cociente entre dos términos consecutivos de la sucesión de Fibonacci se aproxima al número de oro (f = 1,618...).

Los números consecutivos de Fibonacci son primos entre si.

Definimos el codigo que nos servirá para mostrarle como funciona la sucesión de Fobonacci 

Muestra como como se consulta en prolog la suceción.

Bibliografia:

APUNTES DE PROLOG

Edgar Altamirano Carmona    

Universisda Autónoma De Guerrero, 2014

UNIDAD 3: LISTAS, OPERADORES Y ARITMETICA

LISTAS

 

Las listas son otro recurso sintáctico para representar objetos estructurados. Una lista es una secuencia ordenada de términos (que pueden, a su vez, ser listas). Por ejemplo, [A1, A2, A3] es una lista de variables, y [a1, a2, a3] una lista de constantes. Obsérvese que una función se define siempre con un grado asociado, pero una lista puede tener cualquier número de elementos. La lista puede ser vacía: []. Si no es vacía, se puede considerar formada por una cabeza (primer o primeros elementos de la lista) y una cola (lista formada por el resto de los elementos) unidas por la función de construcción de listas, «cons» . Así, la lista del caso anterior puede escribirse de las siguientes maneras:

 

 

    [a1, a2, a3] = cons(a1, [a2, a3]) = cons(a1, cons(a2,[a3]))  

                  = cons(a1, cons(a2, cons(a3, []))) 

 

 

Un ejemplo de agregar y remover en una lista es el 

siguente:

 

 

 

 

 

Codig de una lista, nos sirve para agregar y remover.

Muestro una consulta para agregar  en este caso "z".

 Se muestra que se remueve la "z" en este ejemplo.

En este caso se elimina la "z" y "L"

PRACTICANDO CON PROLOG UNIDAD DOS: TERCERA PARTE

UNIDAD DOS: SINTEXIS Y SIGNIFICADO DE LOS PROGRAMAS

El problema del mono y la banana.

El problema del mono y la banana se utiliza como un ejemplo sencillo de solución de problemas. El siguiente programa en Prolog mostrará como se pueden utilizar los mecanismos de 'matching' y 'backtracking'. Utilizaremos la siguiente versión del problema: Existe un mono en la puerta de un cuarto; enmedio del cuarto cuelga una banana del techo; el mono está hambriento y desea capturar la banana, pero no puede alcanzarla desde el piso. En la ventana del cuarto hay una caja que el mono puede usar.

El mono puede realizar solamente las siguientes acciones: caminar sobre el piso, subir a
la caja, empujar la caja (si el mono está junto a la caja), y, agarrar la banana (si el mono
está sobre la caja y bajo la banana).
¿Cómo puede el mono llegar a capturar la banana?

Análisis del problema.
Una tarea importante en programación es encontrar una representación del problema en
términos del lenguaje de programación utilizado.
En este caso podemos pensar del 'mundo del mono' en términos de 'estados' que
cambian con el tiempo. El estado actual se determina por la posición actual de los
objetos.

Por ejemplo, el estado inicial del mundo está determinado por:
1). El mono está en la puerta.
2). El mono está sobre el piso.
3). La caja está en la ventana.
4). El mono no tiene la banana.
Es conveniente combinar todas estas piezas de información en un solo
objeto estructurado. Escogeremos la palabra 'estado' como el functor que
retendrá los cuatro componentes anteriores :

El estado final es una situación en que el mono tiene la banana, es decir, cualquier
estado en cuyo componente último sea :
estado( _, _, _, silatiene)
Las transiciones permitidas que cambian el mundo de un estado a otro son
las siguientes :
(1). agarrar la banana.
(2). subir a la caja.
(3). empujar la caja.
(4). caminar en el cuarto.
No todas las transiciones son posibles en cada estado posible del mundo del mono. Por
ejemplo, la transición 'agarrar la banana' es solamente posible si el mono está sobre la
caja y bajo la banana y si no tiene todavía la banana. Estas transiciones ó reglas se
pueden formalizar en Prolog como una relación de tres componentes que llamaremos
'mover':

                   mover( Estado1, M, Estado2)

Los tres argumentos de la relación especifican un movimiento tal que:
Estado1 ----- M -----> Estado2
'Estado1' es el estado antes del movimiento 'M'; 'M' es el movimiento realizado, y 'Estado2' es el estado del mundo del mono después de haberse realizado el movimiento 'M'.
El movimiento 'agarrar' es una precondición necesaria antes de la meta final y lo podemos definir con la cláusula:
mover( estado( enmedio, sobrelacaja, enmedio, nolatiene),
agarrarlabanana,
estado( enmedio, sobrelacaja, enmedio, silatiene)).
Esta cláusula nos dice que después de ejecutarse, el mono tendrá la banana y permanece sobre la caja y enmedio del cuarto.
De una forma similar a la anterior podemos expresar el hecho de que el mono estando sobre el piso puede caminar de la posición P1 a cualquier posición P2. El mono puede realizar esta acción sin importar la posición de la caja y si tiene ó no la banana:

                        % caminar de P1 a P2

mover( estado( P1, sobreelpiso, B, H),
caminar( P1, P2 ),
estado( P2, sobreelpiso, B, H)).
Esta cláusula nos dice entre otras cosas:
-El movimiento realizado fue: 'caminar de una posición P1 a otra P2'.
-El mono está sobre el piso antes y después del movimiento.
-La caja está en algún lugar B y permanece en el mismo lugar.
-El estado de tiene ó no tiene la banana permanece igual después del movimiento.
La cláusula especifica un conjunto de movimientos posibles porque es aplicable a cualquier situación que se apareje ('matching') al estado antes del movimiento.
Hasta aquí hemos definido los movimientos 'agarrar la banana' (1) y 'caminar de P1 a P2' (4). Los otros dos tipos de movimientos 'empujar la caja' (3) y 'subir a la caja' (2) se pueden definir de manera similar.
Finalmente, la pregunta que nuestro programa debe contestar es: ¿ Puede el mono, desde algún estado inicial 'S', capturar la banana ?
Esta pregunta se puede formular con el predicado:

                         puedetener(S)

donde el argumento 'S' es un estado del mundo del mono. El programa para satisfacer el predicado 'puedetener' lo podemos basar en dos observaciones:
(1). Para cualquier estado 'S' en el cual el mono ya tiene la banana, el predicado 'puedetener' debe ser cierto:
puedetener( estado( _, _, _, silatiene)) :- !.
(2). De otro modo, el mono puede tener la banana desde un estado S1 si existe algún movimiento M del estado S1 a otro estado S2, tal que el mono pueda tener la banana en el estado S2 :
puedetener( S1) :-
mover( S1, M, S2),
puedetener(S2).

Se muestra el codigo del problema del mono y la banana.

Se muestran las consultas realizadas

Bibliografia:

APUNTES DE PROLOG

Edgar Altamirano Carmona    

Universisda Autónoma De Guerrero, 2014

PRACTICANDO CON PROLOG UNIDAD DOS: SEGUNDA PARTE

UNIDAD DOS: SINTEXIS Y SIGNIFICADO DE LOS PROGRAMAS

Significado procedural

El significado procedural especifica el cómo contesta Prolog a las preguntas. Responder

a una pregunta significa tratar de satisfacer una lista de metas. Estas pueden satisfacerse

si las variables que existen en las metas pueden instanciarse de tal modo que las metas se

sigan lógicamente del programa. Así el significado procedural de Prolog es un

procedimiento para ejecutar una lista de metas con respecto a un programa dado.

Ejecutar las metas significa tratar de satisfacerlas.

Llamemos a este procedimiento 'ejecuta':

las entradas y salidas a este procedimiento son :

entrada : un programa y una lista de metas.

salida : un indicador de éxito / falla y una instanciación particular de las variables.

el significado de las dos salidas es como sigue :

(1). El indicador de éxito/falla es 'yes' si las metas son satisfactibles y 'no' si ocurre lo contrario. Decimos que 'yes' señala una terminación exitosa y 'no' una falla.

(2). Una instanciación de las variables se produce solamente en el caso de una terminación exitosa; en el caso de una falla no hay instanciación.

Un ejemplo es el siguiente:

Es el codigo que se utiliza para mostrar el significado procedual

Muestra consultas las descripciones verdaderas y falsas.

Bibliografia:

APUNTES DE PROLOG

Edgar Altamirano Carmona    

Universisda Autónoma De Guerrero, 2014

PRACTICANDO CON PROLOG UNIDAD DOS

SINTEXIS Y SIGNIFICADO DE LOS PROGRAMAS

Tipos básicos de datos.

Prolog reconoce el tipo de un objeto por su sintaxis (en Prolog no es necesario declarar el tipo de un dato) :

Átomos.
Se pueden construir de tres formas:
1). Cadenas de letras, dígitos y el símbolo de subrayado (_), pero comenzando siempre con una letra minúscula.
Ejemplos :
ana nil x25 x_25 x_25 AB x_ x_y a_b_c
2). Cadenas de caracteres especiales.
Ejemplos: <---> ===> ... .:. ::=
3). Cadenas de caracteres encerrados en comillas simples (').
Ejemplos: 'Tomas' 'Juan_Hernandez' 'Jose Lopez Lopez'

Números.
Pueden ser enteros ó reales :
Ejemplos: 1 -97 3.141592 -1.2 0

Variables.
Son Cadenas de letras, dígitos y el símbolo de subrayado ( _ ) que comienzan siempre con una letra mayúscula ó un símbolo de subrayado.
Ejemplos: X Nombre_1 _x23 _55

Estructuras.
Son objetos que tienen varios componentes.
Ejemplo: fecha( 20, agosto, 1992)
fecha recibe el nombre de functor; En este caso todos sus componentes son constantes pero pueden ser variables ó incluso estructuras. Aunque las estructuras tienen varios componentes, en los programas Prolog se tratan como objetos únicos. Es decir, en Prolog, todos los objetos son términos.
Ejemplo: agosto y fecha( 20, agosto, 1992)

Matching (empatamiento).

La operación más importante sobre los términos es la de matching (empatamiento).
Dados dos términos cualesquiera decimos que "empatan" si se cumple lo siguiente :
(1). Son idénticos; ó,
(2). Las variables en ambos términos pueden instanciarse a objetos de tal modo que después
de la sustitución de las variables por estos objetos los términos puedan ser idénticos.

Significado declarativo.

Los programas Prolog pueden entenderse de dos maneras: declarativa y proceduralmente.

Significado Declarativo.

El significado declarativo de los programas determina si una meta dada es cierta, y si es el caso, para qué valores de las variables es cierta.
Para definir de manera más precisa el significado declarativo, necesitamos introducir antes el concepto de "instancia" de una cláusula.
Una instancia de una cláusula C es la cláusula C con cada una de sus variables sustituidas por algún término. Una "variante" de una cláusula C es una instancia de la cláusula C tal que cada variable se sustituye por otra variable.

El significado declarativo de los programas determina si una meta dada es cierta, y si es el caso, para qué valores de las variables es cierta.
Para definir de manera más precisa el significado declarativo, necesitamos introducir antes el concepto de "instancia" de una cláusula.
Una instancia de una cláusula C es la cláusula C con cada una de sus variables sustituidas por algún término. Una "variante" de una cláusula C es una instancia de la cláusula C tal que cada variable se sustituye por otra variable.

Ahora algo de practica...

Este programa muestra lo que es el significado declarativo.

Con las siguientes que se hacen preguntas se pretende observar  las clausulas y verificación del el uso de la ",".

Una coma entre metas denota una conjunción de metas: todas tienen que ser ciertas.

 Prolog acepta además la disyunción de metas : cualquiera de las metas en una disyunción tiene que ser verdadera. La disyunción se indica con el símbolo de punto y coma (;).

BIBLIOGRAFIA

APUNTES DE PROLOG

Edgar Altamirano Carmona    

Universisda Autónoma De Guerrero, 2014

"PRACTICANDO CON PROLOG UNIDAD UNO"

"Mi árbol familiar"

Para comenzar a entender prolog en esta practica comenzaré explicando mi árbol genealógico que está conformado de la siguiente manera: Donde progenitor, abuelo, abuela, tío, tía, hermano, hermana, hombre y mujer son relaciones; Los nombres que se mencionan son argumentos.

Su servidora:
Estrella

Abuelos paternos:

-Oralia

-Julian

Abuelos maternos:

-Rosa

-Crisoforo

Mis padres:

-Silvia

-Jose

Hermanos paternos

-Jhonatan

-María

-Yari

-Celia

Hermanos maternos

-Carlos

-Yolver

-Blanca

-Yaris

-Alma

Tia:

Cristina

Nota: En el caso de mis hermanos paternos y mantenernos, tengo dos hermanas una que se llama Yari hija de mi Papá y otra que se llama Yaris hija de mi mamá, lo aclaro para al momento de hacer las pruebas no piensen que es un error.

Comienza la practica...

Muestro mi definición de relaciones en mi árbol familiar; En este caso muestra si es hombre o mujer.

Se emplea la relación de progenitor, abuelo, abuela, hermano, hermana, tío y tia.

Para mi primera consulta pido que se muestren los progenitores de cada uno:
?-progenitor(X,Y),progenitor(X,Y).

Las siguientes consultas están enumeradas del 1 al 15, preguntando es este apartado y en la imagen se muestra el resultado.

1.-Mostrar mis padres.

 ?- progenitor(X,estrella).

2.-Pregunto si Yaris es mi hermana

  ?-hermana(yaris,estrella).

3.-Pregunto si Silvia es mi hermano, como lo pueden observar el resultado es falso porque Silvia en realidad es mi mamá.

?- hermano(silvia,estrella).

4.-Para mostrar mis hermanos lo hice de esta manera.

?- hermano(Y,estrella).

5.-Pido que se muestren mis abuelos

?- abuelo(X,estrella).

6.-Pido que se muestren mis abuelas

?- abuela(X,estrella).

7.-Pregunto si mi tía es cristina
?- tia(cristina,estrella)

8.-Muestra quienes son hijas de crisoforo mi abuelo.
?- progenitor(crisoforo,Y).

9.-Pregunto quienes son los padres de mi mamá.
?- progenitor(Y,silvia).

10.-Pregunto quienes son los padres de mi papá.
?- progenitor(Y,jose).

11.-Me muestra que Silvia (mi mamá) es progenitora de los que aparecen en el la consulta 11.
?- progenitor(silvia,Y).

12.-Me muestra que Jose (mi papá) es progenitor de los que aparecen en el la consulta 12.
?- progenitor(Jose,Y).

13.-En este caso pregunto de quién soy progenitor, el resultado es falso porque responde a que no tengo descendencia.
?- progenitor(estrella,Y).

14.-Pregunto si Yolver es mi hermano
?-hermano(yolver,estrella).

15.-Pregunto si julian es mi tío, como verán es falso porque julian es mi abuelo.



Esto es todo sobre prolog unidad uno, espero les sirva la practica que eh hecho con mi árbol familiar.
Seguiremos trabajando en mas ejemplos, así que esperen la siguiente unidad.

PROLOG

PROLOG

Prolog es un lenguaje de programación creado para representar y utilizar el conocimiento que se tiene sobre un determinado dominio. Más exactamente, el dominio es un conjunto de objetos y el conocimiento se representa por un conjunto de relaciones que describen las propiedades de los objetos y sus interrelaciones. Un conjunto de reglas que describa estas propiedades y estas relaciones es un programa PROLOG. Una definición más accesible para el usuario común sería:

Prolog es un lenguaje de programación que es usado para resolver problemas que envuelven objetos y las relaciones entre ellos. Permite ejecutar estatutos que no son otra cosa que oraciones de un lenguaje lógico elemental particular de cláusulas. Prolog por su naturaleza muestra una habilidad para describir gramáticas, en particular gramáticas libres de contexto.

Un programa Prolog está formado por una secuencia de enunciados (cláusulas): hechos, reglas y variables.

Dejo esto link para que comprendan màs sobre prolog contiene ejemplos que espero les sirva...

http://gpd.sip.ucm.es/jaime/pl/prolog.pdf

ABECEDARIO

LA MANERA DE ENSEÑAR EL ABECEDARIO AHORA

Heuristica y el problema del viajero

Heurística

La palabra heurística significa hallar o inventar, en disciplina científica se aplica a cualquier ciencia e incluye la elaboración de cambios auxiliares, principios, reglas, estrategias  y programas que faciliten resolver tareas de cualquier tipo.

Según Horst Müller:

 Los procedimientos heurísticos son formas de trabajo y de pensamiento que apoyan la realización consciente de actividades mentales exigentes.

Los procedimientos heurísticos como método científico pueden dividirse en principios, reglas y estrategias.

1. Principios heurísticos: Constituyen sugerencias para encontrar (directamente) la idea de solución; posibilita determinar, por tanto, a la vez, los medios y la vía de solución. Dentro de estos principios se destacan la analogía y la reducción.

1. Reglas heurísticas: Actúan como impulsos generales dentro del proceso de búsqueda y ayudan a encontrar, especialmente, los medios para resolver los problemas.

Las Reglas heurísticas que más se emplean son:

1. Separar lo dado de lo buscado.
2. Confeccionar figuras de análisis: esquemas, tablas, mapas, etc.
3. Representar magnitudes dadas y buscadas con variables.
4. Determinar si se tienen fórmulas adecuadas.
5. Utilizar números (estructuras más simples) en lugar de datos.
6. Reformular el problema.

1. Estrategias heurísticas: Se comportan como recursos organizativos del proceso de resolución, que contribuyen especialmente a determinar la vía de solución del problema abordado. Existen dos estrategias:
2. El trabajo hacia adelante: se parte de lo dado para realizar las reflexiones que han de conducir a la solución del problema.
3. El trabajo hacia atrás: se examina primeramente lo que se busca y, apoyándose de los conocimientos que se tienen, se analizan posibles resultados intermedios de lo que se puede deducir lo buscado, hasta llegar a los dados.

En computación, dos objetivos fundamentales son encontrar algoritmos con buenos tiempos de ejecución y buenas soluciones, usualmente las óptimas.

Una heurística es un algoritmo que abandona uno o ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser arbitrariamente errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco prueba de que siempre será así. Las heurísticas generalmente son usadas cuando no existe una solución óptima bajo las restricciones dadas tiempo, espacio, etc.

El Problema Del Agente Viajero

 

“Un vendedor tiene una lista de ciudades cada una de las cuales debe visitar solamente una vez; existen carreteras directas entre cada par de ciudades de la lista. Se debe encontrar la ruta que el vendedor debería seguir para que, siguiendo el camino más corto posible, visitara todas las ciudades, comenzando por cualquiera de ellas y volviendo a la misma. Un ejemplo de éste tipo de problemas para seis ciudades se plantea en la figura 2.6.

En principio se puede resolver éste problema explorando el árbol de todos los caminos posibles y eligiendo aquél que tenga la longitud mínima; pero, si existen n ciudades, el número de caminos diferentes entre ellas es (n-1)!, esto significa que el tiempo requerido para resolver el problema es proporcional a n!. Por lo tanto, si tenemos once ciudades, (11-1)! = 10*9*8*7*6*5*4*3*2*1 = 3, 628,000 rutas son posibles, es decir, se trata de un problema típico de explosión combinatoria en el que es útil aplicar técnicas heurísticas.

Una técnica heurística de propósito general que es útil para resolver problemas combinatorios es el 'algoritmo del vecino más próximo', que trabaja seleccionando la alternativa más cercana que aún no ha sido visitada y así sucesivamente hasta recorrer todos los nodos y retornar al punto de partida:

1. Seleccionar arbitrariamente una ciudad de partida.

2. Para seleccionar la siguiente ciudad, analizar todas las ciudades que aún no se han visitado y seleccionar aquélla que sea la más cercana a la ciudad actual; ir a ella en el siguiente paso.

3. Repetir el paso dos hasta que se hayan visitado todas las ciudades. éste algoritmo se ejecuta en un tiempo proporcional al cuadrado de n lo que representa una mejora significativa sobre n!.” (Edgar Altamirano Carmona 2014, p.11, 12)

El algoritmo del agente viajero se puede representar de la siguiente manera:

Definir el número de nodos, su posición y el costo por cada arista (i, j) donde i = ciudad 1 y j = ciudad 2

Elegir el nodo inicial i

Hacer

Si el nodo más cercano no se ha visitado

Visitar nodo j

Actualizar lista de nodos visitados

Costo_total = costo_total + costoij

Nodo i = nodo j

Hasta haber visitado todos los nodos

Conclusión:

Por heurística entendemos una estrategia, método, criterio o truco usado para hacer más sencilla la solución de problemas difíciles. El conocimiento heurístico es un tipo especial de conocimiento usado por los humanos para resolver problemas complejos.

En el área de computación su objetivo primordial es encontrar algoritmos con buenos tiempos de ejecución y que de buenas soluciones, preferentemente óptimas.

En el caso del problema del agente viajero se debe encontrar la ruta más corta que sea posible, es ahí donde entra la heurística porque le da la solución más óptima.

Bibliografía:

APUNTES DE INTELIGENCIA ARTIFICIAL

Edgar Altamirano Carmona    

Universisda Autónoma De Guerrero, 2014

ISC. Patricia Horta Rosado

Inteligencia Artificial (n.d.). Evaluando las Fuentes Electrónicas. Consultado el 17 de marzo del 2014. , página web  Instituto Tecnológico de Veracruz. http://ia.comeze.com/subtemas/un1/1.7.html

Sistemas De Producción

Sistemas De Producción

Un sistema de producción busca convertir a la computadora en una máquina que pueda resolver problemas específicos.

Un sistema de producción proporciona una estructura que facilita la descripción y la ejecución de un proceso de búsqueda.

Un sistema de producción consiste de:

Un conjunto de facilidades para la definición de reglas.

Mecanismos para acceder a una o más bases de conocimientos y datos.

Una estrategia de control que especifica el orden en el que las reglas son procesadas, y la forma de resolver los conflictos que pueden aparecer cuando varias reglas coinciden simultáneamente.

Un mecanismo que se encarga de ir aplicando las reglas.

“El algoritmo básico del aplicador de reglas puede escribirse en forma no determinística como sigue:

Algoritmo sisprod.

1. [Establecer la base de datos inicial.]

DATOS <--- base de datos inicial;

2. [Aplicar reglas hasta que se satisfaga alguna condición de terminación

del problema (éxito ó fracaso)]

while DATOS no satisfaga la condición de terminación del problema

{

seleccionar alguna regla R del conjunto de reglas, tal que

pueda ser aplicada a DATOS;

DATOS <--- resultado de aplicar R a DATOS;

}

3. [Fin]

presentar los resultados.

end.” (Edgar Altamirano Carmona 2014, p.10)

Conclusión:

En mi opinión el sistema de producción busca que la maquina pueda resolver problemas específicos, bajo algoritmos que se le implementen.

Así bien teniendo reglas que se prueban hasta encontrar una secuencia que cumplan una condición determinada.

Bibliografía:

APUNTES DE INTELIGENCIA ARTIFICIAL

Edgar Altamirano Carmona    

Universidad Autónoma De Guerrero, 2014

RESOLUCIÓN DE PROBLEMAS DE ESPACIO Y ESTADO

RESOLUCIÓN DE PROBLEMAS  DE ESPACIO Y ESTADO

Resolución de Problemas

La resolución de problemas es una capacidad que consideramos inteligente
Somos capaces de resolver problemas muy diferentes:

• Encontrar el camino en un laberinto
• Resolver un crucigrama
• Jugar a un juego
• Diagnosticar una enfermedad
• Decidir si invertir en bolsa

El objetivo es que un programa también sea capaz de resolverlos

Deseamos definir cualquier tipo de problema de manera que se pueda
resolver automáticamente.
Necesitamos:

• Una representación común para todos los problemas
• Algoritmos que usen alguna estrategia para resolver problemas
• definidos en esa representación común.

Definición de un Problema

Si abstraemos los elementos de un problema podemos identificar:

• Un punto de partida
• Un objetivo a alcanzar
• Acciones a nuestra disposición para resolver el problema
• Restricciones sobre el objetivo
• Elementos que son relevantes en el problema definidos por el tipo de
• dominio

Representación de problemas

Existen diferentes formas de representar problemas para resolverlos de

manera automática.

Representaciones generales:

Espacio de estados:

• un problema se divide en un conjunto de paso de resolución desde el inicio hasta el objetivo.

Reducción a subproblemas:

•  un problema se puede descomponer en una jerarquía de subproblemas

Representaciones para problemas específicos:

• Resolución de juegos
• Satisfacción de restricciones

Representación de problemas: Estados

Podemos definir un problema por los elementos que intervienen y sus relaciones.

En cada instante de la resolución de un problema esos elementos tendrán unas características y relaciones específicas.

Denominaremos Estado a la representación de los elementos que describen el problema 

en un momento.

Distinguiremos dos estado especiales el Estado Inicial (punto de partida) y el Estado Final 

(objetivo del problema).

Modificación del estado: operadores

Para poder movernos entre los diferentes estados necesitamos operadores de transformación.

Operador: Función de transformación sobre la representación de un estado que lo convierte 

en otro estado.

Los operadores definen una relación de accesibilidad entre estados .

Representación de un operador:

• Condiciones de aplicabilidad
• Función de transformación

Espacio de estados

Los estados y su relación de accesibilidad conforman lo que se denomina espacio de estados.

Representa todos los caminos que hay entre todos los estados posibles de un problema.

Podría asimilarse con un mapa de carreteras de un problema.

La solución de nuestro problema esta dentro de ese mapa.

Solución de un problema en Espacio de Estados

Solución: Secuencia de pasos que llevan del estado inicial al final

(secuencia de operadores) o también el estado final.

Tipos de solución: una cualquiera, la mejor, todas.

Coste de una solución: Gasto en recursos de la aplicación de los operadores a los estados. 

Puede ser importante o no según el problema y que tipo de solución busquemos.

Descripción de un problema en Espacio de Estados

• Definir el conjunto de estados del problema (explícita o implícitamente)
• Especificar el estado inicial
• Especificar el estado final o las condiciones que cumple
• Especificar los operadores de cambio de estado (condiciones de aplicabilidad y función de transformación)
• Especificar el tipo de solución:
• La secuencia de operadores o el estado final
• Una solución cualquiera, la mejor (definición de coste), .

Ejemplo: 8 puzzle

Espacio de estados: Configuraciones de 8 fichas en el tablero

Estado inicial: Cualquier configuración

Estado final: Fichas en orden específico

Operadores: Mover hueco

                    Condiciones: El movimiento está dentro del tablero.

                    Transformación: Intercambio entre el hueco y la ficha en la posición del

                     movimiento.

Solución: Qué pasos + El menor númer

Ejemplo: N reinas

Espacio de estados: Configuraciones de 0 a n reinas en el tablero con sólo una por fila y columna.

Estado inicial: Configuración sin reinas en el tablero.

Estado final: Configuración en la que ninguna reina se mata entre si.

Operadores: Colocar una reina en una fila y columna.

                    Condiciones: La reina no es matada por ninguna ya colocada

                    Transformación: Colocar una reina mas en el tablero en una fila y 

                    columna determinada

Solución: Una solución, pero no nos importan los pasos

Búsqueda en el espacio de estados

• La resolución de un problema con esta representación pasa por explorar el espacio de estados
• Partimos del estado inicial evaluando cada paso hasta encontrar un estado final
• En el caso peor exploraremos todos los posibles caminos entre el estado inicial del problema hasta llegar al estado final

Estructura del espacio de estados

Primero definiremos una representación del espacio de estados para poder implementar 

algoritmos que busquen soluciones.

• Estructuras de datos: Árboles y Grafos
• Estados = Nodos
• Operadores = Arcos entre nodos (dirigidos)
• Árboles: Solo un camino lleva a un nodo
• Grafos: Varios caminos pueden llevar a un nodo

Algoritmo Básico

• El espacio de estados puede ser infinito
• Es necesaria una aproximación diferente par buscar y recorrer árboles y grafos                      (no podemos tener la estructura en memoria)
• La estructura la construimos a medida que hacemos la búsqueda

Función: Búsqueda en espacio de estados()

Datos: El estado inicial.

Resultado: Una solución.

Seleccionar el primer estado como el estado actual

Mientras estado actual #= estado final hacer

               Generar y guardar sucesores del estado actual (expansión)

               Escoger el siguiente estado entre los pendientes (selección)

Fin

• La selección del siguiente nodo determinará el tipo de búsqueda                                         (orden de selección o expansión).
• Es necesario definir un orden entre los sucesores de un nodo (orden de generación).
• Nodos abiertos: Estados generados pero aún no visitados
• Nodos cerrados: Estados visitados y que ya se han expandido
• Tendremos una estructura para almacenar los nodos abiertos.
• Las diferentes políticas de inserción en la estructura determinarán el tipo de búsqueda.
• Si exploramos un grafo puede ser necesario tener en cuenta los estados repetidos                       (esto significa tener una estructura para los nodos
• cerrados). Merece la pena si el número de nodos diferentes es pequeño respecto al número       de caminos.

Características de los algoritmos

• Completitud: ¿Encontrará una solución?
• Complejidad temporal: ¿Cuanto tardará?
• Complejidad espacial: ¿Cuanta memoria gastará?
• Optimalidad: ¿Encontrará la solución óptima?

Algoritmo General de Búsqueda

Algoritmo: Busqueda General

Est_abiertos.insertar(Estado inicial)

Actual← Est_abiertos.primero()

mientras no es_final?(Actual) y no Est_abiertos.vacia?() hacer

               Est_abiertos.borrar_primero()

               Est_cerrados.insertar(Actual)

               Hijos ← generar_sucesores(Actual)

               Hijos ← tratar_repetidos(Hijos, Est_cerrados, Est_abiertos)

               Est_abiertos.insertar(Hijos)

              Actual ← Est_abiertos.primero()

fin

• Variando la estructura de abiertos variamos el comportamiento del algoritm                        (orden de visita de los nodos)
• La función generar_sucesores seguirá el orden de generación de sucesore definido                    en el problema.
• El tratamiento de repetidos dependerá de cómo se visiten los nodos.

Tipos de algoritmos

Algoritmos de búsqueda ciega:

• No tienen en cuenta el coste de la solución en la búsqueda
• Su funcionamiento es sistemático, siguen un orden de visitas y generación de nodos             establecido por la estructura del espacio de búsqueda.
• Anchura prioritaria, Profundidad prioritaria, Profundidad iterativa

Algoritmos de búsqueda heurística:

• Utilizan una estimación del coste de la solución para guiar la búsqueda
• No siempre garantizan el óptimo, ni una solución
• Hill-climbing, Branch and Bound, A∗, IDA∗

Búsqueda en Anchura Prioritaria

Los nodos se visitan y generan por niveles.

La estructura para los nodos abiertos es una cola (FIFO).

Un nodo es visitado cuando todos los nodos de los niveles superiores y sus hermanos                   precedentes han sido visitados.

Características:

• Completitud: El algoritmo siempre encuentra una solución
• Complejidad temporal: Exponencial respecto al factor de ramificación y la profundidad de la         solución O(r^p)
• Complejidad espacial: Exponencial respecto al factor de ramificación y la profundidad de la solución O(r^p)
• Optimalidad: La solución que se encuentra es óptima en número deniveles desde la raíz

Búsqueda en Profundidad Prioritaria

Los nodos se visitan y generan buscando los nodos a mayor profundidad y retrocediendo cuando       no se encuentran nodos sucesores.

La estructura para los nodos abiertos es una pila (LIFO)

Para garantizar que el algoritmo acaba debe imponerse un límite en la profundidad de exploración

Características:

• Completitud: El algoritmo encuentra una solución si se impone un límite de profundidad             y existe una solución dentro de ese límite.
• Complejidad temporal: Exponencial respecto al factor de ramificación y la profundidad             del límite de exploración  O(r^p).
• Complejidad espacial: En el caso de no controlar los nodos repetidos el coste es lineal        respecto al factor de ramificación y el límite de profundidad O(rp). Si tratamos repetidos el    coste es igual que en anchura. Si la implementación es recursiva el coste es O(p).
• Optimalidad: No se garantiza que la solución sea óptima.

Búsqueda en Profundidad Limitada

Procedimiento: Busqueda en profundidad limitada (limite: entero)

Est_abiertos.insertar(Estado inicial)

Actual ← Est_abiertos.primero()

mientras no es_final?(Actual) y no Est_abiertos.vacia?() hacer

            Est_abiertos.borrar_primero()

            Est_cerrados.insertar(Actual)

           si profundidad(Actual) ≤ limite entonces

           Hijos ← generar_sucesores (Actual)

           Hijos ← tratar_repetidos (Hijos, Est_cerrados, Est_abiertos)

           Est_abiertos.insertar(Hijos)

fin

Actual ← Est_abiertos.primero()

fin

• La estructura de abiertos es ahora una pila.
• Se dejan de generar sucesores cuando se llega al límite de profundidad.
• Esta modificación garantiza que el algoritmo acaba.
• Si tratamos repetidos el ahorro en espacio es nulo.

ID (iterative deepening): profundidad iterativa

• Intenta combinar el comportamiento espacial del DFS con la optimalidad del BFS.
• El algoritmo consiste en realizar búsquedas en profundidad sucesivas con un nivel                     de profundidad máximo acotado y creciente en cada iteración.
• Así se consigue el comportamiento de BFS pero sin su coste espacial, ya que la           exploración es en profundidad, y además los nodos se regeneran a cada iteración.
• Además esto permite evitar los casos en que DFS no acaba (existen ramas infinitas).
• En la primera iteración la profundidad máxima será 1 y este valor irá aumentando en           sucesivas iteraciones hasta llegar a la solución.
• Para garantizar que el algoritmo acaba si no hay solución, se puede definir una cota           máxima de profundidad en la exploración.

ID (iterative deepening)

Búsqueda en profundidad iterativa

• Completitud: El algoritmo siempre encontrará la solución
• Complejidad temporal: La misma que la búsqueda en anchura. El regenerar el árbol en           cada iteración solo añade un factor constante a la función de coste O(r^p).
• Complejidad espacial: Igual que en la búsqueda en profundidad.
• Optimalidad: La solución es óptima igual que en la búsqueda en anchura.

BILIOGRAFIA

http://www.lsi.upc.edu/~bejar/ia/transpas/teoria/2-BH1-introduccion_busqueda.pdf