অন্ধ search — BFS, DFS আর uniform cost

পর্ব ৩৯-এ (সমস্যাকে search হিসেবে দেখা) একটি সমস্যাকে state, action, transition, goal test আর path cost দিয়ে লেখা হয়েছে, আর একটি সাধারণ search loop দেখা হয়েছে: frontier থেকে একটি node বের করুন, goal কি না দেখুন (সেখানে goal test হয় বের করার সময়), না হলে তার সন্তানদের frontier-এ রাখুন। এই পর্বের প্রশ্ন: frontier থেকে কোন node আগে বের করবেন? উত্তর বদলালেই পদ্ধতি বদলায়, আর তার সঙ্গে বদলায় পাওয়া পথের মান, সময় আর memory. Graph, queue, stack আর heap কীভাবে বানানো হয়, তা DSA কোর্সের বিষয় (BFS, DFS, Dijkstra); এখানে AI-এর দৃষ্টিতে কৌশলগুলোর তুলনা।

দুটি চলমান উদাহরণ থাকবে। প্রথমটি বাজারঘরের (এই কোর্সের কাল্পনিক অনলাইন দোকান) এক ডেলিভারি রাইডারের বানানো রাস্তার মানচিত্র: ঢাকার ১০টি এলাকা, মিরপুরের গুদাম থেকে মতিঝিলে পার্সেল। এলাকার নাম আসল, কিন্তু রাস্তা আর km সব বানানো, বাস্তবের দূরত্ব নয়। এটি পর্ব ৩৯-এর ৯ এলাকার মানচিত্র থেকে আলাদা, একটু বড় একটি বানানো মানচিত্র, তাই সংখ্যাগুলোও আলাদা। দ্বিতীয়টি ৭ সারি × ১০ কলামের একটি grid maze, যেখানে প্রতিটি ধাপের খরচ সমান।

১ · “অন্ধ” search মানে কী — goal কত দূরে, জানা নেই

ধরুন একজন রিকশাচালক প্রথমবার একটি অচেনা মফস্বল শহরে এসেছেন, হাতে মানচিত্র বা ফোন নেই। তিনি জানেন প্রতিটি মোড়ে কোন কোন রাস্তা বের হয়েছে, আর গন্তব্যে পৌঁছালে সাইনবোর্ড দেখে চিনবেন; কিন্তু কোন রাস্তাটি গন্তব্যের দিকে, তা বোঝার উপায় নেই। তাঁর হাতে শুধু কৌশল বাছার স্বাধীনতা: কাছের সব গলি আগে, নাকি একটি রাস্তা ধরে যতদূর যায়, নাকি সবসময় এখন পর্যন্ত সবচেয়ে কম ভাড়ার পথটি আগে।

এটিই uninformed search, বাংলায় “অন্ধ” search: পদ্ধতিটি সমস্যার সংজ্ঞার বাইরে কিছু জানে না। সবচেয়ে বড় কথা, কোনো state থেকে goal কত দূরে, তার কোনো অনুমান (estimate) এটি ব্যবহার করে না। goal test শুধু “পৌঁছেছি কি না” বলে, “কতটা কাছে” বলে না। সেই অনুমান যোগ করলে পদ্ধতিকে বলে informed বা heuristic search, যা পর্ব ৪১-এর (Heuristic আর A*) বিষয়।

চারটি মাপকাঠি আর তিনটি অক্ষর

পদ্ধতিগুলো তুলনা করা হয় চারটি প্রশ্নে। এক, completeness: সমাধান থাকলে পদ্ধতিটি কি নিশ্চিতভাবে তা পাবে? দুই, optimality: পাওয়া সমাধানটি কি সবচেয়ে কম path cost-এর? তিন, time: কতগুলো node তৈরি বা expand হয়? চার, space: একসঙ্গে সবচেয়ে বেশি কতগুলো node memory-তে রাখতে হয়? সময় আর memory লেখা হয় Big-O দিয়ে (বিস্তারিত DSA-র Big-O পর্বে), তিনটি অক্ষরে:

• b = branching factor: একটি state থেকে সর্বোচ্চ কতগুলো সন্তান। মানচিত্রে মিরপুরের ৪টি রাস্তা, maze-এ একটি ঘরের সর্বোচ্চ ৪টি প্রতিবেশী।
• d = সবচেয়ে অগভীর goal-এর গভীরতা, মানে শুরু থেকে সবচেয়ে কম কয়টি ধাপে goal-এ পৌঁছানো যায়।
• m = state space-এ যেকোনো পথের সর্বোচ্চ দৈর্ঘ্য; চক্র থাকলে আর কোনো বাধা না থাকলে এটি অসীম হতে পারে।

