UNED, Inteligencia Artificial, Búsqueda en un espacio de estados

ACTIVIDAD OBLIGATORIA: 1
Ejercicio 1: Problema de los misioneros y los caníbales.
Los estados con los que voy a trabajar son: q0,q1….,q21.
La información que facilitaré entre paréntesis corresponde al número de misioneros y caníbales que hay en cada orilla, separados por dos
barras invertidas "//" para indicar en qué orilla se encuentran. Al mismo tiempo, para indicar cual es la orillaactiva, subrayaré uno u otro
lado de la información para indicarlo.
Por otro lado, el coste asociado a cada movimiento es 1, es decir, cada vez que desplazamos la barca de una orilla a otra debemos
aumentar en una unidad el coste total (cada operador tiene coste 1).
Tendré varios estados de no regreso que corresponderán a situaciones de fin de juego, ya que incumplirán la condición de que nuncadeben estar en contacto un número mayor de caníbales con un número menor de misioneros. En ellos no indicaré que orilla está activa ya
que dicha situación es indistinta y así podré reutilizarlos independientemente de la orilla de la que provenga la barca. Dich os estados son:
○
○
○
○
○
○
○

q4 ( MMCCC // M )
q5 ( MCCC // MM )
q7 ( MMCCC // M )
q8 ( MCC // MMC )
q9 ( MMC // MCC )
q12(MM // MCCC )
q20 ( M // MMCCC )

El grafo dirigido del problema, comenzando en el estado q0 ( MMMCCC // ) y finalizando en q21 ( // MMMCCC), es el siguiente:
• Desde q0 ( MMMCCC // ) tenemos las siguientes opciones:
○ (C) = q1 ( MMMCC // C )
○ (CC) = q2 ( MMMC // CC )
○ (MC)= q3 ( MMCC // MC )
○ (M)= q4 (no admisible)
○ (MM)= q5 (no admisible)
• Desde q1 ( MMMCC // C ) sólo podemosregresar con el mismo caníbal.
• Desde q2 ( MMMC // CC):
○ (CC)= q0
○ (C) = q6 ( MMMCC // C )
• Desde q3 (MMCC // MC ):
○ (MC)= q0
○ (M)= q6 ( MMMCC // C )
○ (C)= q7 (no admisible)
• Desde q6 ( MMMCC // C ):
○ (C)= q2
○ (M)= q3
○ (CC)= q10 (MMM // CCC)
○ (MM)= q8 (no admisible)
○ (MC)= q9 (no admisible)
• Desde q10 ( MMM // CCC ):
○ (CC)= q6
○ (C) = q11 ( MMMC // CC )
• Desde q11 ( MMMC// CC ):
○ (C)= q10
○ (MM)= q13 ( MC // MMCC)
○ (M)= q9 (no admisible)
○ (MC)= q12 (no admisible)
• Desde q13 ( MC // MMCC):
○ (MM)= q11
○ (MC)= q14 ( MMCC // MC )
○ (M)= q9 (no admisible)
○ (C)= q8 (no admisible)
○ (CC)= q5 (no admisible)
• Desde q14 ( MMCC // MC ):
○ (MC)= q13
○ (MM)= q15 ( CC // MMMC )
○ (C)= q9 (no admisible)
○ (M)= q8 (no admisible)
○ (CC)= q12 (no admisible)Prácticas página 1

• Desde q15 ( CC // MMMC ):
○ (MM)= q14
○ (C)= q16 ( CCC // MMM)
○ (M)= q8 (no admisible)
○ (MC)= q5 (no admisible)
• Desde q16 ( CCC // MMM):
○ (C)=q15
○ (CC)= q17( C // MMMCC)
• Desde q17 ( C // MMMCC):
○ (CC)= q16
○ (M)= q18 ( MC // MMCC)
○ (C)= q19 ( CC // MMM)
○ (MC)= q8 (no admisible)
○ (MM)= q9 (no admisible)

• Desde q18 ( MC // MMCC):
○ (M)= q17○ (MC)= q21 ( // MMMCCC)
○ (C)= q20 (no admisible)

• Desde q19 ( CC // MMM):
○ (C)= q17
○ (CC) = q21 ( // MMMCCC)

Por tanto, y teniendo en cuesta que el coste asociado a cada operador es 1, disponemos de 4 caminos óptimos que nos llevan a la misma
solución, y los 4 con el mismo coste.
Orilla1 = O1 // Orilla2 = O2
O1 - O2 (paso de la orilla 1 a la orilla 2)
O2 - O1 (paso de la orilla2 a la orilla 1)
camino O1 - O2 O2 - O1 O1 - O2 O2 - O1 O1 - O2 O2 - O1 O1 - O2 O2 - O1 O1 - O2 O2 - O1 O1 - O2 coste total
1

CC

C

CC

C

MM

MC

MM

C

CC

M

MC

11

2

CC

C

CC

C

MM

MC

MM

C

CC

C

CC

11

3

MC

M

CC

C

MM

MC

MM

C

CC

M

MC

11

4

MC

M

CC

C

MM

MC

MM

C

CCC

CC

11

(adjunto fichero EJERCICIO1.jff, para su uso en JFLAP)

Ejercicio: 2 Explicar razonadamente en qué orden se expandirán los nodos.

1. Búsqueda Primero en Anchura ( de izquierda a derecha ).
En este caso debemos tratar a ABIERTA como si fuese una cola (insertando los sucesores siempre al final de ABIERTA).
En primer lugar insertamos el estado inicial en abierta:
J...