Uninformed Search-Breadth First Search

## 🧠 **Uninformed Search**

### 📌

– এই অনুসন্ধানে AI কোনো অতিরিক্ত তথ্য (**heuristic**) জানে না।

– শুধুমাত্র **সম্ভাব্য পথগুলো(Possible Path) ঘাঁটাঘাঁটি** করে লক্ষ্যে পৌঁছানোর চেষ্টা করে।

– “অজ্ঞান” মানে হলো — সে জানে না কোন পথ সংক্ষিপ্ত বা ভালো।

> 🔍 উদাহরণ: আপনি একটি অচেনা গুহার মধ্যে, আলো ছাড়া। আপনি সব পথ ঘাঁটছেন — এটাই হলো অজ্ঞান অনুসন্ধান।

—

(a) ব্রেডথ ফার্স্ট সার্চ (BFS) 

📌 ধারণা:

– BFS **এক স্তরের সব নোড পরীক্ষা করে**, তারপর পরের স্তরে যায়।

– এটি **স্তর অনুযায়ী (level by level)** খোঁজে।

– ডেটা স্ট্রাকচার: **কিউ (Queue)** — FIFO (First In First Out)

🎯 উদাহরণ: একটি গ্রাফে BFS

ধরা যাক, নোডগুলো:

“`

        A

       / \

      B   C

     / \   \

    D   E   F

“`

**লক্ষ্য:** ‘F’ নোড খুঁজতে হবে। 

**শুরু:** ‘A’ থেকে

### ✅ ধাপগুলো:

1. প্রথমে `A` দেখা হলো → সন্ধান করা হলো 

2. তারপর `B` ও `C` (A-এর সন্তান) 

3. তারপর `D`, `E`, `F` (B ও C-এর সন্তান)

### 🔍 অনুসন্ধান ক্রম: 

A → B → C → D → E → F

✅ ফলাফল: 

F পাওয়া গেল।

—

✅ BFS-এর বৈশিষ্ট্য:

| বৈশিষ্ট্য | বিবরণ |

|—————–|———————|

| পদ্ধতি | স্তরভিত্তিক অনুসন্ধান |

| ডেটা স্ট্রাকচার | কিউ (Queue) |

| সঠিক কিনা? | হ্যাঁ (যদি লক্ষ্য থাকে) |

| দক্ষতা | মেমরি বেশি খরচ হয় |

| ব্যবহার | সবচেয়ে ছোট পথ খোঁজা (Shortest Path) |

(b) ডেপথ ফার্স্ট সার্চ (DFS) 

📌 ধারণা:

– DFS **একটি পথে যতদূর সম্ভব যায়**, তারপর ফিরে আসে।

– এটি **গভীরে যায়**, তারপর পিছনে ফিরে অন্য পথ খোঁজে।

– ডেটা স্ট্রাকচার: **স্ট্যাক (Stack)** — LIFO (Last In First Out)

🎯 উদাহরণ: একই গ্রাফে DFS

“`

        A

       / \

      B   C

     / \   \

    D   E   F

“`

**লক্ষ্য:** ‘F’ খুঁজতে হবে 

**শুরু:** ‘A’ থেকে

### ✅ ধাপগুলো:

1. A → B (B-এ যাওয়া হলো) 

2. B → D (D-এ যাওয়া হলো) 

3. D থেকে আর যাওয়া যায় না → ফিরে এল B 

4. B → E (E-এ গেল) 

5. E থেকে আর যাওয়া যায় না → ফিরে এল A 

6. A → C → F (F পাওয়া গেল!)

### 🔍 অনুসন্ধান ক্রম: 

**A → B → D → E → C → F**

—

### ✅ DFS-এর বৈশিষ্ট্য:

| বৈশিষ্ট্য |                    বিবরণ                |

|————————|——————————–|

| পদ্ধতি                   | এক পথে গভীরে যাওয়া |

| ডেটা স্ট্রাকচার     | স্ট্যাক (Stack)                   |

| সঠিক কিনা?         | হ্যাঁ (যদি লক্ষ্য থাকে)       |

| দক্ষতা                    | মেমরি কম খরচ হয়       |

| ব্যবহার                  | মেজ সলভিং, সাইকেল ডিটেকশন |

## ✅ BFS vs DFS – তুলনা

| বিষয় | BFS | DFS |

|———————|——————————-|————————————————-|

| পদ্ধতি               | প্রস্থ প্রথম (Level-wise)  | গভীরতা প্রথম (Depth-wise)                |

| ডেটা স্ট্রাকচার | কিউ                                 | স্ট্যাক                                                       |

| মেমরি ব্যবহার | বেশি                                 | কম                                                          |

| সর্বোত্তম পথ    | হ্যাঁ (সবচেয়ে ছোট পথ) | না (দীর্ঘতর পথ হতে পারে)                 |

| ব্যবহার              | শর্টেস্ট পাথ, GPS            | মেজ, গেম ট্রি, ব্যাকট্র্যাকিং              |

—

## 💡 বাস্তব উদাহরণ:

### 🔹 BFS উদাহরণ:

– Google Maps-এ সবচেয়ে কম স্টেপে রুট খোঁজা 

– সোশ্যাল নেটওয়ার্কে 2nd-degree connection খোঁজা

### 🔹 DFS উদাহরণ:

– মেজ সলভ করা (ল্যাবিরিন্থ) 

– ফাইল সিস্টেমে ফোল্ডার ঘাঁটা 

– চেস গেম ট্রি অনুসন্ধান