Làm cách nào để thực hiện tìm kiếm đầu tiên trên một chiều sâu nhất định?

Question

Tôi hiểu và có thể dễ dàng triển khai BFS.

Câu hỏi của tôi là, làm cách nào để BFS này được giới hạn ở một độ sâu nhất định? Giả sử, tôi chỉ cần đi sâu 10 cấp.

Answer 1

Bạn có thể thực hiện việc này với chi phí không gian cố định.

BFS có thuộc tính mà các nút không được liệt kê trong hàng đợi có độ sâu không bao giờ giảm và tăng tối đa 1. Vì vậy, khi bạn đọc các nút từ hàng đợi BFS, bạn có thể theo dõi độ sâu hiện tại trong một đơn depth biến, ban đầu là 0.

Tất cả những gì bạn cần làm là ghi lại nút nào trong hàng đợi tương ứng với độ sâu tăng tiếp theo. Bạn có thể thực hiện điều này đơn giản bằng cách sử dụng biến số timeToDepthIncrease để ghi lại số lượng phần tử đã có trong hàng đợi khi bạn chèn nút này và giảm bộ đếm này bất cứ khi nào bạn bật nút từ hàng đợi.

Khi nó đạt đến số không, nút tiếp theo bạn bật khỏi hàng đợi sẽ có mặt tại một mới, lớn hơn (1) chiều sâu, vì vậy:

• Tăng depth
• Đặt pendingDepthIncrease true

Bất cứ khi nào bạn nhấn nút con trên hàng đợi, trước tiên hãy kiểm tra xem pendingDepthIncrease có đúng không. Nếu có, nút này sẽ có độ sâu lớn hơn, do đó, hãy đặt timeToDepthIncrease thành số lượng nút trong hàng đợi trước khi bạn đẩy nó và đặt lại pendingDepthIncrease thành sai.

Cuối cùng, dừng khi depth vượt quá độ sâu mong muốn! Mỗi nút không được đề xuất có thể xuất hiện sau này phải ở độ sâu này hoặc cao hơn.

[EDIT:. Cảm ơn commenter keyser]

Answer 2

Đối với độc giả trong tương lai, hãy nhìn vào ví dụ này của thuật toán mô tả ở trên. Việc triển khai này sẽ giám sát số lượng nút mà cấp sau chứa. Khi làm như vậy, việc thực hiện có thể theo dõi độ sâu hiện tại.

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

Tác phẩm này hoạt động. Giả sử rằng cờ truy cập không có trong nút. Nếu isVisited có sẵn, sau đó không cần phải theo dõi Bản đồ.

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

Nếu bạn không muốn có một nút lớp (và thêm độ sâu biến để nút của bạn) sau đó bạn có thể có hai bản đồ cho khoảng cách và visitedNodes hoặc một mảng 2ngày nơi mỗi hàng là một nút và column1: sâu , cột2: đã truy cập. Tất nhiên bạn có thể theo dõi cả hai với một map<Node,Depth> (trong đó Node là một thể hiện của lớp hoặc int, String vv và Độ sâu là một int đại diện cho Độ sâu của Nút từ nút gốc). nếu bản đồ có chứa một nút (O (1) chi phí) thì nó được truy cập, nếu không được tiếp tục và thêm nó vào bản đồ với độ sâu của nút hiện tại +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

Ý tưởng dễ dàng để theo dõi chiều sâu là thêm "NULL" vào Hàng đợi mỗi lần bạn đi sâu cấp. Ngay khi bạn thăm dò ý kiến ​​một null từ hàng đợi, Tăng mức truy cập của bạn bằng 1 và thêm một 'null' vào Hàng đợi. Nếu bạn nhận được hai nulls liên tiếp, bạn có thể thoát khỏi vòng lặp.

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