গভীরতা d পর্যন্ত একটি পূর্ণ গাছে node-এর সংখ্যা 1 + b + b² + … + b^d, যা প্রায় b^d. তাই b^d এই পর্বে বারবার আসবে। নিচের ছবিতে একই ছোট গাছে BFS আর DFS কোন ক্রমে node খোলে, দেখুন।

২ · Breadth-first search — FIFO frontier, ঢেউয়ের মতো ছড়ানো

পুকুরে ঢিল ছুড়লে ঢেউ চারদিকে সমানভাবে ছড়ায়: আগে কাছের বৃত্ত, তারপর দূরের। Breadth-first search (BFS) ঠিক তাই করে। শুরুর node থেকে ১ ধাপ দূরের সবগুলো আগে, তারপর ২ ধাপ দূরের সবগুলো, এভাবে। frontier একটি FIFO queue: নতুন node লাইনের পেছনে দাঁড়ায়, আর সামনে থেকে বের হয়, যেমন ব্যাংকের কাউন্টারে টোকেন ধরে ডাকা হয়। Python-এ এর জন্য collections.deque, যার popleft() সামনে থেকে O(1) সময়ে বের করে (queue কীভাবে বানানো হয়, দেখুন DSA-র queue আর deque).

পাশাপাশি একটি explored set বা reached set রাখা হয়, যাতে একই এলাকা বারবার frontier-এ না ঢোকে। পর্ব ৩৯-এর ভাষায় এটি graph search; তা না রাখলে মিরপুর → গাবতলী → মিরপুর → … করে একই রাস্তায় ঘুরপাক খেতে হতো। নিচে মিরপুর থেকে মতিঝিল পর্যন্ত BFS ধাপে ধাপে দেখুন। প্রতিবেশীদের ক্রম dhaka_map.txt ফাইলে যেভাবে লেখা, সেভাবেই।

Goal test: তৈরির সময় না expand-এর সময়?

উপরের ধাপ ৫-এ BFS মতিঝিল তৈরি হওয়ার মুহূর্তেই goal test করেছে, queue থেকে বের হওয়া পর্যন্ত অপেক্ষা করেনি। একে বলে early goal test. BFS-এ এটি নিরাপদ: BFS গভীরতা d-এর সব node, গভীরতা d + 1-এর কোনো node-এর আগে তৈরি করে, তাই প্রথম তৈরি হওয়া goal-ই সবচেয়ে অগভীর goal.

কিন্তু পার্থক্যটি খরচে বিশাল। ধরুন b = 10, goal গভীরতা ৪-এ আর দুর্ভাগ্যবশত সেই স্তরের সবচেয়ে শেষ node. তৈরির সময় test করলে সর্বোচ্চ 1 + 10 + 100 + 1,000 + 10,000 = 11,111টি node তৈরি হয়। expand-এর সময় test করলে goal-এর আগের গভীরতা ৪-এর বাকি 9,999টি node-ও expand হবে, প্রতিটি ১০টি করে সন্তান বানাবে: আরও 99,990টি, মোট 1,11,101. প্রায় দশ গুণ, মানে পুরো একটি বাড়তি স্তর। এই পার্থক্য পরের অংশের memory-র হিসাবেও আসবে। তবে uniform-cost search-এ early goal test ভুল ফল দেয়, অংশ ৬-এ দেখবেন।

BFS-এর চার মাপকাঠি

• Complete: হ্যাঁ, যদি b সসীম হয়। goal কোনো সসীম গভীরতা d-তে থাকলে BFS সেই স্তরে একদিন পৌঁছাবেই, এমনকি state space অসীম হলেও।
• Optimal: শুধু তখনই, যখন প্রতিটি ধাপের খরচ সমান (বা গভীরতার সঙ্গে খরচ কখনো কমে না)। BFS সবচেয়ে কম ধাপের পথ দেয়; ধাপের খরচ আলাদা হলে তা সবচেয়ে সস্তা নাও হতে পারে, ঠিক যেমন ২২ km.
• Time: O(b^d), কারণ সবচেয়ে খারাপ অবস্থায় গভীরতা d পর্যন্ত প্রায় সব node তৈরি হয়।
• Space: O(b^d). পুরো শেষ স্তরটি একসঙ্গে frontier-এ থাকে, আর reached set-এ আগের সবাই। এটিই BFS-এর আসল দুর্বলতা।

৩ · BFS-এর memory-র দেয়াল

“O(b^d)” শুনতে বিমূর্ত। সংখ্যায় দেখলে বোঝা যায় কেন বাস্তবে BFS প্রায়ই সময়ের আগে memory-তে আটকে যায়। নিচের টেবিলে b = 10, আর গভীরতা d পর্যন্ত মোট node 1 + 10 + … + 10^d (early goal test-এ সবচেয়ে খারাপ অবস্থা)।

