Search & Planningপড়তে ১০ মিনিট লাগবে

স্টেট স্পেস সার্চ (State Space Search)

লক্ষ্যে পৌঁছাতে সম্ভাব্য প্রতিটি চাল বা উপায় অন্বেষণ করা
scope:কোর কনসেপ্ট (মূল ধারণা)difficulty:বিগিনার (Beginner)

ধাঁধায় হারিয়ে যাওয়া (Lost in a Maze)

কল্পনা করুন, আপনি একটি বিশাল গোলকধাঁধা বা মেজ (maze)-এর প্রবেশদ্বারে দাঁড়িয়ে আছেন। আপনি দেখতে পাচ্ছেন যে আপনার চারদিকে করিডোরগুলো নানা দিকে ছড়িয়ে গেছে, কিন্তু আপনার কাছে কোনো ম্যাপ নেই। আপনার কাজ কী? বের হওয়ার রাস্তা খুঁজে পাওয়া।

এক্ষেত্রে আপনার কাছে দুটি কৌশল থাকতে পারে:

  • কৌশল ১ (BFS): এক কদম দূরের সব করিডোর আগে চেক করে নেওয়া। এরপর দুই কদম দূরের সব করিডোর চেক করা। তারপর তিন კদমেরগুলো। ঠিক যেন পানিতে ছড়িয়ে পড়া কোনো ঢেউয়ের মতো, যা সবদিকে সমানভাবে এক স্তর স্তর করে এগোতে থাকে।
  • কৌশল ২ (DFS): একটি করিডোর ধরে হাঁটা শুরু করা এবং একদম শেষ মাথায় পৌঁছানো পর্যন্ত শুধু এগোতে থাকা। এক সময় যদি কোনো ডেড এন্ডে বা দেয়ালে আটকে যান? তখন আবার পেছনের রাস্তায় ফিরে এসে নতুন আরেকটি করিডোর ধরে হাঁটা শুরু করা। অর্থাৎ সবদিকে ছড়িয়ে পড়ার চেয়ে আপনি বরং আগে একটি রাস্তার গভীরে যাওয়ার চেষ্টা করেন।

এআই (AI)-ও ঠিক এভাবেই বিভিন্ন সমস্যার সমাধান করে থাকে। এই মেজ বা গোলকধাঁধাটি হলো একটি স্টেট স্পেস (state space) — প্রতিটি সম্ভাব্য অবস্থানকে একটি স্টেট (state) বলা হয়, প্রতিটি নেওয়া কদমকে বলা হয় ট্রানজিশন (transition), আর বের হওয়ার দরজাটি হলো আপনার গোল স্টেট (goal state) বা পরম লক্ষ্য।

স্টেট স্পেস (State Space) কী?

