Solucion de un ejemplo con algoritmo de A*

Problema
Se desea llegar del punto "S" al punto "G" usando el método de A*, por lo tanto se debe hallar la solución con menor costo

Árbol de solución

Algoritmo de solución

Taller grafo de ciudades

1) Búsqueda en profundidad iterativa
Este tipo de búsqueda, es una combinación de la búsqueda en anchura y en profundidad, donde combina las ventajas de estas dos, tomando de la BPP (búsqueda por profundidad) la complejidad espacial y de la BPA (búsqueda por anchura) la optimización. Ademas evita gastos en equipo ya que no es recursiva.

"c" es usado como auxiliar para recorrer el árbol sin irse eternamente por una rama. "L" y "n" se usan para evaluar cada nodo y encontrar la solución, este algoritmo se basa en la búsqueda en profundidad.
Ejemplo de la expansión:

Complejidad Espacio:
Es igual que la búsqueda en profundidad:

                    d(b-1)

Complejidad Tiempo:
            
Optima-> Se encuentra la solución mas cercana a la raíz.
Completa-> Como no tiene problema de ramas infinitas, encuentra la solución si la hay.
Problema:
Se desea llegar de la ciudad A hasta la ciudad F

Solución por profundidad iterativa
Árbol completo:                                                                           

Recorrido de la profundidad iterativa

La mejor solución esta en el paso #34 la peor en el paso #63
Algoritmo de solución:

2) Amplitud iterativa
Es una variación de las búsquedas en profundidad y anchura, tomando de referencia la expansión de los nodos de la búsqueda en anchura (BPA). 

Con este algoritmo no se expande por completo en profundidad el árbol sino que va recorriendo el árbol de izquierda a derecha.
Ejemplo de la expansión:

Complejidad espacio:
Es igual que la búsqueda en profundidad:
                    d(b-1)
Complejidad tiempo:

Optima-> Se encuentra la solución no necesariamente la más cercana a la raíz.
Completa-> Encuentra la solución si la hay.
Solución problema anterior mencionado 

Algoritmo de solución:

Referencias

Wordpress (2016). Amplitud Iterativa. https://intartificialblog.wordpress.com/2016/09/05/amplitud-iterativa/

Daniel Alejandro Garcia Lopez. (2009). Solución de problemas por búsqueda. 

http://www.unistmo.edu.mx/~daniel.garcia/unidadiii_ia.pdf.

Israel Calderón de la Cruz (2014). Busqueda por profundidad iterativa.

https://es.slideshare.net/icalderond/busqueda-por-profundidad-iterativa.

Iiia.csic.es. (2016). Busqueda Ciega.

http://www.iiia.csic.es/~pedro/busqueda1-ciega.

Búsqueda en profundidad

Ejercicio de los sapos y las ranas

Hay 7 rocas en un lago, en 6 de ellas hay 3 ranas y 3 sapos una en cada una de esas rocas, la séptima esta vacía y en el medio de las otras 6 rocas. Las ranas están todas ubicadas de forma seguida en las 3 rocas al lado izquierdo de la roca vacía y los sapos en la parte derecha de igual forma. Se busca llevar a las ranas donde están los sapos y viceversa, teniendo en cuenta que las ranas pueden saltar por encima de los sapos, pero los sapos no pueden hacer lo mismo y solo pueden saltar al espacio vació. Tampoco puede haber mas de 1 rana y/o sapo en una roca.

Estado inicial:

Estado final:

Espacio estado: 43 aproximadamente
Solucion
1: S1 S2 S3 O R1 R2 R3
2: S1 S2 O S3 R1 R2 R3
3: S1 S2 R1 S3 O R2 R3
4: S1 S2 R1 O S3 R2 R3
5: S1 S2 O R1 S3 R2 R3
6: S1 O S2 R1 S3 R2 R3
7: S1 R1 S2 O S3 R2 R3
8: S1 R1 S2 R2 S3 O R3
9: S1 R1 S2 R2 O S3 R3
10: S1 R1 S2 O R2 S3 R3
11: S1 R1 O S2 R2 S3 R3
12: S1 O R1 S2 R2 S3 R3
13: O S1 R1 S2 R2 S3 R3
14: R1 S1 O S2 R2 S3 R3
15: R1 S1 R2 S2 O S3 R3
16: R1 S1 R2 S2 R3 S3 O
17: R1 S1 R2 S2 R3 O S3
18: R1 S1 R2 S2 O R3 S3
19: R1 S1 R2 O S2 R3 S3
20: R1 S1 O R2 S2 R3 S3
21: R1 O S1 R2 S2 R3 S3
22: R1 R2 S1 O S2 R3 S3
23: R1 R2 S1 R3 S2 O S3
24: R1 R2 S1 R3 O S2 S3
25: R1 R2 S1 O R3 S2 S3
26: R1 R2 O S1 R3 S2 S3
27: R1 R2 R3 S1 O S2 S3
28: R1 R2 R3 O S1 S2 S3

