Skip to main content
se añadieron 44 caracteres en el cuerpo
Origen Enlace
import graphviz
import os
os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin'
import Drawpy
n = 0
number_node = 0
side1 = "left"
side2 = "right"

start = {"farmer":side1, "wolf":side1, "goat":side1, "cabbage":side1}
meta = {"farmer":side2, "wolf":side2, "goat":side2, "cabbage":side2}

_Queue =[]
notrepet =[]
_patch  = []

notrepet.append(start)
_Queue.append(start)
   

def validate_state(state):
    if state["wolf"] == state["goat"] and state["wolf"] != state["farmer"]:
        return False
    elif state["goat"] == state["cabbage"] and state["cabbage"] != state["farmer"]:
        return False
    else:
        return True

def Generar_states(state_actual, _patch ,dot):
    global n
    list_state = []
    new_state = dict(state_actual)
    _nodes = [w[0] for w in _patch.copy()] # se supone que obtengo todas las llaves de los dict
    if state_actual not in _nodes: #si aun no se ah creado el nodo para ese estado
        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 0)
    if state_actual["farmer"] == side2:  
        new_state["farmer"] = side1  
        if validate_state(new_state) and new_state not in notrepet:
            list_state.append(dict(new_state)) 
            notrepet.append(dict(new_state))
            n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)

        for k, v in new_state.items():
            if k != "farmer":
                if v == side2: 
                    new_state[k] = side1  
                    if validate_state(new_state) and new_state not in notrepet:
                        list_state.append(dict(new_state))
                        notrepet.append(dict(new_state))
                        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)
                    new_state[k] = side2 
    else: 
        new_state["farmer"] = side2
        for k, v in new_state.items():
            if k != "farmer":
                if v == side1:
                    new_state[k] = side2
                    if validate_state(new_state) and new_state not in notrepet:
                        list_state.append(dict(new_state))
                        notrepet.append(dict(new_state))
                        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)
                    new_state[k] = side1
    return list_state

#Tipo: (0) en profundidad (1) anchura, (2)profundidad limitada
def algoritmo(tipo, number_node, _patch, dot):
    while _Queue:
        if tipo == 0:
            node = _Queue.pop() #en profundidad
        elif tipo == 1:
            node = _Queue.pop(0) # anchura
        number_node += 1
        if node != meta: 
            temp_list = Generar_states(node, _patch, dot)[:]
            print("Generate", temp_list)
            _Queue.extend(temp_list.copy())      
        elif node == meta:
            print("End......")
            break 



dot = graphviz.Digraph(comment='Arbol de decisión')
algoritmo(0, number_node, _patch, dot) #LLAMAMO EL METEDO PRINCIPAL. 
dot.render()
import graphviz
import os
os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin'
import Drawpy
n = 0
number_node = 0
side1 = "left"
side2 = "right"

start = {"farmer":side1, "wolf":side1, "goat":side1, "cabbage":side1}
meta = {"farmer":side2, "wolf":side2, "goat":side2, "cabbage":side2}

_Queue =[]
notrepet =[]
_patch  = []

notrepet.append(start)
_Queue.append(start)
   

def validate_state(state):
    if state["wolf"] == state["goat"] and state["wolf"] != state["farmer"]:
        return False
    elif state["goat"] == state["cabbage"] and state["cabbage"] != state["farmer"]:
        return False
    else:
        return True

def Generar_states(state_actual, _patch ,dot):
    global n
    list_state = []
    new_state = dict(state_actual)
    _nodes = [w[0] for w in _patch.copy()] # se supone que obtengo todas las llaves de los dict
    if state_actual not in _nodes: #si aun no se ah creado el nodo para ese estado
        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 0)
    if state_actual["farmer"] == side2:  
        new_state["farmer"] = side1  
        if validate_state(new_state) and new_state not in notrepet:
            list_state.append(dict(new_state)) 
            notrepet.append(dict(new_state))
            n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)

        for k, v in new_state.items():
            if k != "farmer":
                if v == side2: 
                    new_state[k] = side1  
                    if validate_state(new_state) and new_state not in notrepet:
                        list_state.append(dict(new_state))
                        notrepet.append(dict(new_state))
                        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)
                    new_state[k] = side2 
    else: 
        new_state["farmer"] = side2
        for k, v in new_state.items():
            if k != "farmer":
                if v == side1:
                    new_state[k] = side2
                    if validate_state(new_state) and new_state not in notrepet:
                        list_state.append(dict(new_state))
                        notrepet.append(dict(new_state))
                        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)
                    new_state[k] = side1
    return list_state

