## 🧠 **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 উদাহরণ:
– মেজ সলভ করা (ল্যাবিরিন্থ)
– ফাইল সিস্টেমে ফোল্ডার ঘাঁটা
– চেস গেম ট্রি অনুসন্ধান