Árbol del problema:



Algoritmo de búsqueda en profundidad para la solución:

Búsqueda ciega por anchura

Complejidad de anchura temporal

imágenes sacadas de: http://www.iiia.csic.es/~pedro/busqueda2-ciega.pdf

Ejercicio de los políticos y ciudadanos representado en grafo

P = politicos  C = ciudadanos de bien  A = orilla A  B = orilla B

Ejercicios de busqueda

1- Políticos y Ciudadanos de Bien 

Se desea transportar 3 políticos y 3 ciudadanos de bien de una orilla del rió a otra, para esto cuentan con una barca en la que caben dos personas, sin embargo a medida que se va transportando a estas personas se debe cumplir la regla de que no puede haber una mayoría de políticos en alguna de las dos orillas, en comparación con el numero de ciudadanos de bien porque los ciudadanos serían robados.

Solución

Estado inicial: 3 políticos y 3 ciudadanos de bien en la orilla de la izquierda y con la balsa arrimada a esa orilla

Estado final: 3 políticos y 3 ciudadanos de bien en la orilla de la derecha y con la balsa arrimada a esa orilla

Espacio de estado: 

1: 2 Políticos cruzan hacia el otro lado del rió.
2: Regresa uno de los dos con el bote.
3: Un político lleva a otro político al otro lado.
4: El político regresa de nuevo y se quedan de momento 2 políticos en la segunda orilla.
5: 2 ciudadanos de bien cruzan al otro lado.
6: 1 ciudadano regresa con 1 político y por ahora en las dos orillas hay 1 político y 1 ciudadano de bien.
7: Cruzan los 2 ciudadanos de bien a la segunda orilla lo que significa que todos los ciudadanos están en la segunda orilla.
8: El politico que hay en la segunda orilla se desplaza a la primera.
9: El mismo politico se lleva a otro a la segunda orilla.
10: El politico vuelve a la primera.
11: El politico se lleva al que estaba en la primera orilla.
12: Los 2 politicos llegan a la segunda orilla y todos terminan por cruzar el rio

Operadores:

AB(AbordarBalsa)
DAB(DesabordarBalsa)
MBI(MoverBalsaIzquierda)
MBD(MoverBalsaDerecha)
VO1(VerOrilla1)
VO2(VerOrilla2)

2- Caballos negros y Caballos blancos

Se desea ubicar a dos pares de caballos negros y blancos en un tablero para que queden los blancos abajo con casilla de por medio y los negros arriba con casilla de por medio, su posición inicial es que los blancos están arriba con una casilla de por medio y los negros de igual manera pero en la parte baja. El tablero por donde se pueden mover es de 3x3 y sus movimientos deben ser los de cualquier caballo en ajedrez (en L), ademas de que ninguno puede ubicarse en la misma casilla.

Solución
Estado inicial:


Estado final:


Espacio de estados: 34
 

Operaciones:
MC1U2L(MoverCaballo1Up2Left)
MC2U1L(MoverCaballo2Up1Left)
MC1D2L(MoverCaballo1Down2Left)
MC2D1L(MoverCaballo2Down1Left)
MC1U2R(MoverCaballo1Up2Right)
MC2U1R(MoverCaballo2Up1Right)
MC1D2R(MoverCaballo1Down2Right)
MC2D1R(MoverCaballo2Down1Right)
VEV(VerificarEspacioVacio)

Curso de IA

Inteligencia Artificial, definición, avances, peligros y su desarrollo 

La definición formal más común es la de M. Minsky, uno de los más influyentes en el área. Dice que "es la ciencia de hacer máquinas que hagan cosas que si fueran hechas por los hombres".

Puede ser tomada como parte de la ciencia, por la cual fenómenos computacionales y naturales se unen para hacer programas que equiparen el conocimiento del hombre. O también como ámbito de la ingeniería en la que se busca una buena relación entre entrada-salida para sintetizar un algoritmo computacional.

Existen diferentes tipos de inteligencia artificial