টেবিলটি দুটি কথা বলে। প্রথমত, প্রতি দুই স্তরে খরচ একশো গুণ বাড়ে; যন্ত্র দশ গুণ দ্রুত হলে আপনি মাত্র এক স্তর বেশি যেতে পারবেন। দ্বিতীয়ত, গভীরতা ৮-এ সময় মাত্র দুই মিনিট, কিন্তু memory 111 GB, যা একটি সাধারণ ল্যাপটপের RAM-এর অনেক গুণ। গভীরতা ১০-এ তিন ঘণ্টা অপেক্ষা করা যায়, কিন্তু 11 TB RAM কোথায় পাবেন? BFS-এ memory সময়ের অনেক আগে ফুরায়। সংখ্যার এমন বিস্ফোরণকে বলে combinatorial explosion. এই দেয়াল পার হওয়ার দুটি পথ এই পর্বেই: DFS-ঘরানার কম memory-র কৌশল (অংশ ৪–৫), আর পরের পর্বে goal-এর দিকে অনুমান দিয়ে কম node খোলা।

৪ · Depth-first search — LIFO frontier, গভীরে ডুব

গোলকধাঁধায় হারিয়ে গেলে অনেকে একটি পুরোনো কৌশল নেন: একটি পথ ধরে যতদূর যায় যান, আটকে গেলে শেষ মোড়ে ফিরে অন্য পথ ধরুন। Depth-first search (DFS) এটিই। frontier এখানে একটি LIFO stack, থালার স্তূপের মতো: সবচেয়ে শেষে রাখা থালাটি আগে তোলা হয়। তাই সবচেয়ে নতুন তৈরি node, মানে সবচেয়ে গভীরটি, আগে expand হয়। Python-এ list-এর append আর pop() দিয়েই stack (DSA-র stack), অথবা recursion দিয়ে।

নিচের stepper-এ একই মানচিত্রে DFS. কোডে প্রতিবেশীদের উল্টো ক্রমে push করা হয়, যাতে ফাইলের প্রথম প্রতিবেশীটি stack-এর ওপরে থাকে আর আগে expand হয়। একটি node stack-এ একাধিকবার থাকতে পারে; বের হওয়ার সময় আগেই explored হলে সেটি বাদ যায়। goal test হয় expand-এর সময়।

DFS কোথায় হারিয়ে যায়

উপরের DFS explored set রেখেছিল বলে শেষ পর্যন্ত পৌঁছেছে। এবার দুটি বিপদ দেখুন।

• চক্র: explored set বা অন্তত নিজের পথের ওপর কোনো যাচাই ছাড়া (tree search) DFS মিরপুর → গাবতলী → মিরপুর → গাবতলী … করে চিরকাল ঘুরবে, কারণ সবসময় সবচেয়ে নতুন node-টি আগে, আর প্রথম প্রতিবেশী আবার মিরপুর। প্রতিটি রাস্তা দুই দিকে চলে বলে এই মানচিত্রে চক্র সর্বত্র।
• অসীম state space: ধরুন state হলো “একটি সংখ্যা”, action “১ যোগ” বা “২ দিয়ে গুণ”। DFS “১ যোগ” শাখা ধরে অসীম গভীরে নামতে থাকবে, পাশের শাখায় goal থাকলেও। BFS এখানে পায়, কারণ সে স্তর ধরে চলে।

তাই DFS complete নয়, অসীম বা চক্রযুক্ত space-এ কোনো যাচাই ছাড়া। সসীম space-এ graph search হিসেবে (explored set রেখে) সে complete, কিন্তু তখন explored set-এ সব state রাখতে হয়, ফলে memory-র সুবিধা হারায়। Optimal-ও নয়, উপরে ৩৮ km দেখলেন। সময় O(b^m), যেখানে m সর্বোচ্চ গভীরতা, যা d-এর চেয়ে অনেক বড় হতে পারে।

তাহলে DFS কেন? memory. শুধু নিজের পথের ওপর চক্র-যাচাই করে (পুরো explored set না রেখে) চালালে DFS-কে রাখতে হয় শুধু বর্তমান পথটি আর পথের প্রতিটি node-এর এখনো না-দেখা ভাইবোন: সর্বোচ্চ প্রায় b × m টি node, মানে space O(bm). b = 10 আর m = 12 হলে মাত্র প্রায় ১২০টি node, BFS-এর 1.11 PB-এর পাশে প্রায় শূন্য। Recursion দিয়ে একটি একটি করে সন্তান তৈরি করলে (backtracking, DSA-র backtracking) এটি O(m)-এ নামে।

