Ejercicio de algoritmo de Búsqueda Heuristica pura (Torres de Hanoi)

  

Ejercicio de Grafo en Profundidad c++

RECORRIDO EN PROFUNDIDAD PROGRAMA

programa en c++ adaptado de

https://raw.githubusercontent.com/jariasf/Online-Judges-Solutions/master/Algorithms/C++/Graph%20Theory/Algoritmo%20DFS%20usando%20Recursion.cpp

/*

adaptado por paola martinez , carlos diaz y jorge hernández

*/

#include <stdio.h>

#include <cstring>

#include <vector>

using namespace std;

#define MAX 550

vector<int> ady[ MAX ];  //lista de adyacencia

bool visitado[ MAX ];    //para nodos visitados

int V;

int path[ MAX ];         //para guardar la direccion del  recorrido

///Ver todo el recorrido del grafo de acuerdo al orden ingresado en la lista de adyacencia

bool first;

void dfs( int u )

{

   ( first )? printf("%d" , u ) : printf("->%d" , u ); //operador terneario

   first = false;

   visitado[ u ] = true;

   for( int v = 0 ; v < ady[ u ].size(); ++v )

{

       if( !visitado[ ady[ u ][ v ] ] ){

           dfs( ady[ u ][ v ] );

       }

   }

}

///Ver todos las rutas posibles partiendo de nodo inicial y llegando a uno final, usamos backtracking

void dfs_allPath( int u , int fin , int len ){

   visitado[ u ] = true;

   path[ len ] = u;                    //almaceno la direccion del vertice actual

   if( u == fin ){                     //si se llego al final imprimimos ese path

       first = true;

       for( int i = 0 ; i <= len ; ++i ){

           ( first ) ? printf("%d" , path[i]) : printf("->%d" , path[i] );

           first = false;

       }

       printf("\n");

       return;

   }

   for( int i = 0 ; i < ady[ u ].size(); ++i ){

       int v = ady[ u ][ i ];

       if( !visitado[ v ] ){

           dfs_allPath( v , fin , len + 1 );

           //parte para backtracking, aquellos nodos hoja ya que no poseen adyacentes o ya fueron visitados

           visitado[ v ] = false;              //marcamos como no visitado para usarlo posteriormente en otro path

       }

   }

}

int main(){

   int E , x , y, inicial , final;

   scanf("%d %d" , &V , &E );      //Numero de vertices y numero de aristas

   printf("Digita las entradas para generar grafo");

   for(int i = 1 ; i <= E ; ++i )

{

   

printf("Por favor dijita x y y ");

       scanf("%d %d" , &x , &y );  //Origen y destino

       ady[ x ].push_back( y );

       ady[ y ].push_back( x );    //Commentar si se desea aplicar en grafo dirigido

   }

   

   first = true;

   //Veremos todo el recorrido del grafo iniciando en el vertice ingresado

   printf("Nodo raiz: ");

   scanf("%d" , &inicial );

   memset( visitado , 0 ,sizeof( visitado ) );

   printf("Recorrido DFS de todo el grafo\n");

   dfs( inicial );

   printf("\n\n\n");

   //Veremos posibles rutas de nodo inicial a uno final

   memset( visitado , 0 , sizeof( visitado ) );        //inicializar a no visitado

   printf("Posibles Rutas de inicial a final usando regreso\n");

   printf("Nodo Final: ");

   scanf("%d" , &final );

   dfs_allPath( inicial , final , 0 );                     //posibles rutas de nodo inicial a final

   return 0;

}

ejecución

Taller Busqueda en Anchura (Ranas)

¿Que es Búsqueda en Anchura?

Búsqueda en anchura es un algoritmo para recorrer o buscar elementos de un grafo(usado frecuentemente en arboles). Se comienza por la raíz y se explora todos los hijos de este nodo. A continuación se explora cada unos de los hijos de los hermanos y así sucesivamente hasta encontrar la solución.

¿Cual es la complejidad temporal para la búsqueda en Anchura?

Su complejidad tanto espacial como temporal es exponencial, y está en O (n^p), siendo n el número medio de sucesores, y p el nivel donde se alcanza la solución; por ello, esta estrategia es sólo aplicable a problemas no demasiado amplios.

Este procedimiento es completo, ya que encontrará siempre una solución si es que la hay, pero en general no es óptimo. Para implementarlo se ha hecho uso de una cola FIFO.

Ejercicio 

Hay tres personas de bien y 3 políticos los cuales están en la orilla 1 y desean pasar el rió en una
balsa y llegar a la orilla 2 Resolverlo por el método de búsqueda en Anchura 

    

   

Ciudadanos y Políticos

FORMALIZACION DE PROBLEMAS DE BÚSQUEDA

•  Formalizar los siguientes problemas como un problema de búsqueda

1.     Se encuentra en una orilla del rio 3 políticos y 3 ciudadanos de bien, la idea es pasar los políticos y los ciudadanos  al otro lado del rio, con las siguientes condiciones 

