Código de Python - Algoritmo de búsqueda de elemento en profundidad

Imágen de perfil
Val: 1.437
Oro
Ha mantenido su posición en Python (en relación al último mes)
Gráfica de Python

Algoritmo de búsqueda de elemento en profundidadgráfica de visualizaciones


Python

estrellaestrellaestrellaestrellaestrella(5)
Actualizado el 28 de Agosto del 2018 por xve (Publicado el 17 de Julio del 2018)
6.842 visualizaciones desde el 17 de Julio del 2018
Este código muestra como encontrar un elemento en profundidad de forma recursiva utilizando el algoritmo de búsqueda de elemento en profundidad.

arbol-busqueda


La función devuelve el camino para llegar desde un punto inicial al punto final.

Requerimientos

Python 3

Versión 1
estrellaestrellaestrellaestrellaestrella(5)

Actualizado el 15 de Agosto del 2018 (Publicado el 17 de Julio del 2018)gráfica de visualizaciones de la versión: Versión 1
6.843 visualizaciones desde el 17 de Julio del 2018
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
"""
Cada elemento de este diccionario contiene una posicion y como valor tiene
el nombre de su elemento padre en el arbol

                  a
               /  |  \
              b   c   d
             / \  |  / \
            e   f h i   j
            |   | |     |
            k   m g     l
               / \
              n   o
"""
valores={
    "b":"a",
    "c":"a",
    "d":"a",
    "e":"b",
    "f":"b",
    "h":"c",
    "i":"d",
    "j":"d",
    "k":"e",
    "m":"f",
    "g":"h",
    "l":"j",
    "n":"m",
    "o":"m"
}
 
# variable que contiene el camino recorrido hasta llegar a la letra a buscar
camino=[]
 
def buscar(inicio,valorBuscar):
    """
    Funcion recursiva para buscar en profundidad
    Tiene que recibir:
        - el valor inicial donde empezar a buscar
        - el valor a buscar en su estructura
    Devuelve el valor a buscar o 0 si no lo encuentra
    """
    camino.append(inicio)
 
    # si encontramos el elemento, lo devolvemos
    if inicio==valorBuscar:
        return valorBuscar
 
    # recorremos todos los elementos en busca del valor de inicio
    for k,v in valores.items():
 
        # si el valor del elemento tiene como padre al valor de inicio
        if v==inicio:
 
            # llamamos a la función recursivamente enviando el nuevo padre
            result=buscar(k,valorBuscar)
 
            # si hemos recibido algun resultado es que hemos encontrado el
            # elemento que buscamos
            if result:
                return result
 
    camino.pop()
 
    # si llegamos aqui, es que hemos llegado al final de una profundidad
    return 0
 
result=buscar("a","o")
if result:
    print(camino)
else:
    print("no encontrado")



Comentarios sobre la versión: Versión 1 (5)

Imágen de perfil
24 de Julio del 2018
estrellaestrellaestrellaestrellaestrella
Gracias Bro
Responder
Guerlin P
16 de Agosto del 2018
estrellaestrellaestrellaestrellaestrella
Este código sirve para buscar cualquier elemento dentro de un archivo o fuera del mismo en el disco duro en Windows.
Será que lo pueden hacer ejecutable?
Responder
Jorge
28 de Agosto del 2018
estrellaestrellaestrellaestrellaestrella
Saludos a todos,

Imagino que la idea de este ejercicio es encontrar la ruta desde inicio hasta valorBuscar.

Si es el caso, hay un detalle con esta versión: En algunos casos incluye en los resultados nodos que no forman parte de la ruta. La razón es que busca siempre en todos los elementos del diccionario valores.

