चौड़ाई पहली खोज के साथ भूलभुलैया

Question

क्या कोई बता सकता है कि मैं चौड़ाई पहली खोज का उपयोग करके भूलभुलैया कैसे हल कर सकता हूं? मुझे भूलभुलैया के माध्यम से सबसे छोटा रास्ता खोजने के लिए पहली बार चौड़ाई का उपयोग करने की ज़रूरत है, लेकिन मैं बहुत उलझन में हूं। ,

void breadth_first_search(tree T) { 
    queue!; 
    node u, v; 

    initialize(Q); 
    v = root of T; 
    visit v; 
    enqueue(Q, v); 

    while (!empty(Q)) { 
    dequeue(Q, v); 
    for (each child u of v) { 
     visit u; 
     enqueue(Q, u); 
    } 
    } 
} 

तो अगर मुझे लगता है कि एक 2 डी मैट्रिक्स में संग्रहीत किया जाता है एक उलझन है, "रूट" (यानी प्रारंभिक बिंदु) है में होने जा रहा:

यह मेरी पुस्तक से छद्म कोड है maze[x][y]?

Answer 1

लघु जवाब: हां

स्पष्टीकरण:

छद्म कोड एक पेड़ की पत्ती के लिए एक मार्ग के रूप में भूलभुलैया के माध्यम से पथ का प्रतिनिधित्व कर रहा है यही कारण है कि। भूलभुलैया में प्रत्येक स्थान पेड़ पर एक नोड है और वहां से प्रत्येक नया स्थान उस नोड का बच्चा है।

चौड़ाई पहली खोज करने के लिए, पहले एक एल्गोरिदम को लंबाई के पेड़ के माध्यम से सभी पथों पर विचार करना होता है, फिर लंबाई दो, आदि जब तक यह अंत तक नहीं पहुंच जाता है, जिससे अंत में एल्गोरिदम बंद हो जाता है कोई बच्चा नहीं, जिसके परिणामस्वरूप खाली कतार होती है।

कोड एक कतार (क्यू) का उपयोग करके उन नोड्स का ट्रैक रखता है जिन्हें देखने की आवश्यकता होती है। यह पहले पेड़ की जड़ में भूलभुलैया की शुरुआत को सेट करता है, इसे देखता है (चेक करता है कि यह अंत है), फिर कतार से रूट हटा देता है और प्रत्येक बच्चे के साथ प्रक्रिया को दोहराता है। इस तरह, यह पोस्ट-ऑर्डर यानी रूट (रूट के प्रत्येक बच्चे), (पहले बच्चे के प्रत्येक बच्चे), (दूसरे बच्चे के प्रत्येक बच्चे) आदि में नोड्स पर जाता है, जब तक कि यह अंत तक न हो जाए।

संपादित करें: जैसा कि यह खड़ा है, कतार में इसके बाद अन्य नोड्स की वजह से अंत तक पहुंचने पर एल्गोरिदम समाप्त नहीं हो सकता है। आपको खुद को समाप्त करने की शर्त को लिखना होगा।

Answer 2

यहां एक पूर्ण बीएफएस भूलभुलैया सॉल्वर है। यदि यह पाया जाता है तो यह अंत बिंदु के लिए एक पूर्ण सबसे छोटा रास्ता देता है।

import java.util.*; 

public class Maze { 

    public static int[][] arr = new int[][] { 
      {0,0,0,0,0,0,0,0,0}, 
      {5,5,5,0,0,0,0,0,0}, 
      {0,0,0,5,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,0}, 
      {0,0,0,0,0,0,0,0,9}, 
    }; 

    private static class Point { 
     int x; 
     int y; 
     Point parent; 

     public Point(int x, int y, Point parent) { 
      this.x = x; 
      this.y = y; 
      this.parent = parent; 
     } 

     public Point getParent() { 
      return this.parent; 
     } 

     public String toString() { 
      return "x = " + x + " y = " + y; 
     } 
    } 

    public static Queue<Point> q = new LinkedList<Point>(); 

    public static Point getPathBFS(int x, int y) { 

     q.add(new Point(x,y, null)); 

     while(!q.isEmpty()) { 
      Point p = q.remove(); 

      if (arr[p.x][p.y] == 9) { 
       System.out.println("Exit is reached!"); 
       return p; 
      } 

      if(isFree(p.x+1,p.y)) { 
       arr[p.x][p.y] = -1; 
       Point nextP = new Point(p.x+1,p.y, p); 
       q.add(nextP); 
      } 

      if(isFree(p.x-1,p.y)) { 
       arr[p.x][p.y] = -1; 
       Point nextP = new Point(p.x-1,p.y, p); 
       q.add(nextP); 
      } 

      if(isFree(p.x,p.y+1)) { 
       arr[p.x][p.y] = -1; 
       Point nextP = new Point(p.x,p.y+1, p); 
       q.add(nextP); 
      } 

      if(isFree(p.x,p.y-1)) { 
       arr[p.x][p.y] = -1; 
       Point nextP = new Point(p.x,p.y-1, p); 
       q.add(nextP); 
      } 

     } 
     return null; 
    } 


    public static boolean isFree(int x, int y) { 
     if((x >= 0 && x < arr.length) && (y >= 0 && y < arr[x].length) && (arr[x][y] == 0 || arr[x][y] == 9)) { 
      return true; 
     } 
     return false; 
    } 

    public static void main(String[] args) { 

     Point p = getPathBFS(0,0); 

     for (int i = 0; i < 9; i++) { 
      for (int j = 0; j < 9; j++) { 
       System.out.print(arr[i][j]); 
      } 
      System.out.println(); 
     } 

     while(p.getParent() != null) { 
      System.out.println(p); 
      p = p.getParent(); 
     } 

    } 

}