• Balsa: 2 personas
• No pueden en ninguna de las orillas más políticos que ciudadanos porque o si no los políticos los roban    

ESTADO INICIA
      ESTADO FINAL: 

ESPACIO DE ESTADO: 

Número posible de estados 6! = 720, ya que son 6 los participantes de este juego

               

       OPERADORES: 

1.     Político y un ciudadano cruzan el rió 

2.     1 Político cruza el rió 

3.     1 Ciudadano cruza el rió 

4.     2 Políticos cruzan el rió

5.     2 Ciudadanos cruzan el río

Ejercicios de Bùsqueda

Formalizarlos siguientes problemas como un problema de búsqueda

Ejercicio 1.

Hay tres personas de bien y 3 políticos los cuales están en la orilla 1 y desean pasar el rió en una
balsa y llegar a la orilla 2.

Regla:

-No pueden en quedar en ninguna de las dos orillas más políticos que ciudadanos, porque los políticos roban.

-La balsa solo puede ser usada por dos personas.


1 Estado Inicial 

2. Estado Final

3. Espacio de Estados 

1) En la Orilla 1: 3 ciudadanos y 3 políticos 

     Balsa: sola 

     Orilla 2: sola 

2) Orilla 1: 2 ciudadanos y 2 políticos 

     Balsa: 1 ciudadano y 1 político y esta en la  (orilla 1)

     Orilla 2: sola  

3) Orilla 1: 2 ciudadanos y dos políticos 

     Balsa: 1 político  y esta en la (orilla 2)

    Orilla 2:1 ciudadano

4) Orilla 1:2 ciudadano y 1 político 

    Balsa: 2  político  y están en la (orilla 1)

    Orilla 2:1 ciudadano 

5) Orilla 1:2 ciudadanos y 1 político 

    Balsa: 1 político y están en la (orilla 2) 

    Orilla 2: 1 ciudadano y 1 político

6) Orilla 1: 1 ciudadanos y 1 político 

    Balsa: 1 político y 1 ciudadano y están en la (orilla 1)

    Orilla 2: 1 ciudadano y 1 político

7) Orilla 1: 1 ciudadano y 1 político 

    Balsa: 1 político y esta en la (orilla 1)

    Orilla 2:2 ciudadanos y 1 político

8) Orilla 1: 1 ciudadano 

     Balsa: 1 políticos y están en la  (orilla 2)

     Orilla 2: 2 ciudadanos y 2 políticos

9) Orilla 1:  0 personas 

     Balsa: 1 políticos y 1 ciudadanos  y esta en la (orilla 1)

     Orilla 2: 2 ciudadanos y 2 políticos

10) Orilla 1: 0 personas 

      Balsa: 0  personas  y esta en la (orilla 2)

      Orilla 2: 3 ciudadanos y 3 políticos 

4. Operaciones.

-Arriba 

-Abajo 

-Desplazar 

-Parar 

-Recoger personas 

-Subir a la balsa 

-Bajar a la balsa 

Ejercicio 2.

1.Estado Inicial

                                  

2. Estado Final 

                                   

  

3. Estado de Estados 

1) Salto de Caballo Blanco 

                                

2) Salto de Caballo Negro 

  

                            

                              

3) Movimiento del Caballo Blanco

    

                          

                              

4) Salto del Caballo Negro 

                          

                             

                            

  

5) Movimiento del Caballo Negro 

                                

6) Salto del Caballo Blanco

                             

7) Salto del Caballo Negro 

                                                              

  8) Movimiento del Caballo Blanco 

                                 

9)  Salto de Caballo Negro 

                             

10) Movimiento del Caballo Negro 

                         

                             

ESPACIO DE ESTADOS:

9! = 36.288

      OPERADORES

  

  

Invetigaciòn

¿Que es Inteligencia Artificial?

La inteligencia artificial es considerada una rama de la computación y relaciona un fenómeno natural con una analogía artificial a través de programas de computador.

La inteligencia artificial puede ser tomada como ciencia si se enfoca hacia la elaboración de programas basados en comparaciones con la eficiencia del hombre, contribuyendo a un mayor entendimiento del conocimiento humano.

Si por otro lado es tomada como ingeniería, basada en una relación deseable de entrada-salida para sintetizar un programa de computador. "El resultado es un programa de alta eficiencia que funciona como una poderosa herramienta para quien la utiliza."

A través de la inteligencia artificial se han desarrollado los sistemas expertos que pueden imitar la capacidad mental del hombre y relacionan reglas de sintaxis del lenguaje hablado y escrito sobre la base de la experiencia, para luego hacer juicios acerca de un problema, cuya solución se logra con mejores juicios y más rápidamente que el ser humano.

 En la medicina tiene gran utilidad al acertar el 85 % de los casos de diagnóstico.

¿Que avances se han dado en los últimos tres años?

1.-‘Jarvis’

Se trata del propósito de año nuevo del creador de Facebook, Mark Zuckerberg: crear un sistema que le permitiera controlar su hogar: Jarvis, un mayordomo virtual.

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.