এবার grid maze-এ দুটি পদ্ধতি একসঙ্গে চালান। state হলো একটি ঘর (সারি, কলাম); প্রতিবেশীর ক্রম ডানে, নিচে, বাঁয়ে, ওপরে; প্রতিটি ধাপের খরচ 1. শুরু ওপরের বাঁ কোণে (S), goal নিচের ডান কোণে (G). ফলে * দিয়ে পাওয়া পথ আঁকা হবে। এই ব্লক আর পরের তিনটি ব্লক একই namespace ভাগ করে (data-shared), তাই এখানে লেখা bfs আর dfs পরে আবার ব্যবহার হবে; পরের কোনো ব্লক আগে চালালে এটি নিজেই আগে চলে যায়। প্রথমবার ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে।

from collections import deque
MAZE = open("maze.txt").read().split()                 # '#' = দেয়াল
R, C = len(MAZE), len(MAZE[0]); START, GOAL = (0, 0), (R - 1, C - 1)
def grid_nbrs(s):                    # ক্রম: ডানে, নিচে, বাঁয়ে, ওপরে; প্রতি ধাপ 1
    r, c = s
    return [((a, b), 1) for a, b in [(r, c+1), (r+1, c), (r, c-1), (r-1, c)]
            if 0 <= a < R and 0 <= b < C and MAZE[a][b] != "#"]
def walk(parent, s):                 # parent ধরে উল্টো দিকে হেঁটে পথ
    return [] if s is None else walk(parent, parent[s]) + [s]
def bfs(start, goal, nbrs):
    frontier, parent, order, maxf = deque([start]), {start: None}, [], 1
    while frontier:
        s = frontier.popleft(); order.append(s)            # FIFO: সবচেয়ে পুরোনো
        for t, _ in nbrs(s):
            if t not in parent:                            # আগে দেখা হয়নি
                parent[t] = s
                if t == goal: return walk(parent, t), order, maxf  # তৈরির সময় test
                frontier.append(t)
        maxf = max(maxf, len(frontier))
def dfs(start, goal, nbrs):
    frontier, parent, order, maxf = [(start, None)], {}, [], 1
    while frontier:
        s, par = frontier.pop()                            # LIFO: সবচেয়ে নতুন
        if s in parent: continue                           # আগেই expand হয়েছে
        parent[s] = par; order.append(s)
        if s == goal: return walk(parent, s), order, maxf  # expand-এর সময় test
        frontier += [(t, s) for t, _ in reversed(nbrs(s)) if t not in parent]
        maxf = max(maxf, len(frontier))

for name, f in [("BFS", bfs), ("DFS", dfs)]:
    path, order, maxf = f(START, GOAL, grid_nbrs)
    print(f"{name}: steps {len(path)-1}, expanded {len(order)}, max frontier {maxf}")
    print("  first 6 expanded:", order[:6])
    for r in range(R): print("  " + "".join("*" if (r, c) in path else MAZE[r][c] for c in range(C)))

BFS: steps 19, expanded 44, max frontier 4
  first 6 expanded: [(0, 0), (0, 1), (1, 0), (0, 2), (2, 0), (1, 2)]
  ***#******
  .#*#*####*
  .#***#...*
  .###.#.##*
  ...#.#..#*
  .#.#.##.#*
  .#......#*
DFS: steps 25, expanded 26, max frontier 5
  first 6 expanded: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3)]
  ***#......
  .#*#.####.
  .#***#****
  .###*#*##*
  ...#*#**#*
  .#.#*##*#*
  .#..****#*

৫ · Depth-limited search আর iterative deepening

DFS-এর অসীম গভীরতার সমস্যার সরল সমাধান: একটি সীমা দিন। Depth-limited search (DLS) গভীরতা l-এর node-গুলোকে এমনভাবে দেখে যেন তাদের কোনো সন্তান নেই। ফলে দুই রকম ব্যর্থতা হয়: “সমাধান নেই” (failure), আর “এই সীমার মধ্যে নেই” (cutoff). সীমা কোথা থেকে আসবে? কখনো সমস্যা থেকেই: ১০টি এলাকার মানচিত্রে চক্রহীন কোনো পথ ৯ ধাপের বেশি হতে পারে না, তাই l = 9 যথেষ্ট। কিন্তু l < d হলে DLS goal পায় না (complete নয়), আর l অনেক বড় হলে আবার DFS-এর মতো খারাপ পথ দিতে পারে।

যদি d জানা না থাকে? তখন iterative deepening DFS (IDDFS): l = 0 দিয়ে DLS চালান, না পেলে l = 1, তারপর 2, … যতক্ষণ না goal পাওয়া যায়। প্রতিটি দফা একটি DFS, তাই memory মাত্র বর্তমান পথ। আবার প্রথম যে সীমায় goal পাওয়া যায়, তা সবচেয়ে অগভীর goal-এর গভীরতা d, তাই BFS-এর মতো সবচেয়ে কম ধাপের পথ।

