Busqueda en árboles

Problemas de Busqueda en Árboles

Políticos y Ciudadanos 

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 número 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 rio.
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 político que hay en la segunda orilla se desplaza a la primera.
9: El mismo político se lleva a otro a la segunda orilla.
10: El político vuelve a la primera.
11: El político se lleva al que estaba en la primera orilla.
12: Los 2 políticos llegan a la segunda orilla y todos terminan por cruzar el rio

Operadores:

SB(SubirseBalsa)
BB(BajarseBalsa)
DBI(DesplazarBalsaIzquierda)
DBD(DesplazarBalsaDerecha)

Caballos Negros y 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), además de que ninguno puede ubicarse en la misma casilla.

Estado inicial:

Estado final:

Espacio de estados: 34

Operaciones:
MC1A2I(Mover Caballo 1 Arriba 2 Izquierda)
MC2A1I(Mover Caballo 2 Arriba 1 Izquierda)
MC1AB2I(Mover Caballo 1Abajo 2 Izquierda)
MC2AB1I(Mover Caballo 2 Abajo1 Izquierda)
MC1A2D(Mover Caballo 1 Arriba 2 Derecha)
MC2A1D(Mover Caballo 2 Arriba 1 Derecha)
MC1AB2D(Mover Caballo 1 Abajo 2 Derecha)
MC2AB1D(Mover Caballo 2 Abajo 1 Derecha)

EP (Verificar espacio vacío)