1

estoy implementando un método de búsqueda en profundidad en lenguaje Python. Lo estoy utilizando para hallar el camino óptimo entre dos nodos de un grafo, el problema está en que usando mi código, solamente consigo obtener el primer nodo del grafo.

Sé que el algoritmo crea una lista de caminos pendientes y que, hasta que llegue al nodo final, expande el primer camino, pero no consigo obtener todo el camino. Dejo mi código para saber si tengo algún elemento erróneo:

Código:

def busqueda_profundidad(self, origen, fin):
    cp = [[origen]] # camino pendiente
    while cp:
        print(cp)
        if not cp: 
            return False
        if cp[0][0] == fin:
            return list(reversed(cp[0][0]))
        expansion = self.expandir(cp[0][0])
        cp = expansion + cp[1:]

def expandir(self, camino):
    expansion = self.sucesores(camino[0])
    nuevos = []
    for n in expansion:
        if not n in camino:
            nuevos.append([n] + camino)
    return nuevos

def sucesores(self, station):
    """Devuelve la lista de posibles sucesores"""
    return sorted(list(set(self.model[nodo])))
1
  • 1
    El código debería ser lo más completo posible para que podamos darnos una idea y estaría bien tener el caso que has probado para poder probarlo nosotros. Se puede suponer que son métodos en una clase, pero hay variables que no están definidas (eg: nodo en la última línea o self.model). Commented el 28 dic. 2016 a las 1:00

1 respuesta 1

0

No has suministrado suficiente información para encontrar el error en tu código, pero por si te sirve de algo aquí tienes una solución.

Dado un grafo no dirigido con N nodos, numerados con enteros desde 0 a N-1:

introducir la descripción de la imagen aquí

con su lista de adyacencia:

adyacencia = [
    [1, 3, 4],
    [0, 2, 3, 4],
    [1, 4],
    [0, 1],
    [0, 1, 2]]

Una implementación general no recursiva del algoritmo:

class Grafo(object):

    def __init__(self, adyacencia):
        self.ady = adyacencia
        self._init_grafo(-1)

    def _init_grafo(self, inicio):
        self.encontrado = [False for n in self.ady]
        self.procesado = [False for n in self.ady]
        self.padre = [-1 for n in self.ady]
        self.inicio = inicio

    def profundidad(self, inicio):
        """Usar busqueda en profundidad desde inicio a todo el grafo"""
        self._init_grafo(inicio)
        q = [inicio]
        self.encontrado[inicio] = True

        while q:
            v = q.pop()
            self.procesado[v] = True

            for vecino in self.ady[v]:
                if not self.encontrado[vecino]:
                    q.append(vecino)
                    self.encontrado[vecino] = True
                    self.padre[vecino] = v

    def construir_camino(self, destino):
        """Devuelve el camino entre los vertices inicio y destino"""
        if self.padre[destino] == -1 or self.inicio == -1:
            return None

        camino = [destino,]
        p = destino
        while p != self.inicio:
            camino.append(self.padre[p])
            p = self.padre[p]

        return camino

Para ejecutarlo:

inicio = 3
destino = 2
g = Grafo(adyacencia)
g.profundidad(inicio)
camino = g.construir_camino(destino)

Por supuesto en la mayoría de los casos no es necesario calcular la ruta a todo los vértices, y puedes detener la búsqueda en cuanto llegues al destino, pero eso lo vas a tener que solucionar tu.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.