#Tipo: (0) en profundidad (1) anchura, (2)profundidad limitada
def algoritmo(tipo, number_node, _patch, dot):
    while _Queue:
        if tipo == 0:
            node = _Queue.pop() #en profundidad
        elif tipo == 1:
            node = _Queue.pop(0) # anchura
        number_node += 1
        if node != meta: 
            temp_list = Generar_states(node, _patch, dot)[:]
            print("Generate", temp_list)
            _Queue.extend(temp_list.copy())      
        elif node == meta:
            print("End......")
            break 



dot = graphviz.Digraph(comment='Arbol de decisión')
algoritmo(0, number_node, _patch, dot) #LLAMAMO EL METEDO PRINCIPAL. 
dot.render()
import graphviz
import os
os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin'
import Drawpy
n = 0

side1 = "left"
side2 = "right"

start = {"farmer":side1, "wolf":side1, "goat":side1, "cabbage":side1}
meta = {"farmer":side2, "wolf":side2, "goat":side2, "cabbage":side2}

_Queue =[]
notrepet =[]
_patch  = []

notrepet.append(start)
_Queue.append(start)
   

def validate_state(state):
    if state["wolf"] == state["goat"] and state["wolf"] != state["farmer"]:
        return False
    elif state["goat"] == state["cabbage"] and state["cabbage"] != state["farmer"]:
        return False
    else:
        return True

def Generar_states(state_actual, _patch ,dot):
    global n
    list_state = []
    new_state = dict(state_actual)
    _nodes = [w[0] for w in _patch.copy()] # se supone que obtengo todas las llaves de los dict
    if state_actual not in _nodes: #si aun no se ah creado el nodo para ese estado
        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 0)
    if state_actual["farmer"] == side2:  
        new_state["farmer"] = side1  
        if validate_state(new_state) and new_state not in notrepet:
            list_state.append(dict(new_state)) 
            notrepet.append(dict(new_state))
            n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)

        for k, v in new_state.items():
            if k != "farmer":
                if v == side2: 
                    new_state[k] = side1  
                    if validate_state(new_state) and new_state not in notrepet:
                        list_state.append(dict(new_state))
                        notrepet.append(dict(new_state))
                        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)
                    new_state[k] = side2 
    else: 
        new_state["farmer"] = side2
        for k, v in new_state.items():
            if k != "farmer":
                if v == side1:
                    new_state[k] = side2
                    if validate_state(new_state) and new_state not in notrepet:
                        list_state.append(dict(new_state))
                        notrepet.append(dict(new_state))
                        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)
                    new_state[k] = side1
    return list_state

#Tipo: (0) en profundidad (1) anchura, (2)profundidad limitada
def algoritmo(tipo, _patch, dot):
    while _Queue:
        if tipo == 0:
            node = _Queue.pop() #en profundidad
        elif tipo == 1:
            node = _Queue.pop(0) # anchura
        
        if node != meta: 
            temp_list = Generar_states(node, _patch, dot)[:]
            print("Generate", temp_list)
            _Queue.extend(temp_list.copy())      
        elif node == meta:
            print("End......")
            break 



dot = graphviz.Digraph(comment='Arbol de decisión')
algoritmo(0, _patch, dot) #LLAMAMO EL METEDO PRINCIPAL. 
dot.render()
se añadieron 44 caracteres en el cuerpo
Origen Enlace
def Make_Node(state1, state2, id_node, _patch, dot, hijo_padre):
    if hijo_padre == 0: # si el nodo es padre
        id_node += 1
        _patch.append((dict(state1), id_node)) #vamos guardando el nodo y sus id's
        dot.node(str(id_node), estado(dict(state1)))
    elif hijo_padre == 1: #si se trata de un nodo hijo debe creear
        id_node +=1
        _patch.append((dict(state2), id_node))
        dot.node(str(id_node), estado(dict(state2)))
        dot.edge(str([ w[1] for w in _patch if w[0] == state1].pop()), str(id_node))

    return id_node, _patch, dot
def Make_Node(state1, state2, id_node, _patch, dot, hijo_padre):
if hijo_padre == 0: # si el nodo es padre
    id_node += 1
    _patch.append((dict(state1), id_node)) #vamos guardando el nodo y sus id's
    dot.node(str(id_node), estado(dict(state1)))
elif hijo_padre == 1: #si se trata de un nodo hijo debe creear
    id_node +=1
    _patch.append((dict(state2), id_node))
    dot.node(str(id_node), estado(dict(state2)))
    dot.edge(str([ w[1] for w in _patch if w[0] == state1].pop()), str(id_node))