বারবার দেখার দাম কত? b = 10-এর হিসাব

গভীরতা d-এর goal-এর জন্য IDDFS-এ শেষ স্তরের node (গভীরতা d) একবার তৈরি হয়, গভীরতা d − 1-এর node দুবার, …, গভীরতা ১-এর node d বার। শুরুর node বাদ দিয়ে মোট:

N(IDDFS) = d·b + (d − 1)·b² + … + 2·b^d−1 + 1·b^d

b = 10, d = 5 হলে: 5 × 10 + 4 × 100 + 3 × 1,000 + 2 × 10,000 + 1 × 1,00,000 = 50 + 400 + 3,000 + 20,000 + 1,00,000 = 1,23,450. একই goal-এ BFS (শুরু বাদ দিয়ে) 10 + 100 + 1,000 + 10,000 + 1,00,000 = 1,11,110. অনুপাত 1,23,450 ÷ 1,11,110 ≈ 1.11, মানে মাত্র প্রায় ১১% বাড়তি কাজ। কারণ, বেশিরভাগ node সবচেয়ে নিচের স্তরে, আর সেটি একবারই তৈরি হয়। d বড় হলে অনুপাত b ÷ (b − 1)-এর দিকে যায়: b = 10-এ 1.11, b = 2-এ 2. b ছোট হলেই কেবল পুনরাবৃত্তির দাম বেশি।

নিচের কোড দুটি জিনিস চালায়: মানচিত্রে IDDFS, প্রতিটি সীমায় কতগুলো node দেখা হলো তা গুনে; আর b = 10-এর একটি কৃত্রিম গাছে, যেখানে goal গভীরতা ৪-এর একেবারে শেষ node, যাতে ওপরের সূত্র সত্যিকারের গণনার সঙ্গে মেলানো যায়। এখানে DLS শুধু নিজের পথের ওপর চক্র ঠেকায়, কোনো explored set রাখে না; তাই memory শুধু পথটি। গণনায় শুরুর node-ও ধরা হয়েছে।

ROADS = {}                                     # বানানো রাস্তার মানচিত্র, km
for line in open("dhaka_map.txt").read().splitlines():
    a, rest = line.split(":")
    ROADS[a] = [(b, int(km)) for b, km in (x.split() for x in rest.split(","))]
map_nbrs = lambda s: ROADS[s]

def dls(s, goal, limit, nbrs, path, st):
    st["nodes"] += 1; st["deep"] = max(st["deep"], len(path))
    if s == goal: return list(path)
    if limit == 0: return None                  # cutoff: এর নিচে যাওয়া নিষেধ
    for t, _ in nbrs(s):
        if t not in path:                       # নিজের পথে চক্র নয়
            path.append(t)
            found = dls(t, goal, limit - 1, nbrs, path, st)
            path.pop()
            if found: return found
    return None
def iddfs(start, goal, nbrs, max_limit=60, show=False):
    st, total = {"nodes": 0, "deep": 0}, 0
    for limit in range(max_limit + 1):          # 0, 1, 2, ... করে গভীরতা বাড়ানো
        st["nodes"] = 0
        found = dls(start, goal, limit, nbrs, [start], st)
        total += st["nodes"]
        if show: print(f"  limit {limit}: nodes {st['nodes']:>6}, total {total:>6}")
        if found: return found, total, st["deep"]

print("delivery map:")
p, total, deep = iddfs("Mirpur", "Motijheel", map_nbrs, show=True)
print("  path:", " -> ".join(p), "| hops", len(p) - 1)

print("uniform tree, b = 10, goal = last node at depth 4:")
tree = lambda n: [(10 * n + k, 1) for k in range(1, 11)]
p, total, deep = iddfs(0, 11110, tree, show=True)
bfs_nodes = 1 + 10 * len(bfs(0, 11110, tree)[1])     # root + expanded × b
print(f"  BFS nodes {bfs_nodes} | IDDFS/BFS = {total / bfs_nodes:.3f} | memory: {deep} nodes")

delivery map:
  limit 0: nodes      1, total      1
  limit 1: nodes      5, total      6
  limit 2: nodes     10, total     16
  path: Mirpur -> Mohakhali -> Motijheel | hops 2
uniform tree, b = 10, goal = last node at depth 4:
  limit 0: nodes      1, total      1
  limit 1: nodes     11, total     12
  limit 2: nodes    111, total    123
  limit 3: nodes   1111, total   1234
  limit 4: nodes  11111, total  12345
  BFS nodes 11111 | IDDFS/BFS = 1.111 | memory: 5 nodes