সহজ কথায় স্টেট স্পেস হলো "কোনো সমস্যার সম্ভাব্য সব ধরন বা কনফিগারেশনগুলোর (configurations) সমষ্টি।" একটি রুবিক্স কিউবের (Rubik's Cube) কথাই ধরা যাক — রঙের ব্লকগুলোকে ঘুরিয়ে পেঁচিয়ে যতগুলো ছকে সাজানো যায়, তার প্রতিটিই হলো একেকটি স্টেট। এর প্রতিটি ঘূর্ণন বা মোচড়ই হলো একেকটি ট্রানজিশন (transition)। আর কিউবটি পুরোপুরি মিলে গেলে সেটি হবে তার গোল স্টেট (goal state)।

একটি রুবিক্স কিউবের ৪৩ কুইন্ট্রিলিয়ন (43 quintillion) বা ৪৩-এর পর ১৮টি শূন্য বসালে যত হয়, তার সমপরিমাণ স্টেট থাকতে পারে! আপনি কখনোই এর সবগুলো একে একে চেক করতে পারবেন না। আর ঠিক এই কারণেই এখানে সার্চ স্ট্র্যাটেজি বা খোঁজার কৌশল এত বেশি গুরুত্বপূর্ণ।

বিএফএস (BFS): একজন সাবধানী অভিযাত্রী

ব্রেডথ-ফার্স্ট সার্চ (Breadth-First Search বা BFS) আরও গভীরে যাওয়ার আগে আশপাশের সব প্রতিবেশী (neighbors) নোডগুলোকে ঘুরে দেখে। ঠিক পানিতে একটি পাথর ফেললে যেরকম হয় — তার চারপাশে তৈরি হওয়া ঢেউগুলো সমানভাবে সবদিকে ছড়িয়ে পড়ে, এখানে কাজটাও ঠিক একইভাবে হয়।

BFS আপনাকে সবচেয়ে ছোট পথটি খুঁজে পাওয়ার নিশ্চয়তা বা গ্যারান্টি দেয় (যদি আদৌ সেরকম কোনো পথ থেকে থাকে)। কারণ এটি ২-কদম দূরের পথগুলো চেক করার আগেই ১-কদমের সবগুলো চেক করে, আবার ৩-এর আগে ২-কদমের সবগুলো চেক করে ইত্যাদি। এর নেতিবাচক দিকটা কী? এটি প্রচুর মেমোরি খরচ করে, কারণ লেভেলের প্রতিটি স্টেটের কথাই একে অক্ষরে অক্ষরে মনে রাখতে হয়।

ডিএফএস (DFS): এক দুঃসাহসী অভিযাত্রী

ডেপথ-ফার্স্ট সার্চ (Depth-First Search বা DFS) পেছন ফিরে আসার বা ব্যাকট্র্যাক (backtrack) করার আগে একেবারে শেষ মাথা বা গভীরতম জায়গা পর্যন্ত ডুব দেয়। এটি অনেকটা চুজ-ইউর-ওন-অ্যাডভেঞ্চার (choose-your-own-adventure) বা পছন্দমতো অ্যাডভেঞ্চার গল্পের বই পড়ার মতো, যেখানে আপনি সবসময় প্রথম অপশনটি বেছে নিয়ে একদম গল্পের শেষ অব্দি পৌঁছে যান এবং এরপর আবার পুনরায় ফিরে এসে পরের অপশনগুলোর দিকে নজর দেন।

DFS অনেক কম মেমোরি ব্যবহার করে (কারণ এটিকে কেবল তার বর্তমান পাথ বা চলার পথটিকে মনে রাখলেই হয়), কিন্তু এটি সবচেয়ে ছোট পথটি খুঁজে পাওয়ার কোনো নিশ্চয়তা বা গ্যারান্টি দেয় না। শর্টকাট থাকার পরও এটি গোল বা লক্ষ্যে পৌঁছানোর অনেক লম্বা ও আঁকাবাঁকা পথ খুঁজে বের করতে পারে।

বিএফএস এবং ডিএফএস ইন অ্যাকশন (BFS and DFS in Action)

from collections import deque


def bfs(graph, start, goal):
    """ব্রেডথ-ফার্স্ট সার্চ (BFS) — লেভেল ধরে ধরে এক্সপ্লোর করা হয়।"""
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        node, path = queue.popleft()
        if node == goal:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None


def dfs(graph, start, goal):
    """ডেপথ-ফার্স্ট সার্চ (DFS) — সবার আগে গভীরে ডুব দেয়।"""
    stack = [(start, [start])]
    visited = {start}
    
    while stack:
        node, path = stack.pop()
        if node == goal:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append((neighbor, path + [neighbor]))
    return None


# গ্রাফ হিসেবে একটি সাধারণ মেজ বা গোলকধাঁধা নেওয়া হলো
maze = {
    'Start': ['A', 'B'],
    'A': ['C', 'D'],
    'B': ['E'],
    'C': [],
    'D': ['Goal'],
    'E': ['Goal'],
    'Goal': []
}


print("BFS-এর পথ:", bfs(maze, 'Start', 'Goal'))
print("DFS-এর পথ:", dfs(maze, 'Start', 'Goal'))
Output
BFS-এর পথ: ['Start', 'B', 'E', 'Goal']
DFS-এর পথ: ['Start', 'B', 'E', 'Goal']
Note: বিএফএস (BFS) বনাম ডিএফএস (DFS): BFS আপনাকে সবচেয়ে ছোট পথের গ্যারান্টি দিলেও, এটি খুব দ্রুত মেমোরি খরচ করে ফুরিয়ে ফেলে। অন্যদিকে, DFS মেমোরি বাঁচালেও এটি একটি ভুল পথে অনেক দূর পর্যন্ত হারিয়ে যেতে পারে। আর বাস্তবে, অনেক এআই (AI) সিস্টেম এই দুইয়ের মিশেলে তৈরি একটি হাইব্রিড সিস্টেম ব্যবহার করে, যাকে ইটারেটিভ ডিপেনিং ডিএফএস (Iterative Deepening DFS) বলা হয় — এটি মূলত একটি নির্দিষ্ট ডেপথ বা গভীরতা পর্যন্ত DFS চালায় এবং ধীরে ধীরে সেই গভীরতার লিমিটটি বাড়াতে থাকে, যার ফলে দুটো অ্যালগরিদমেরই সবচেয়ে ভালো দিকগুলো দারুণভাবে কাজে লাগানো যায়।

বাস্তব জগতের স্টেট স্পেস (Real-World State Spaces)

স্টেট স্পেস সার্চ কেবল গোলকধাঁধা মেলানোর জন্যই নয়, বরং এআই-এর প্রায় প্রতিটি শাখাতেই এর ব্যবহার রয়েছে:

  • জিপিএস (GPS) নেভিগেশন — এর প্রতিটি মোড় বা সংযোগস্থল হলো একটি স্টেট, প্রতিটি রাস্তা হলো ট্রানজিশন এবং আপনার গন্তব্য হলো এর গোল বা লক্ষ্য।
  • গেম এআই (Game AI) — দাবা খেলার মতো প্রতিটি বোর্ডের অবস্থান হলো একটি স্টেট, প্রতিটি বৈধ বা লিগ্যাল (legal) চাল হলো ট্রানজিশন এবং কিস্তিমাত বা চেকমেট করা হলো এর গোল।
  • রোবট প্ল্যানিং (Robot planning) — রোবটের জয়েন্টগুলোর (joints) বিভিন্ন অবস্থান হলো একেকটি স্টেট এবং এর প্রতিটি মোটর কমান্ড হলো একেকটি ট্রানজিশন।
  • পাজল সলভার (Puzzle solvers) — স্লাইডিং পাজল (sliding puzzles), সুডোকু (Sudoku) এবং রুবিক্স কিউব (Rubik's cube) ইত্যাদি সবই হলো স্টেট স্পেস প্রবলেম।

এগুলোর প্রতিটিতেই আসল চ্যালেঞ্জটি এসে দাঁড়ায় এক জায়গাতেই: এর স্টেট স্পেসটি অনেক বিশাল হয়ে থাকে, তাই সবকিছু এক্সপ্লোর না করে কেবল লক্ষ্যটিতে ঠিকঠাক পৌঁছানোর জন্য আপনাকে বেশ চতুর বা বুদ্ধিদীপ্ত এপ্রোচ নিতে হয়।

ছোট কুইজ

BFS এমন কোন জিনিসটি নিশ্চিত করে, যা DFS পারে না?
Challenge

পড়া চালিয়ে যান