Jak zaimplementować szerokość pierwszego wyszukiwania do określonej głębokości?

Question

Rozumiem i mogę łatwo wdrożyć BFS.

Moje pytanie brzmi: jak możemy ograniczyć BFS do określonej głębokości? Przypuśćmy, że muszę po prostu zejść na 10 poziom.

Answer 1

Możesz to zrobić ze stałym narzutem.

BFS ma właściwość, że nieodwiedzone węzły w kolejce mają wszystkie głębokości, które nigdy nie ulegają zmniejszeniu, i zwiększają się co najwyżej 1. Tak jak czytasz węzły z kolejki BFS, możesz śledzić bieżącą głębokość w pojedynczej depth zmienna, która początkowo wynosi 0.

Wszystko, co musisz zrobić, to zarejestrować, który węzeł w kolejce odpowiada następnemu zwiększeniu głębokości. Możesz to zrobić, używając zmiennej timeToDepthIncrease do zapisania liczby elementów, które są już w kolejce podczas wstawiania tego węzła i zmniejszania tego licznika za każdym razem, gdy wysuniesz węzeł z kolejki.

Kiedy osiągnie zero, następny węzeł pop z kolejki będzie na nowy, większy (o 1) głębokość, więc:

• Przyrost depth
• Ustaw pendingDepthIncrease true

Po każdym naciśnięciu węzła podrzędnego w kolejce najpierw sprawdź, czy pendingDepthIncrease ma wartość true. Jeśli tak, to węzeł będzie miał większą głębokość, więc ustaw timeToDepthIncrease na liczbę węzłów w kolejce przed naciśnięciem go i zresetuj pendingDepthIncrease na wartość false.

Na koniec zatrzymaj się, gdy depth przekroczy żądaną głębokość! Każdy niezweryfikowany węzeł, który może pojawić się później, musi znajdować się na tej głębokości lub większej.

[EDIT:. Dzięki komentator Keyser]

Answer 2

Dla przyszłych czytelników, spojrzeć na ten przykład algorytmu opisanego powyżej. Ta implementacja będzie monitorować, ile węzłów zawiera poniższy poziom. W ten sposób implementacja jest w stanie śledzić bieżącą głębokość.

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

To działa. Zakładając, że odwiedzona flaga nie znajduje się w węźle. Jeśli opcja isVisited jest dostępna, nie ma potrzeby śledzenia mapy.

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

Jeśli nie chcesz mieć węzeł klasy (i dodać zmienną głębokość do węzła), a następnie można mieć dwie mapy na odległość i visitedNodes lub tablicy 2D, gdzie każdy wiersz jest węzłem i kolumna1: głębokość , column2: odwiedzony. Oczywiście można śledzić oba z jednym map<Node,Depth> (gdzie Węzeł jest instancją klasy lub int, ciągiem itp., A Głębokość jest int, które reprezentują głębokość węzła od węzła głównego). jeśli mapa zawiera węzeł (koszt O (1)), to jest odwiedzana, jeśli nie kontynuować i dodać ją do mapy z głębokością bieżącego węzła +1.

Answer 5

Łatwym pomysłem do śledzenia głębokości jest dodanie "NULL" do kolejki za każdym razem, gdy idziesz na głęboką głębię. Jak tylko odpytasz wartość zerową z kolejki, zwiększ swój licznik poziomu o 1 i dodaj kolejną "pustkę" do kolejki. Jeśli otrzymasz dwie kolejne wartości zerowe, możesz wyjść z pętli.

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; 
    }