সংক্ষেপে IDDFS: complete (b সসীম হলে), optimal যখন সব ধাপের খরচ সমান, time O(b^d), space O(bd). state space বড় আর সমাধানের গভীরতা অজানা হলে এটি সাধারণত ভালো অন্ধ পদ্ধতি। দুর্বলতা: explored set না রাখায় একই state ভিন্ন পথে বারবার আসে; grid-এর মতো চক্রে ভরা graph-এ তা অনেক (অংশ ৮)।

৬ · Uniform-cost search — খরচ ধরে priority queue

রাইডারের আসল চিন্তা ধাপ নয়, km (বা সময়, বা তেলের খরচ)। Uniform-cost search (UCS) frontier-কে মোট পথ-খরচ g(n) ধরে সাজায়: শুরু থেকে node n পর্যন্ত পাওয়া পথের সব ধাপের খরচের যোগ। সবসময় সবচেয়ে কম g-এর node আগে expand হয়। frontier এখানে একটি priority queue, Python-এ heapq (binary heap, ভেতরের গঠন DSA-র heap পর্বে)। heapq.heappush(h, (g, node)) দিলে tuple-এর প্রথম মান g ধরে সাজায়; g সমান হলে দ্বিতীয় মান, এখানে এলাকার ইংরেজি নাম, বর্ণানুক্রমে।

দুটি নিয়ম মনে রাখুন। এক, কোনো node-এ নতুন করে সস্তা পথ পেলে তার g হালনাগাদ করে নতুন entry push করা হয়; পুরোনো দামি entry heap-এ থেকে যায় আর বের হলে বাদ পড়ে (heapq-তে “দাম কমানো”-র সরাসরি উপায় নেই, তাই এই কৌশল)। দুই, goal test হয় expand-এর সময়, তৈরির সময় নয়।

কেন UCS optimal, আর কখন নয়

যুক্তিটি এক লাইনের: সব ধাপের খরচ ঋণাত্মক না হলে কোনো পথ এগোলে তার খরচ কমে না, আর UCS g-এর ছোট থেকে বড় ক্রমে node expand করে। তাই কোনো node যখন প্রথমবার expand হয়, তখন তার g-ই সবচেয়ে কম সম্ভব খরচ; goal-এর ক্ষেত্রেও তাই। এ কারণেই goal test expand-এর সময়: ধাপ ৫-এ মতিঝিল তৈরি হয়েছিল ২২-এ, কিন্তু তখনো ১০ আর ১১ খরচের node বাকি ছিল, যাদের পথ ধরে সস্তা রাস্তা আসতে পারত, আর এসেছেও।

• ঋণাত্মক খরচ (ধরুন কোনো রাস্তায় গেলে ক্যাশব্যাক পাওয়া যায়) থাকলে এই যুক্তি ভাঙে, UCS আর Dijkstra ভুল ফল দিতে পারে; তখন Bellman-Ford-এর মতো অ্যালগরিদম লাগে (DSA-তে)।
• শূন্য খরচের চক্র থাকলে UCS ঘুরপাক খেতে পারে; completeness-এর জন্য প্রতিটি ধাপের খরচ অন্তত একটি ধনাত্মক ε (epsilon, ছোট একটি সংখ্যা) হওয়া দরকার।
• খরচ: সবচেয়ে ভালো সমাধানের খরচ C* হলে time আর space O(b^{1 + ⌊C*/ε⌋}); এখানে ⌊ ⌋ মানে নিচের পূর্ণসংখ্যা। ধাপের খরচ খুব ছোট আর সমাধান দামি হলে এটি BFS-এর b^d-এর চেয়ে অনেক খারাপ হতে পারে, কারণ UCS অনেক সস্তা-কিন্তু-অকাজের ছোট ধাপ আগে ঘোরে। সব ধাপের খরচ সমান হলে UCS কার্যত BFS-ই, শুধু goal test দেরিতে।

UCS আর Dijkstra: একই ধারণা, ভিন্ন ব্যবহার

Dijkstra-র অ্যালগরিদম (Edsger Dijkstra, ১৯৫৯) একটি উৎস থেকে জানা graph-এর সব node-এর সবচেয়ে ছোট দূরত্ব বের করে (DSA-র Dijkstra). UCS একই নিয়মে চলে, কিন্তু node তৈরি করে যখন দরকার আর goal expand হলেই থামে; ৮-puzzle-এর মতো বিশাল state space-এ এই পার্থক্য বড় (ভাবনার প্রশ্ন ৩)।

এবার BFS আর UCS একই মানচিত্রে, একই শুরু আর goal-এ। km(p) একটি পথের সব রাস্তার km যোগ করে।

import heapq

