Código de Python - Algorimto de búsqueda de elemento en ancho de banda

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

Algorimto de búsqueda de elemento en ancho de bandagráfica de visualizaciones


Python

Publicado el 3 de Agosto del 2018 por xve
1.569 visualizaciones desde el 3 de Agosto del 2018
Este código muestra como encontrar un elemento en anchura de forma recursiva utilizando el algoritmo de búsqueda de elemento en ancho de banda.

arbol-busqueda-en-anchura


El algoritmo devuelve el camino que ha utilizado y el numero de iteraciones.

Requerimientos

Python 3

Versión 1

Publicado el 3 de Agosto del 2018gráfica de visualizaciones de la versión: Versión 1
1.570 visualizaciones desde el 3 de Agosto 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
73
74
75
76
77
78
79
80
81
82
83
"""
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 que recorre el algoritmo
camino=[]
 
# variable que contiene la cola de elementos a revisar
# First In, First Out
fifo=[]
 
def buscar(inicio,valorBuscar,iteraciones):
    """
    Funcion recursiva para buscar en anchura
    Tiene que recibir:
        - el valor inicial donde empezar a buscar
        - el valor a buscar en su estructura
        - el contador de interaciones
    Devuelve True o False y el valor de interaciones realizadas para encontrar
    el elemento
    """
 
    camino.append(inicio)
 
    # Si encontramos el elemento, lo devolvemos
    if inicio==valorBuscar:
        return (True,iteraciones)
 
    # Añadimos los elementos al fifo
    fifoAdd(inicio)
 
    # Si no hay elementos en el fifo, es que hemos llegado al final y no ha
    # encontrado el elemento
    if len(fifo)==0:
        return (False,iteraciones)
 
    # Llamamos nuevamente a la función pasando el primer elemento añadido a la
    # fifo y aumentando la variable de la interacion
    return buscar(fifo.pop(0),valorBuscar,iteraciones+1)
 
def fifoAdd(inicio):
    """
    Función para buscar los elementos hijos a un elemento dado y añadirlos
    a la variable fifo
    """
    for k,v in valores.items():
        if v==inicio:
            fifo.append(k)
 
resultado,iteraciones=buscar("a","f",1)
if resultado:
    print("Ha encontrado el valor en {} iteraciones".format(iteraciones))
else:
    print("No se ha encontrado")
print("El camino que ha realizado ha sido: {}".format(camino))



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


No hay comentarios
 

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/s4740