El sistema incluye varios paradigmas de inteligencia artificial, tales como el procesado y comprensión del lenguaje natural, el reconocimiento facial, de voz, y, lo más importante, la capacidad de aprender con la experiencia. A una semana de que finalice el año, el objetivo es que este mayordomo sea totalmente funcional.

2.- Ocean One

Se trata un robot humanoide que tiene como misión adentrarse al fondo del mar, cual fue desarrollado por un grupo de especialistas de la Universidad de Stanford, ubicada en California. Sus manos y brazos y manos están totalmente articulados lo que le permite realizar movimientos como un verdadero 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.- Smart VR: 

El traslado de la Realidad Virtual (VR) al móvil, una oportunidad para las marcas
la realidad Virtual  está moviéndose del mundo de los videojuegos y consolas al consumidor medio y a través de sus smartphones. Facebook y Twitter ya cuentan con retransmisiones en directo a las que se puede acceder acoplando gafas o cardboards a los teléfonos.

El salto a los smartphones y sus aplicaciones más usadas ofrecerá a las marcas muchas oportunidades de comunicación. Por ejemplo, los minoristas tendrán la oportunidad de transformar la forma en que la gente compra, permitiéndoles probar productos sin tener que visitar una tienda.

4.- Robots mayordomo

Asistencia automatizada: los robots mayordomo, gran éxito en las tiendas de High Street
Los robots industriales se han utilizado durante muchos años. Ahora, la tecnología combina la automatización física con la digital para crear robots de servicio, que trabajarán junto a nosotros.

 Las oportunidades más obvias e inmediatas están en la venta al por menor y la hostelería.

 Los robots de servicio serán capaces de proporcionar información sobre precios y disponibilidad de existencias y, utilizando algoritmos, podrán ofrecer descuentos y sugerencias de productos relacionados. 

Las oportunidades podrían extenderse más allá del comercio a la asistencia en información sanitaria y en ayuda doméstica.

¿Que peligros tiene la Inteligencia Artificial?

El escrito toma en cuenta décadas de investigación sobre inteligencia artificial, y entre las principales advertencias se habla de la posibilidad de que en un ambiente no controlado en forma adecuada, los sistemas de inteligencia artificial podrían tener comportamientos no deseados e incluso dañinos.

La comunidad muestra así la preocupación ante una posible independencia de la inteligencia artificial, capaz de pueda tomar vida propia y superar la que ha figurado el hombre. De este modo, quienes hoy estamos a cargo de estos dispositivos perderíamos el control sobre las máquinas y estas podrían actuar en contra de sus creadores. Según la carta abierta, las investigaciones deberían enfocarse en lograr que quienes trabajan con ella tomen medidas de seguridad ante una rebelión robótica en caso de problemas.

La diferencia entre la inteligencia y las capacidades de robots y computadorascon respecto a la mente humana es cada vez menor, incluso llegando a superarnos en algunos aspectos, lo que puede resultar preocupante.

Las máquinas y sistemas de inteligencia artificial carecen de dos cosas muy importantes:  sentimientos y ètica  por lo que no son capaces discernir correctamente entre el bien y el mal, ya que su comportamiento depende de programación y no de la racionalidad, por lo que, en caso de cualquier falla, podrían dañar al resto.

¿Cual ha sido el desarrollo de la Inteligencia Artificial?

En los últimos años el desarrollo y evolución de la  Inteligencia Artificial ha creado mejoras importantes que millones de negocios a escala mundial están aprovechado. Esta tecnología, que fue introducida por primera vez en 1955, ha mostrado avances significativos, que nos hacen pensar un futuro donde los humanos seremos capaces de predecir muchos de los factores empresariales que hasta hoy pueden causar incertidumbre y miedos para invertir.

Tal vez recuerdas a la computadora HAL 9000 de la película 2001,Odisea del espacio en la cual ya se mostraba lo que la IA podría hacer por la humanidad.

El aprendizaje automático  de las máquinas sigue mejorando, así como la creciente demanda de consumidores respecto al análisis de los grandes datos, por lo que seguramente ya te estás imaginando las infinitas posibilidades de la IA, y los posibles negocios que puedes crear en lo que ya se llama la cuarta revolución industrial.

Asistentes personales de voz de la nueva era como Alexa y Google Home, el HomeKit de Apple para controlar todos los dispositivos electrónicos de casa y la omnipresencia de chatbots que agilizan los procesos de la banca en línea o que contestan preguntas relacionadas con la salud, prometen crecer con la ola tecnológica actual y reconstruir la confianza del consumidor, así como aumentar la demanda de estos desarrollos.

El actual éxito de la IA se debe en gran medida a algunos factores críticos, como son las nuevas plataformas de los principales actores tecnológicos, incluyendo a Google, Microsoft y Amazon, que han apoyado la práctica e impulsado la construcción de una masa crítica de profesionales que están aprovechando la inteligencia artificial para facilitarnos a todos un manejo más intuitivo de equipos y programas que tal vez hace años hubiera únicamente estado en manos de los ingenieros.