def ucs(start, goal, nbrs):
    frontier, best, parent = [(0, start)], {start: 0}, {start: None}
    order, maxf = [], 1
    while frontier:
        g, s = heapq.heappop(frontier)                    # সবচেয়ে কম g আগে
        if g > best[s]: continue                          # পুরোনো, বেশি দামের entry
        order.append(s)
        if s == goal: return walk(parent, s), order, maxf # expand-এর সময় test
        for t, w in nbrs(s):
            if g + w < best.get(t, float("inf")):         # নতুন বা সস্তা পথ
                best[t], parent[t] = g + w, s
                heapq.heappush(frontier, (g + w, t))
        maxf = max(maxf, len(frontier))

km = lambda p: sum(dict(ROADS[a])[b] for a, b in zip(p, p[1:]))
for name, f in [("BFS", bfs), ("UCS", ucs)]:
    p, order, maxf = f("Mirpur", "Motijheel", map_nbrs)
    print(f"{name}: {' -> '.join(p)}")
    print(f"     hops {len(p) - 1}, km {km(p)}, expanded {len(order)}")
print("UCS expand order:", ", ".join(ucs("Mirpur", "Motijheel", map_nbrs)[1]))

BFS: Mirpur -> Mohakhali -> Motijheel
     hops 2, km 22, expanded 4
UCS: Mirpur -> Farmgate -> Tejgaon -> Motijheel
     hops 3, km 16, expanded 10
UCS expand order: Mirpur, Gabtoli, Farmgate, Mohakhali, Tejgaon, Dhanmondi, Gulshan, Uttara, Badda, Motijheel

৭ · Bidirectional search — দুই দিক থেকে খোঁড়া সুড়ঙ্গ

পাহাড়ের নিচে সুড়ঙ্গ খুঁড়তে দুই দিক থেকে দুটি দল কাজ শুরু করে, মাঝখানে মিলিত হয়। Bidirectional search একই কাজ করে: একটি search শুরু থেকে সামনে, আরেকটি goal থেকে পেছনে, আর দুটি frontier কোনো state-এ মিলে গেলে থামে। লাভটি ঘাতের হিসাবে: প্রতিটি দিক মাত্র d/2 গভীরতা পর্যন্ত যায়, তাই মোট প্রায় b^d/2 + b^d/2, যা b^d-এর চেয়ে অনেক কম। b = 10, d = 6 হলে 2 × 10³ = 2,000 বনাম 10⁶ = দশ লাখ।

৮ · পাশাপাশি তুলনা — তত্ত্ব আর সত্যিকারের run

প্রথমে তত্ত্বের টেবিল, যা বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় প্রায়ই চাওয়া হয়। b = branching factor, d = সবচেয়ে অগভীর goal-এর গভীরতা, m = সর্বোচ্চ গভীরতা, l = গভীরতার সীমা, C* = সবচেয়ে সস্তা সমাধানের খরচ, ε = সবচেয়ে ছোট ধাপের খরচ।

¹ b সসীম হলে। ² প্রতিটি ধাপের খরচ ≥ ε > 0 হলে। ³ সব ধাপের খরচ সমান হলে। ⁴ সসীম state space-এ explored set রাখলে complete, কিন্তু তখন memory বেশি। ⁵ দুই দিকেই BFS (বা ঠিক থামার নিয়মসহ UCS) হলে।

এবার চারটি পদ্ধতি দুটি সমস্যায় সত্যিকারে চালিয়ে মিলিয়ে দেখুন। expanded কলামে BFS, DFS আর UCS-এর জন্য expand হওয়া node, আর IDDFS-এর জন্য সব দফা মিলিয়ে দেখা node (প্রতিটি দফার শুরুর node-সহ)। max mem কলামে প্রথম তিনটির জন্য frontier-এর সর্বোচ্চ আকার, আর IDDFS-এর জন্য memory-তে থাকা পথের সর্বোচ্চ দৈর্ঘ্য। মানচিত্রে cost হলো km, maze-এ ধাপের সংখ্যা। নিচে maze-এ BFS আর DFS কোন ঘর কোন ক্রমে খুলেছে, তার একটি ছবিও আসবে।

import numpy as np
import matplotlib.pyplot as plt

def compare(title, start, goal, nbrs, cost):
    print(f"{title}\n  {'algo':6}{'expanded':>9}{'max mem':>8}{'steps':>6}{'cost':>6}")
    for name, f in [("BFS", bfs), ("DFS", dfs), ("IDDFS", iddfs), ("UCS", ucs)]:
        p, work, mem = f(start, goal, nbrs)
        if name != "IDDFS": work = len(work)          # IDDFS আগেই মোট সংখ্যা দেয়
        print(f"  {name:6}{work:>9}{mem:>8}{len(p) - 1:>6}{cost(p):>6}")

compare("delivery map (km)", "Mirpur", "Motijheel", map_nbrs, km)
compare("grid maze (steps)", START, GOAL, grid_nbrs, lambda p: len(p) - 1)

