Come implementare una ricerca per ampiezza fino a una certa profondità?

Question

Capisco e posso facilmente implementare BFS.

La mia domanda è, come possiamo rendere questo BFS limitato ad una certa profondità? Supponiamo, ho solo bisogno di andare a 10 livelli di profondità.

Answer 1

È possibile farlo con overhead spazio costante.

BFS ha la proprietà che i nodi non visitati nella coda hanno tutti profondità che non diminuiscono mai e aumentano di un massimo di 1. Quindi mentre leggete i nodi dalla coda BFS, potete tenere traccia della profondità attuale in un singolo depth variabile, che è inizialmente 0.

Tutto quello che devi fare è registrare quale nodo nella coda corrisponde al successivo aumento di profondità. È possibile farlo semplicemente utilizzando una variabile timeToDepthIncrease per registrare il numero di elementi già presenti nella coda quando si inserisce questo nodo e diminuendo questo contatore ogni volta che si inserisce un nodo dalla coda.

Quando si raggiunge lo zero, il nodo successivo si pop dalla coda sarà a un nuovo, più grande (da 1) la profondità, in modo da:

• Incremento depth
• Impostare pendingDepthIncrease true

Ogni volta che si preme un nodo figlio sulla coda, verificare innanzitutto se pendingDepthIncrease è vero. Se lo è, questo nodo avrà una profondità maggiore, quindi imposta timeToDepthIncrease sul numero di nodi nella coda prima di eseguirlo, quindi reimposta pendingDepthIncrease su falso.

Infine, interrompere quando depth supera la profondità desiderata! Ogni nodo non visitato che potrebbe apparire in seguito deve essere a questa profondità o maggiore.

[EDIT:. Grazie commentatore Keyser]

Answer 2

Per i lettori futuri, guardare a questo esempio dell'algoritmo sopra descritto. Questa implementazione monitorerà quanti nodi contiene il seguente livello. In tal modo, l'implementazione è in grado di tenere traccia della profondità attuale.

void breadthFirst(Node parent, int maxDepth) { 

    if(maxDepth < 0) { 
    return; 
    } 

    Queue<Node> nodeQueue = new ArrayDeque<Node>(); 
    nodeQueue.add(parent); 

    int currentDepth = 0, 
     elementsToDepthIncrease = 1, 
     nextElementsToDepthIncrease = 0; 

    while (!nodeQueue.isEmpty()) { 
    Node current = nodeQueue.poll(); 
    process(current); 
    nextElementsToDepthIncrease += current.numberOfChildren(); 
    if (--elementsToDepthIncrease == 0) { 
     if (++currentDepth > maxDepth) return; 
     elementsToDepthIncrease = nextElementsToDepthIncrease; 
     nextElementsToDepthIncrease = 0; 
    } 
    for (Node child : current.children()) { 
     nodeQueue.add(child); 
    } 
    } 

} 

void process(Node node) { 
    // Do your own processing here. All nodes handed to 
    // this method will be within the specified depth limit. 
}  

Answer 3

Questo funziona. Supponendo che la bandiera visitata non sia presente nel nodo. Se isVisited è disponibile, non c'è bisogno di tracker Map.

// k is depth, result should not contain initialNode. 
public static Collection<Node> bfsWithK_Depth(Node initialNode, int k) { 

    if (initialNode == null || k <= 0) { 
     return new ArrayList<>(); 
    } 

    Queue<Node> q = new LinkedList<>(); 
    q.add(initialNode); 
    Map<Node, Node> tracker = new HashMap(); // no need if there is visited flag. 
    Collection<Node> result = new ArrayList<>(); 

    while (!q.isEmpty()) { // Q will be filled only with eligible nodes 
     --k ; 
     Node node = q.remove(); 
     List<Node> neighbor = node.getNeighbor(); 
     for (Node n : neighbor) { 
      if (tracker.get(n) == null && k > 0) { 
       q.add(n); 
      } 
      if (tracker.get(n) == null) { 
       tracker.put(n, n); 
       result.add(n); // visit this node 
      } 
     } 

    } 
    return result; 
} 

Answer 4

Se non si desidera avere un nodo di classe (e aggiungere una profondità variabile per il nodo) allora si può avere due mappe per la distanza e visitedNodes o una matrice 2D in cui ogni riga è un nodo e column1: la profondità , column2: visited. Naturalmente è possibile tenere traccia di entrambi con uno map<Node,Depth> (dove Nodo è un'istanza della classe o int, String ecc. E Depth è un int che rappresenta la Profondità del Nodo dal nodo radice). se la mappa contiene un nodo (costo O (1)), viene visitato, se non procede e lo aggiunge alla mappa con la profondità del nodo corrente +1.

public static void BfsToDepth(graph graphDb, Node rootNode, int depth) { 
    if(depth<1) 
     return; 
    Queue<Node> queue = new LinkedList<>(); 
    ResourceIterator<Node> nodesIterator = graphDb.getAllNodes().iterator(); 
    LinkedHashMap<Node, Boolean> visited = new LinkedHashMap<>(); 
    LinkedHashMap<Node, Integer> distance = new LinkedHashMap<>(); 
    // Start: Bfs Init Step 
    if (nodesIterator.hasNext() == true) { 
     while (nodesIterator.hasNext()) { 
      Node currentNode = nodesIterator.next(); 
      visited.put(currentNode, false); 
      distance.put(currentNode, Integer.MAX_VALUE); 
     } 
    } else { 
     System.out.println("No nodes found"); 
    } 
    // End: Bfs Init Step 

    distance.put(rootNode, 0); 
    visited.put(rootNode, true); 
    queue.add(rootNode); 
    Node current = null; 

    while (queue.isEmpty() == false) { 
     current = queue.poll(); 
     if (distance.get(current) <= depth) { 
      Iterator<Relationship> relationships = current.getRelationships().iterator(); 
      if (relationships.hasNext() == true) { 
       while (relationships.hasNext()) { 
        Relationship relationship = relationships.next(); 
        Node adjacent = relationship.getOtherNode(current); 

        if (visited.get(adjacent) == false) { 
         /*if you want to print the distance of each node from root then 
         System.out.println("len: "+ (distance.get(current) + 1)+" to: "+ adjacent);*/ 
         distance.put(adjacent, (distance.get(current) + 1)); 
         visited.put(adjacent, true); 
         queue.add(adjacent); 
        } 
       } 
      } 
     } 
    } 
} 

Answer 5

L'Idea facile per tenere traccia della profondità è di aggiungere "NULL" alla coda ogni volta che vai a livello profondo. Non appena esegui il polling di un valore nullo dalla coda, aumenta il tuo contatore di livelli di 1 e aggiungi un altro 'nullo' alla coda. Se ottieni due null consecutivi puoi uscire dal ciclo.

q.offer(user); 
q.offer(null); 

user.setVisited(true); 

while(!q.isEmpty()){ 

    User userFromQ = q.poll(); 

    if(userFromQ == null){ 
     level++; 
     q.offer(null); 
     if(q.peek()==null) 
      break; 
     else 
      continue; 
    }