Problema de los ciudadanos y los políticos 

Este problema se ambienta de igual manera que el problema en el que hay 3 caníbales y 3 ciudadanos, el objetivo es cruzarlos todos al otro lado del rió sin que haya mayor numero de caníbales que de ciudadanos o estos los devoran, en este caso si hay mayor numero de políticos estos robaran a los ciudadanos. 

En este apartado se estudia la búsqueda por profundidad, y para ello se pide desarrollar los siguientes puntos:

1       Formalizar el problema como un problema de búsqueda

2       Generar el algoritmo búsqueda primero en profundidad con prueba de escritorio

3       Encontrar número de nodos generados y expandidos

4       Tiempo hasta encontrar la solución

5       Plantear el problema en un lenguaje de programación

      

       Estado inicial

     
     

       Estado final 

       

        

      Espacio de estados

      n = (3) + (3) = 6 

      Numero posible de estados: 6! = 720 

      Operadores        

      

c    condiciones para operar 

      A) El barco solo se puede desplazar cuando  amenos una persona esta remando

      B) No pueden haber mas políticos que ciudadanos en ninguna de las dos orillas

      C) No se pueden desplazar una y otra vez los mismos tripulantes

     Instrucciones para operar 

     1) 1 político y un ciudadano cruzan el rió 

     2) 1 político cruza el rió

     3) 1 ciudadano cruza el rió 

4   4) 2 políticos cruzan el rió 

     5) 2 ciudadanos cruzan el rió

      siguiendo los operadores anteriores se llego al siguiente árbol 

     

       El algoritmo de búsqueda en profundidad es el siguiente: 

     

      

      Nodos generados y expandidos

     

      Los nodos generados son 17 y los nodos expandidos 3 

     Tiempo demorado

      

     Para esto hay que tener en cuenta lo siguiente: 

     

     b = factor de ramificación 

     d = Nivel del árbol 

     Tiempo = d = 12 

     Espacio que ocupo el algoritmo 

     E = d(b-1) + 1 

     E = 12(3-1) + 1 =  25 

      

   

      

ç