walls = np.where(np.array([[ch == "#" for ch in row] for row in MAZE]), 1.0, np.nan)
fig, axes = plt.subplots(1, 2, figsize=(8, 3.8))
for ax, (name, f) in zip(axes, [("BFS", bfs), ("DFS", dfs)]):
    p, order, _ = f(START, GOAL, grid_nbrs)
    seen = np.full((R, C), np.nan)
    for i, s in enumerate(order): seen[s] = i       # কততম expand
    ax.imshow(seen, cmap="viridis")
    ax.imshow(walls, cmap="Greys", vmin=0, vmax=1)
    ys, xs = zip(*p)
    ax.plot(xs, ys, color="red", lw=2.5, label="path")
    ax.set_title(f"{name}: {len(order)} expanded, path {len(p) - 1} steps")
    ax.set_xticks([]); ax.set_yticks([])
axes[0].legend(loc="lower left", fontsize=8)
fig.suptitle("Expanded cells (dark = early, yellow = late), walls in black")
plt.tight_layout()
plt.show()

delivery map (km)
  algo   expanded max mem steps  cost
  BFS           4       4     2    22
  DFS          10       8     8    38
  IDDFS        16       3     2    22
  UCS          10       5     3    16
grid maze (steps)
  algo   expanded max mem steps  cost
  BFS          44       4    19    19
  DFS          26       5    25    25
  IDDFS       601      20    19    19
  UCS          45       4    19    19

৯ · কোনটি কখন — পরিস্থিতি দেখে বাছাই

কোনো একটি পদ্ধতি সবসময় সেরা নয়; প্রশ্নগুলো এভাবে করুন:

goal নির্দিষ্ট আর পেছনে হাঁটা সহজ হলে bidirectional ভাবুন। আর b^d যন্ত্রের সাধ্যের বাইরে হলে কোনো অন্ধ পদ্ধতিই চলবে না: তখন goal-এর দিকে অনুমান (পর্ব ৪১) বা local search (পর্ব ৪৪)।

১০ · AI-এর যুগে — AI সহকারীর লেখা search কোড যাচাই

AI সহকারী কয়েক সেকেন্ডে BFS বা UCS-এর কোড দেবে, আর ছোট উদাহরণে তা প্রায়ই ঠিকও চলবে; ভুল লুকিয়ে থাকে কিনারায়। AI সহকারীরা প্রায়ই যা করে:

• ভুল কাঠামো: queue হিসেবে list.pop(0) (প্রতিবার O(n), বড় search-এ ধীর), অথবা BFS-এ “visited” চিহ্ন বের হওয়ার সময় দেওয়া, ফলে একই node queue-তে বহুবার।
• UCS-এ তৈরির সময় goal test, যা অংশ ৬-এর মতো ২২ km ফেরত দেয়; অথবা ওজনওয়ালা graph-এ BFS দিয়ে “সবচেয়ে ছোট পথ” দাবি।
• heapq-এ তুলনা করা যায় না এমন জিনিস: (g, state_dict); g সমান হলেই TypeError. সমাধান: মাঝে একটি ক্রমিক সংখ্যা, (g, counter, state).
• বড় grid-এ recursive DFS, যা Python-এর recursion সীমা (সাধারণত ১,০০০) পার হয়ে RecursionError দেয়; বা গভীরতার সীমা ছাড়া অসীম space-এ DFS.
• জটিলতা আর তুলনার ভুল দাবি: “DFS সবসময় দ্রুত”, “IDDFS দ্বিগুণ খরচ”, বা node না গুনেই কোনটি ভালো বলে দেওয়া।

AI-এর search কোড হাতে পেলে — যাচাইয়ের চেকলিস্ট

• হাতে trace করা একটি ছোট graph-এ (৫–৬টি node) কোডের পথ, খরচ আর expand-এর ক্রম মিলিয়েছি
• frontier-এর কাঠামো দেখেছি: BFS-এ deque.popleft, DFS-এ stack, UCS-এ heapq; কোথাও list.pop(0) নেই
• goal test কোথায় হয়, দেখেছি: BFS-এ তৈরির সময় চলে, UCS-এ অবশ্যই expand-এর সময়
• চক্র ঠেকানোর ব্যবস্থা (explored set বা পথের ওপর যাচাই) আর DFS-এ গভীরতার সীমা আছে
• কোনটি ভালো, তা দাবি নয়, কোডে node গুনে আর একটি সরল baseline (যেমন BFS) পাশে রেখে দেখেছি
• অচেনা function আর parameter Python-এর অফিসিয়াল docs-এ মিলিয়েছি; আসল গ্রাহকের ঠিকানা বা রুটের ডেটা AI-তে পেস্ট করিনি