Que piensan en detalle como humanos.

Que actúan de igual forma como humanos.

Que piensan lógicamente llegándose a comparar con el pensamiento humano

Que racionalmente actúan acercándose a la forma humana de actuar

Los avances más destacados de los últimos años han sido:

Jarvis: un mayordomo virtual creado por Mark Zuckerberg con el fin de tener un sistema que le permitiera controlar su hogar. "Jarvis puede distinguir a los miembros de la familia de Zuckerberg, aprender sus diferencias y patrones, aspecto que hace particular este sistema. Su creador puede hablarle a través de su computadora y su teléfono para tener el control de sus luces, temperatura, reproductor música y las cámaras de seguridad de su casa." [1].

Esta IA puede procesar y comprender el lenguaje natural, hacer reconocimiento facial, de voz, y también posee la capacidad de aprender con la experiencia.

WaveNet: Es un programa que crea voces parecidas a las de los humanos. Este desarrollo logra hacer que los asistentes de voz en los smartphones parezcan reales. "WaveNet aprende a generar simulaciones de voces emulando la frecuencia de los sonidos, la fluidez de los fonemas y el ritmo de conversación de las personas. En una onda de audio, desmenuzada al detalle, se encuentran todos los matices de una voz real: temblor, entonación, silencios irregulares, ruidos de respiración, etc" [2].

iMind Technology: Esta inteligencia artificial fue creada sin conciencia para que pudiera aprender a partir de cualquier interacción con los humanos. Puede procesar el lenguaje e interpretar lo que una persona quiere decir. Además puede comprender el contexto en el que se le está hablando.

Ocean One: Es un robot humanoide que pretende usarse para investigar el fondo marino, fue desarrollado por un grupo de especialistas de la Universidad de Stanford, en California. Sus extremidades están bien hechas ya que su movimiento es como el de un humano. "Éste fue equipado con un software de Inteligencia Artificial que le permite identificar objetos en el fondo del mar. Además, es controlado desde la superficie por un operador, quien puede ver lo que el robot tiene en frente, gracias a un sistema de visión binocular, y puede ‘sentir’ lo que Ocean One tiene en sus manos, por medio de un sistema de sensores de presión" [3].

Las posibles amenazas que la inteligencia artificial traiga con su desarrollo han sido previstas por algunas personas relacionadas en el campo de la tecnología o ciencia, como por ejemplo Elon Musk, el fundador del fabricante de carros Tesla y la empresa de exploración espacial Space X,  afirmo durante una reunión de gobernadores de los Estados Unidos, que "La inteligencia artificial representa el raro caso en el que necesitamos ser pro-activos con la regulación, en vez de reactivos. Creo que, para el momento en el que estemos reaccionando, será muy tarde. La inteligencia artificial representa un riesgo fundamental para la existencia de la civilización humana". El británico  Stephen Hawking dijo "La tecnología podría revertir parte del daño causado al planeta por la industrialización y también ayudar a poner fin a la pobreza, pero la inteligencia artificial (IA) debe ser controlada".

El desarrollo de la inteligencia artificial se remonta en la época donde el matemático Walter Pitts y el neurofisico Warren McCulloch hicieron un trabajo de investigación que hablaba de inteligencia artificial con fundamentos en la fisiología humana, el funcionamiento de las neuronas, la teoría computacional de Alan Turing, entre otros. Esta investigación fue la primera del tema y fundo las bases de las redes neuronales.

Trece años luego, Josehp Engelberger creo el primer robot industrial de la historia llamado Unimate. John McCarthy fue el primero en usar el término de "Inteligencia Artificial" en una conferencia en el 56.

Qué es inteligencia artificial
http://bvs.sld.cu/revistas/san/vol2_2_98/san15298.htm

¿Qué es la inteligencia artificial?
https://www.hpe.com/lamerica/es/what-is/artificial-intelligence.html

¿Qué es inteligencia artificial?
http://culturacion.com/que-es-la-inteligencia-artificial/

Avances sobre inteligencia artificial de este 2016 [1],[2],[3]   http://tecreview.itesm.mx/avances-sobre-inteligencia-artificial-de-este-2016/

¿Cómo surgió el desarrollo de la inteligencia artificial?

https://blogingenieria.com/libros-ingenieria/desarrollo-inteligencia-artificial/

El desarrollo de la inteligencia artificial
http://diariojudio.com/opinion/el-desarrollo-de-la-inteligencia-artificial/255519/