return id_node, _patch, dot
def Make_Node(state1, state2, id_node, _patch, dot, hijo_padre):
    if hijo_padre == 0: # si el nodo es padre
        id_node += 1
        _patch.append((dict(state1), id_node)) #vamos guardando el nodo y sus id's
        dot.node(str(id_node), estado(dict(state1)))
    elif hijo_padre == 1: #si se trata de un nodo hijo debe creear
        id_node +=1
        _patch.append((dict(state2), id_node))
        dot.node(str(id_node), estado(dict(state2)))
        dot.edge(str([ w[1] for w in _patch if w[0] == state1].pop()), str(id_node))

    return id_node, _patch, dot
Origen Enlace

Con la ayuda abulafia puede hacer lo que buscaba, el algoritmo funciona bien, solo que no guardaba bien el árbol y ni el recorrido, pero ya esta corregido o al menos ya logre que funcionara como buscaba.

Para la búsqueda en anchura y profundidad hice esto, espero que a alguien mas le sea útil al menos como idea.

import graphviz
import os
os.environ["PATH"] += os.pathsep + 'C:/Program Files (x86)/Graphviz2.38/bin'
import Drawpy
n = 0
number_node = 0
side1 = "left"
side2 = "right"

start = {"farmer":side1, "wolf":side1, "goat":side1, "cabbage":side1}
meta = {"farmer":side2, "wolf":side2, "goat":side2, "cabbage":side2}

_Queue =[]
notrepet =[]
_patch  = []

notrepet.append(start)
_Queue.append(start)
   

def validate_state(state):
    if state["wolf"] == state["goat"] and state["wolf"] != state["farmer"]:
        return False
    elif state["goat"] == state["cabbage"] and state["cabbage"] != state["farmer"]:
        return False
    else:
        return True

def Generar_states(state_actual, _patch ,dot):
    global n
    list_state = []
    new_state = dict(state_actual)
    _nodes = [w[0] for w in _patch.copy()] # se supone que obtengo todas las llaves de los dict
    if state_actual not in _nodes: #si aun no se ah creado el nodo para ese estado
        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 0)
    if state_actual["farmer"] == side2:  
        new_state["farmer"] = side1  
        if validate_state(new_state) and new_state not in notrepet:
            list_state.append(dict(new_state)) 
            notrepet.append(dict(new_state))
            n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)

        for k, v in new_state.items():
            if k != "farmer":
                if v == side2: 
                    new_state[k] = side1  
                    if validate_state(new_state) and new_state not in notrepet:
                        list_state.append(dict(new_state))
                        notrepet.append(dict(new_state))
                        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)
                    new_state[k] = side2 
    else: 
        new_state["farmer"] = side2
        for k, v in new_state.items():
            if k != "farmer":
                if v == side1:
                    new_state[k] = side2
                    if validate_state(new_state) and new_state not in notrepet:
                        list_state.append(dict(new_state))
                        notrepet.append(dict(new_state))
                        n, _patch, dot = Drawpy.Make_Node(state_actual, new_state, n, _patch, dot, 1)
                    new_state[k] = side1
    return list_state

#Tipo: (0) en profundidad (1) anchura, (2)profundidad limitada
def algoritmo(tipo, number_node, _patch, dot):
    while _Queue:
        if tipo == 0:
            node = _Queue.pop() #en profundidad
        elif tipo == 1:
            node = _Queue.pop(0) # anchura
        number_node += 1
        if node != meta: 
            temp_list = Generar_states(node, _patch, dot)[:]
            print("Generate", temp_list)
            _Queue.extend(temp_list.copy())      
        elif node == meta:
            print("End......")
            break 



dot = graphviz.Digraph(comment='Arbol de decisión')
algoritmo(0, number_node, _patch, dot) #LLAMAMO EL METEDO PRINCIPAL. 
dot.render()

La funcion

Make_node() es esta

def Make_Node(state1, state2, id_node, _patch, dot, hijo_padre):
if hijo_padre == 0: # si el nodo es padre
    id_node += 1
    _patch.append((dict(state1), id_node)) #vamos guardando el nodo y sus id's
    dot.node(str(id_node), estado(dict(state1)))
elif hijo_padre == 1: #si se trata de un nodo hijo debe creear
    id_node +=1
    _patch.append((dict(state2), id_node))
    dot.node(str(id_node), estado(dict(state2)))
    dot.edge(str([ w[1] for w in _patch if w[0] == state1].pop()), str(id_node))

return id_node, _patch, dot

Es muy probable que se puede hacer de mejor manera y seguramente tenga varios detalles, me escudo en que aun soy nuevo en la programación y soy mas nuevo aun en python :p