Por ejemplo, esta versión del código da los siguientes resultados;
buscar('a','o') = ['a', 'b', 'f', 'm', 'o']
buscar('a','g') = ['a', 'b', 'f', 'm', 'o', 'a', 'c', 'h', 'g']
buscar('a','l') = ['a', 'b', 'f', 'm', 'o', 'a', 'c', 'h', 'g', 'a', 'd', 'j', 'l']
buscar('c','g') = ['a', 'b', 'f', 'm', 'o', 'a', 'c', 'h', 'g', 'a', 'd', 'j', 'l', 'c', 'h', 'g']
buscar('o','g') = no encontrado
buscar('b','g') = no encontrado
buscar('x','y') = no encontrado


Redefiniendo la funcion buscar de la siguiente manera:
def buscar( inicio , valorBuscar ):
# Encontrar todos los nodos cuyo padre es inicio
children = [k for k,v in valores.items() if v == inicio]
# Si inicio tiene hijos
if children :
# Si el valorBuscar es hijo de inicio
if valorBuscar in children :
# Devolver una lista con ambos valores como elementos
return [inicio,valorBuscar]
# de lo contrario buscar en cada nodo hijo
else :
for child in children :
# de manera recursiva
nextNode = buscar( child , valorBuscar )
if nextNode :
# hasta encontrar valorBuscar
return [inicio]+nextNode
# y retornar None si valorBucar no es concontrado en el árbol de ninguno de sus hijos
return None
# Si inicio no tiene hijos no hay camino a valorBuscar
else :
return None

Estos son los resultados:
buscar('a','o') = ['a', 'b', 'f', 'm', 'o']
buscar('a','g') = ['a', 'c', 'h', 'g']
buscar('a','l') = ['a', 'd', 'j', 'l']
buscar('c','g') = ['c', 'h', 'g']
buscar('o','g') = no encontrado
buscar('b','g') = no encontrado
buscar('x','y') = no encontrado

Aquí la idea es buscar solo en los nodos hijos de inicio, ignorando el resto de los nodos.


Luego hay otra cuestión práctica para el caso de los diccionarios: Cada key es única, por lo que podría determinarse directamente si inicio y valorBuscar existen como key. Y también si solo existen como value en el diccionario valores, en cuyo caso sabemos que se trata del Nodo al tope del árbol.

Suponiendo que valorBuscar pertenece al arbol de inicio, se puede hacer la búqueda en sentido contrario, es decir desde valorBuscar hasta inicio:
Esta búsqueda devuelve una ruta invertida, la cual puede luego ser reordenada.

def RutaEntreNodos( valorBuscar , inicio ) :
camino = []
actual = valorBuscar
while actual in valores.keys() :
padre = valores[actual]
camino.append(actual)
if actual == inicio :
return camino
actual=padre
# El elemento al tope del arbol no es un key en el diccionario valores porque no tiene un nodo padre. Solo aparece en el diccionario como value
if actual in valores.values() :
camino.append(actual)
# Para asegurarnos que valorBuscar sea el último elemento del camino = inicio
if actual == inicio :
return camino
else :
return None

Y por supuesto, se podría ampliar para establecer una ruta entre dos nodos aunque no estén en la misma rama del árbol.

PD: La imagen 5b4debf423386-arbol-busqueda-en-profundidad.png tiene un error. El elemento M aparece repetido. El error está en A-C-H-M que deb ser cambiado a A-C-H-G.
Responder
Imágen de perfil
28 de Agosto del 2018
estrellaestrellaestrellaestrellaestrella
Gracias Jorge, pero a mi no me da tus resultados...
buscar('a','g') = ['a', 'c', 'h', 'g']
buscar('a','l') = ['a', 'd', 'i']
buscar('c','g') = ['c', 'h', 'g']

he actualizado la imagen, gracias por comentarlo!!!
Responder
Jorge
28 de Agosto del 2018
estrellaestrellaestrellaestrellaestrella
Gracias por respder.

Tienes razón.
Ya me di cuenta de mi error.
Ejecuté las pruebas, una detrás de la otra, en el mismo script, y por supuesto el contenido de camino seguía manteniendo los valores de la búsqueda anterior.

Saludos y disculpa mi torpeza.
Responder

Comentar la versión: Versión 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad

http://lwp-l.com/s4722