সমস্যাকে search হিসেবে দেখা — state, action আর goal

এই পর্ব দিয়ে মডিউল ৭ শুরু। মডিউল ৩ থেকে ৬ পর্যন্ত আপনি ডেটা নিয়ে কাজ করেছেন: array, টেবিল, chart আর সম্ভাবনা। এবার AI-এর আরেকটি পুরোনো আর এখনো খুব কাজের দিক: শেখার ডেটা ছাড়াই, শুধু সমস্যার নিয়ম জেনে সমাধান খুঁজে বের করা। চলমান উদাহরণ বাজারঘর (এই কোর্সের কাল্পনিক অনলাইন দোকান)। তার একজন ডেলিভারি রাইডার মিরপুরের গুদাম থেকে মতিঝিলে একটি পার্সেল নেবেন। কোন পথে যাবেন? প্রশ্নটি সহজ, কিন্তু কম্পিউটারকে দিয়ে উত্তর বের করাতে হলে আগে প্রশ্নটিকে নিখুঁতভাবে লিখতে হবে। এই পর্বের পুরো বিষয় সেই লেখার কৌশল। কোন algorithm দিয়ে খুঁজবেন, তা পরের পাঁচটি পর্বে।

১ · Agent থেকে search — কখন এটি ঠিক টুল

পর্ব ১-এ আপনি agent দেখেছেন: যে environment থেকে percept পায় আর action নেয়। সেখানে পরিবেশের ছয়টি বৈশিষ্ট্য আর পাঁচ ধরনের agent ছিল, তাই এখানে আবার বলা হবে না। শুধু একটি ধরন মনে করিয়ে দেওয়া দরকার: goal-based agent, যাকে একটি লক্ষ্য দেওয়া হয় আর সে ভেবে দেখে কোন কাজের ধারাবাহিকতা লক্ষ্যে নিয়ে যাবে। এই “ভেবে দেখা”-র সবচেয়ে সরল রূপের নাম search. পর্ব ৫-এর সমস্যার মানচিত্রে search আর planning আলাদা একটি পরিবার ছিল, যার আউটপুট একটি লেবেল বা সংখ্যা নয়, একটি সমাধান: কাজের একটি ক্রম। আর পর্ব ৩-এর তিন পথের মধ্যে এটি নিয়মভিত্তিক (symbolic) পথের অংশ: এখানে কোনো ডেটা থেকে শেখা নেই, সমস্যার নিয়ম আমরা নিজেরাই লিখে দিই।

এই “চোখ বন্ধ করে চালানো” তখনই নিরাপদ, যখন পরিবেশ চারটি শর্ত মোটামুটি মানে:

ধাঁধা (8-puzzle, Sudoku), রুট খোঁজা আর কারখানার কাজের ক্রম এই শর্তগুলোর কাছাকাছি। আবার পরের মাসের বিক্রি অনুমান বা একটি বাংলা রিভিউয়ের মনোভাব বোঝা search-এর সমস্যা নয়: সেখানে “কাজের ক্রম” বলে কিছু নেই, আছে ডেটা থেকে একটি অনুমান, যা মডিউল ১০-এর বিষয়।

২ · সমস্যার ছয়টি অংশ — রাইডারের রোড ম্যাপ

কম্পিউটারের কাছে “মতিঝিলে যাওয়ার ভালো পথ কোনটি?” কোনো স্পষ্ট প্রশ্নই নয়। তাকে ছয়টি জিনিস নির্দিষ্ট করে দিতে হয়। এই ছয়টি মিলিয়ে লেখাকে বলে problem formulation. Russell ও Norvig-এর “Artificial Intelligence: A Modern Approach” (চতুর্থ সংস্করণ, ২০২০/২০২১) বইয়ে এই কাঠামো যেভাবে সাজানো, বিশ্ববিদ্যালয়ের AI কোর্সে সাধারণত সেভাবেই পড়ানো হয়; নিচের উদাহরণগুলো এই কোর্সের নিজের।

এই ছয়টি দিলে একটি সমাধান মানে initial state থেকে লক্ষ্যে নিয়ে যাওয়া action-এর একটি ক্রম। সব সমাধানের মধ্যে যার path cost সবচেয়ে কম, সেটি optimal solution. লক্ষ করুন, ছয়টির মধ্যে প্রথম চারটি মিলে একটি graph তৈরি হয়: state হলো node, action হলো তীর, আর ধাপের খরচ তীরের ওজন। এই graph-কে বলে state-space graph. এখন রাইডারের জগৎটি দেখুন। মানচিত্রটি বানানো; এলাকার নাম সত্যি, কিলোমিটারগুলো নয়।

এবার ছয়টি অংশ এক এক করে ভরুন। Stepper-এর কোডের প্রতিটি লাইন একটি অংশের Python রূপ।

1states = set(ROADS)          # ৯টি এলাকা2initial = "Mirpur"3def actions(s): return list(ROADS[s])4def result(s, a): return a5def is_goal(s): return s == "Motijheel"6def step_cost(s, a): return ROADS[s][a]7plan = search(initial, ...)

৩ · আরও দুটি formulation — 8-puzzle আর পানির জগ

8-puzzle

8-puzzle একটি ৩ × ৩ বোর্ড, যেখানে ১ থেকে ৮ নম্বরের আটটি টাইল আর একটি ফাঁকা ঘর। ফাঁকা ঘরের পাশের একটি টাইল ঠেলে ফাঁকায় আনা যায়। লক্ষ্য একটি নির্দিষ্ট সাজানো বিন্যাস। ছয়টি অংশ:

• State: ৯টি ঘরের কোনটিতে কোন টাইল, ফাঁকা ঘরকে 0 ধরে ৯টি সংখ্যার একটি tuple, যেমন (1, 2, 3, 4, 0, 6, 7, 5, 8).
• Initial state: যেকোনো বিন্যাস, যা ধাঁধাটি দেয়।
• Actions: টাইলের বদলে ফাঁকা ঘরকে সরানো ভাবলে সহজ: Up, Down, Left, Right, বোর্ডের কিনারা যতটা দেয়। মাঝখানে ফাঁকা থাকলে ৪টি, কিনারার মাঝে ৩টি, কোণে ২টি।
• Transition model: ফাঁকা ঘর আর সেই দিকের পাশের টাইল জায়গা বদল করে।
• Goal test: state == (1, 2, 3, 4, 5, 6, 7, 8, 0).
• Path cost: প্রতিটি চাল ১, তাই পথের খরচ মানে চালের সংখ্যা।

নিচের কোড এই ছয়টি অংশকে একটি ছোট class-এ রাখে (class কী, তা Python কোর্সে)। এটি একটি state থেকে সব successor ছাপে, আর একটি ধাপ বেশি চালিয়ে লক্ষ্য খোঁজে। শেষে inversions নামের একটি গণনা আছে, যার মানে অংশ ৫-এ পরিষ্কার হবে। প্রথমবার চালালে ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে।

GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)               # 0 = blank
STEP = {"Up": -3, "Down": 3, "Left": -1, "Right": 1}  # where the blank moves

class Puzzle8:
    def __init__(self, tiles):
        self.tiles = tuple(tiles)
    def actions(self):
        r, c = divmod(self.tiles.index(0), 3)
        ok = {"Up": r > 0, "Down": r < 2, "Left": c > 0, "Right": c < 2}
        return [a for a in STEP if ok[a]]
    def result(self, action):                    # transition model
        t = list(self.tiles)
        i = t.index(0); j = i + STEP[action]
        t[i], t[j] = t[j], t[i]                  # slide one tile into the gap
        return Puzzle8(t)
    def is_goal(self):
        return self.tiles == GOAL
    def inversions(self):                        # pairs out of order, blank ignored
        t = [x for x in self.tiles if x]
        return sum(t[i] > t[j] for i in range(8) for j in range(i + 1, 8))
    def __str__(self):
        s = "".join(str(x) if x else "_" for x in self.tiles)
        return " ".join(s[k:k + 3] for k in (0, 3, 6))

start = Puzzle8([1, 2, 3, 4, 0, 6, 7, 5, 8])
print("start:", start, "| goal?", start.is_goal(), "| inversions:", start.inversions())
for a in start.actions():
    child = start.result(a)
    print(f"  {a:<5} -> {child}  goal? {child.is_goal()}")
two = start.result("Down").result("Right")
print("Down, Right:", two, "| goal?", two.is_goal())
swapped = Puzzle8([1, 2, 3, 4, 5, 6, 8, 7, 0])
print("8 and 7 swapped:", swapped, "| inversions:", swapped.inversions())
print("corner blank actions:", Puzzle8(GOAL).actions())

start: 123 4_6 758 | goal? False | inversions: 2
  Up    -> 1_3 426 758  goal? False
  Down  -> 123 456 7_8  goal? False
  Left  -> 123 _46 758  goal? False
  Right -> 123 46_ 758  goal? False
Down, Right: 123 456 78_ | goal? True
8 and 7 swapped: 123 456 87_ | inversions: 1
corner blank actions: ['Up', 'Left']

একটি state থেকে successor বানানোর কাজটিকে বলে expansion. নিচে একই শুরুর বোর্ড ধাপে ধাপে expand করে দেখুন।

পানির জগের ধাঁধা

পাড়ার চায়ের দোকানে একটি অর্ডারের জন্য ঠিক ৪ লিটার দুধ মাপা দরকার। মাপার দাগ নেই, আছে শুধু একটি ৫ লিটারের আর একটি ৩ লিটারের জগ, আর একটি কল। ধাঁধাটি পুরোনো আর নানা রূপে পরিচিত; এর formulation এমন:

• State: (a, b), যেখানে a = বড় জগে কত লিটার (0–5), b = ছোট জগে কত (0–3). মোট 6 × 4 = 24টি সম্ভাব্য জোড়া।
• Initial state: (0, 0), দুটিই খালি।
• Actions: ছয়টি: বড়টি ভরা, ছোটটি ভরা, বড়টি খালি করা, ছোটটি খালি করা, বড় থেকে ছোটতে ঢালা, ছোট থেকে বড়তে ঢালা।
• Transition model: ঢালার নিয়মটিই আসল কাজ: বড় থেকে ছোটতে ঢালা যায় min(a, 3 − b) লিটার, মানে যতক্ষণ না বড়টি খালি বা ছোটটি ভরা হয়।
• Goal test: a == 4. ছোট জগে কত আছে, তাতে কিছু যায় আসে না, তাই লক্ষ্য একটি state নয়, একটি শর্ত।
• Path cost: প্রতিটি কাজ ১।

এই formulation অংশ ৭-এর generic loop-এ বসালে (অনুশীলন ৪-এ নিজে লিখে দেখবেন) সমাধান আসে ৬ ধাপে: বড়টি ভরা (5, 0), ছোটতে ঢালা (2, 3), ছোটটি খালি (2, 0), আবার ঢালা (0, 2), বড়টি ভরা (5, 2), ছোটতে ঢালা (4, 3). হাতে মিলিয়ে নিন: শেষ ধাপে ছোট জগে মাত্র ১ লিটারের জায়গা ছিল, তাই বড়টিতে ঠিক ৪ লিটার থাকে। ২৪টি জোড়ার মধ্যে কিন্তু শুরু থেকে মাত্র ১৬টিতে পৌঁছানো যায়; যেমন (2, 2) কখনো হয় না, কারণ প্রতিটি কাজের পর অন্তত একটি জগ হয় খালি নয়তো ভরা থাকে।

৪ · Abstraction — state-এ কী রাখবেন, কী বাদ দেবেন

রাইডারের আসল যাত্রায় হাজারটা জিনিস আছে: বাইকের তেলের মিলিলিটার, রেডিওতে কী গান বাজছে, আকাশে মেঘ, প্রতিটি সেকেন্ডের GPS অবস্থান। আমরা এসব ফেলে দিয়ে শুধু “কোন এলাকায়” রেখেছি। এই বাদ দেওয়ার নাম abstraction. এটি অলসতা নয়, এটিই formulation-এর সবচেয়ে বড় সিদ্ধান্ত।

একটি abstraction ঠিক আছে কি না, তা যাচাইয়ের একটি সহজ পরীক্ষা: সরল মডেলের প্রতিটি সমাধান কি আসল জগতে চালানো যায়? “মিরপুর থেকে ফার্মগেট” একটি action হিসেবে কাজ করে, কারণ আসল রাইডার যেকোনো সময় এটি করতে পারেন, ভেতরের খুঁটিনাটি তিনি নিজেই সামলান। দ্বিতীয় পরীক্ষা: বাদ দেওয়া কোনো তথ্য কি সিদ্ধান্ত বদলে দিতে পারে? যদি তেল এত কম থাকে যে উত্তরা ঘুরে আসা যায় না, তাহলে তেল বাদ দেওয়া abstraction আর ঠিক নেই।

একই সমস্যার খারাপ আর ভালো state নকশা

বাজারঘরের একটি নতুন সমস্যা ধরুন। একজন রাইডার গুদাম থেকে ৩টি পার্সেল তিনটি ঠিকানায় দেবেন, যেকোনো ক্রমে, তারপর গুদামে ফিরবেন। State-এ কী থাকবে?

লক্ষ করুন, “খুব কম” নকশাটি দেখতে সবচেয়ে সরল, কিন্তু এটি ভুল উত্তর দেবে, কারণ এতে দুটি সত্যিকারের ভিন্ন অবস্থা এক হয়ে গেছে। তাই নিয়মটি দুই দিকেই খাটে: সিদ্ধান্ত বদলাতে পারে এমন সব কিছু রাখুন, বাকি সব ফেলে দিন। পার্সেলের সংখ্যা বাড়ালে এই state space দ্রুত বাড়ে: ২০টি পার্সেলে বাকি-তালিকা 2²⁰ = 1,048,576 রকম। এটি travelling salesman ধরনের সমস্যা, যার কঠিনতার কথা মডিউল ৭-এর শেষ পর্বগুলোতে আবার আসবে।

৫ · State space কত বড় — 8-puzzle-এর 181,440

৯টি ঘরে ৮টি টাইল আর একটি ফাঁকা ঘর যত রকমে সাজানো যায়, তা 9! = 9 × 8 × … × 1 = 362,880 (! চিহ্নের মানে factorial, ১ পর্যন্ত সব সংখ্যার গুণফল)। কিন্তু একটি চমক আছে: এর ঠিক অর্ধেক বিন্যাস লক্ষ্য থেকে কখনো পৌঁছানো যায় না, যত চালই দিন। কেন?

Parity-র যুক্তি, সহজ ভাষায়

ফাঁকা ঘর বাদ দিয়ে টাইলগুলো বাঁ থেকে ডানে, ওপর থেকে নিচে একটি সারিতে পড়ুন। তারপর গুনুন কতগুলো জোড়া “উল্টো ক্রমে” আছে, মানে বড় সংখ্যা ছোট সংখ্যার আগে। একে বলে inversion-এর সংখ্যা। লক্ষ্যে (12345678) একটিও নেই, তাই 0. ওপরের কোডের শুরুর বোর্ড 123 4_6 758 পড়লে 1 2 3 4 6 7 5 8: উল্টো জোড়া (6, 5) আর (7, 5), মোট ২।

এবার দেখুন একটি চালে এই সংখ্যার কী হয়। পাশাপাশি চাল (Left বা Right) টাইলের পড়ার ক্রম বদলায় না, কারণ টাইলটি একই সারিতে ফাঁকার এক ঘর এদিক-ওদিক যায়; inversion একই থাকে। ওপর-নিচের চাল (Up বা Down) একটি টাইলকে পড়ার ক্রমে ঠিক দুটি টাইল ডিঙিয়ে নিয়ে যায় (একই সারির বাকি দুটি ঘর)। সেই দুটি টাইলের প্রতিটির সঙ্গে জোড়াটি হয় উল্টো হয়, নয়তো সোজা হয়; তাই inversion বদলায় +2, 0 বা −2. দুটি ক্ষেত্রেই inversion-এর জোড়-বিজোড় (parity) বদলায় না। লক্ষ্যের inversion 0, জোড়; তাই লক্ষ্য থেকে পৌঁছানো প্রতিটি বিন্যাসের inversion জোড়। যে বিন্যাসে inversion বিজোড়, যেমন ওপরের “8 আর 7 অদলবদল” (১টি), তা কখনো সমাধান করা যায় না।

এই যুক্তি দেখায় “অর্ধেকের বেশি পৌঁছানো যায় না”। ঠিক অর্ধেকই যে পৌঁছানো যায়, অর্থাৎ জোড় parity-র প্রতিটি বিন্যাস, তার প্রমাণ একটু লম্বা। তার বদলে আমরা গুনে দেখি: লক্ষ্য থেকে BFS চালিয়ে (যার বিস্তারিত পর্ব ৪০-এ) প্রতিটি পৌঁছানো state একবার করে গোনা। পুরো গণনা ব্রাউজারে চালানো যায়, কিন্তু কয়েক সেকেন্ড পাতা আটকে থাকতে পারে, তাই এটি লেখকের যন্ত্রে একটি সাধারণ Python script হিসেবে চালানো হয়েছে।

# count_states.py (মূল অংশ; পুরো script-এ জগের ধাঁধাও আছে)
GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)
NEIGH = {i: [j for j in (i - 3, i + 3, i - 1, i + 1)
             if 0 <= j < 9 and (j // 3 == i // 3 or j % 3 == i % 3)]
         for i in range(9)}
depth = {GOAL: 0}
q = deque([GOAL])
while q:
    s = q.popleft()
    i = s.index(0)
    for j in NEIGH[i]:
        t = list(s); t[i], t[j] = t[j], t[i]; t = tuple(t)
        if t not in depth:
            depth[t] = depth[s] + 1
            q.append(t)
…

সত্যিকারের run, Python 3.14.4 (শুধু standard library):

~/bazarghar-ai$ python count_states.py
Python 3.14.4
all arrangements 9!     : 362,880
reachable from goal     : 181,440
9!/2                    : 181,440
odd-inversion reachable : 0
even-inversion arrangements: 181,440
deepest optimal solution: 31 moves, states: 2
mean optimal solution   : 21.97 moves
states by depth 0..10   : [1, 2, 4, 8, 16, 20, 39, 62, 116, 152, 286]
BFS time                : 0.23 s
15-puzzle 16!/2         : 10,461,394,944,000
jug states reachable    : 16 of 24
jug plan                : fill5 pour5to3 empty3 pour5to3 fill5 pour5to3 | steps: 6

15-puzzle কেন অনেক বড়

৪ × ৪ বোর্ডের 15-puzzle-এ ১৬টি ঘর। একই ধরনের parity যুক্তি (তবে বোর্ডের চওড়া জোড় বলে নিয়মে ফাঁকা ঘরের সারিও গুনতে হয়) দেখায় যে এখানেও ঠিক অর্ধেক পৌঁছানো যায়: 16!/2 = 10,461,394,944,000, প্রায় 1.05 × 10¹³. বোর্ডে মাত্র সাতটি ঘর বাড়তেই state বেড়েছে 16!/9! = 57,657,600 গুণ, প্রায় পৌনে ছয় কোটি গুণ। প্রতিটি state-এর জন্য মাত্র ১ byte রাখলেও প্রায় ১০ terabyte লাগবে; তাই 15-puzzle-এ “সব state গুনে রাখা” আর সাধারণ যন্ত্রে চলে না, আর 24-puzzle (৫ × ৫)-এ সংখ্যাটি প্রায় 7.8 × 10²⁴. এখানেই heuristic-এর দরকার, যা পর্ব ৪১-এর বিষয়। এই হঠাৎ বিস্ফোরণকে বলে combinatorial explosion.

৬ · Search tree বনাম state graph — repeated state আর explored set

State-space graph হলো জগতের মানচিত্র: প্রতিটি state একবার। Search algorithm কিন্তু মানচিত্রটি আগে থেকে হাতে পায় না; সে শুরু থেকে এক এক করে পথ বাড়ায়। সে যে পথগুলো ধরে, সেগুলো একটি গাছ তৈরি করে, যার নাম search tree. গাছের প্রতিটি node একটি পথের শেষ বিন্দু: তাতে থাকে state, কোন parent থেকে এসেছে, কোন action-এ, আর এ পর্যন্ত খরচ। একই state অনেক পথে আসতে পারে, তাই গাছে একই state অনেক node-এ থাকতে পারে।

এই পুনরাবৃত্তিকে বলে repeated state. চক্র থাকলে search tree অসীম: S → A → S → A → … চিরকাল চলতে পারে। চক্র না থাকলেও ক্ষতি আছে: একই state-এ পৌঁছানোর অনেক পথ থাকলে গাছ সেই state-এর নিচের পুরো অংশ বারবার খোঁজে। 8-puzzle-এ প্রতিটি চালের উল্টো চাল আছে (Down-এর পর Up), তাই এখানে চক্র সব জায়গায়; ওপরের stepper-এর শেষ ধাপে আপনি একটি দেখেছেন।

প্রতিকার সহজ: যে state একবার expand হয়েছে, তাদের একটি set-এ লিখে রাখা, আর আবার এলে বাদ দেওয়া। এই set-ই explored set (কোনো বইয়ে reached set বা closed list). এটি রাখলে algorithm-টির নাম graph search, না রাখলে tree search. নিচের কোড ওপরের ছবির graph-টিতে দুটিকে পাশাপাশি চালায় আর expansion গোনে। Tree search-কে ২,০০০ expansion-এ থামানো হয়েছে, যাতে পাতা আটকে না যায়।

from collections import deque

G = {"S": "AB", "A": "SBC", "B": "SAD", "C": "ADG", "D": "BC", "G": "C"}

def run(start, goal, use_explored, cap=2000):
    frontier = deque([(start, start)])           # (state, path so far)
    explored, expanded = set(), 0
    while frontier and expanded < cap:
        state, path = frontier.popleft()         # FIFO frontier
        if state == goal:
            return path, expanded, len(frontier)
        if use_explored:
            if state in explored: continue
            explored.add(state)
        expanded += 1
        for nxt in G[state]:
            if not (use_explored and nxt in explored):
                frontier.append((nxt, path + nxt))
    return None, expanded, len(frontier)

for goal in ["G", "Z"]:
    for name, flag in [("graph search", True), ("tree search ", False)]:
        path, n, left = run("S", goal, flag)
        print(f"goal {goal} | {name} | path {path} | expanded {n:>4} | frontier {left}")

level, sizes = ["S"], []                         # search tree, level by level
for d in range(7):
    sizes.append(len(level))
    level = [n for s in level for n in G[s]]
print("tree nodes per depth:", sizes, "| distinct states:", len(G))

goal G | graph search | path SACG | expanded    5 | frontier 0
goal G | tree search  | path SACG | expanded   16 | frontier 25
goal Z | graph search | path None | expanded    6 | frontier 0
goal Z | tree search  | path None | expanded 2000 | frontier 3184
tree nodes per depth: [1, 2, 6, 15, 39, 99, 252] | distinct states: 6

৭ · Generic search loop — frontier নীতি একটি parameter

এবার মূল কাঠামো। প্রায় প্রতিটি classical search algorithm একই loop: frontier থেকে একটি node তোলা, লক্ষ্য কি না দেখা, না হলে expand করা, আর সন্তানদের frontier-এ রাখা। Frontier হলো সেই node-গুলোর তালিকা, যা তৈরি হয়েছে কিন্তু এখনো expand হয়নি, মানে খোঁজা এলাকার সীমানা। Algorithm-গুলোর পার্থক্য শুধু একটি প্রশ্নে: frontier থেকে পরের কোনটি তোলা হবে?

Queue, stack আর heap কীভাবে বানানো হয়, তা DSA কোর্সে আছে; এখানে শুধু ব্যবহার। নিচের কোডে search function সমস্যার অর্থ কিছুই জানে না: সে নেয় একটি শুরুর state, একটি goal test, একটি successor function আর একটি frontier object. Frontier-এর শুধু দুটি method লাগে, push আর pop. এখানে একটি FIFO দেওয়া হয়েছে, Python-এর deque থেকে বানিয়ে; পরের পর্বগুলো একই loop-এ অন্য frontier বসাবে।

from collections import deque, defaultdict

EDGES = [("Mirpur", "Mohammadpur", 5), ("Mirpur", "Farmgate", 7),
         ("Mirpur", "Banani", 6), ("Mirpur", "Uttara", 12),
         ("Mohammadpur", "Dhanmondi", 3), ("Mohammadpur", "Farmgate", 4),
         ("Farmgate", "Dhanmondi", 4), ("Farmgate", "Gulshan", 6),
         ("Farmgate", "Motijheel", 6), ("Banani", "Gulshan", 2),
         ("Banani", "Uttara", 9), ("Gulshan", "Badda", 3),
         ("Badda", "Motijheel", 7), ("Dhanmondi", "Motijheel", 4)]
ROADS = defaultdict(dict)                 # invented km, two-way roads
for a, b, km in EDGES:
    ROADS[a][b] = km; ROADS[b][a] = km
class FIFO(deque):                        # frontier policy: first in, first out
    push = deque.append
    pop = deque.popleft

def search(start, is_goal, successors, frontier):
    frontier.push((start, [start], 0))    # (state, path, path cost)
    explored, expanded = set(), 0
    while frontier:
        state, path, cost = frontier.pop()
        if is_goal(state): return path, cost, expanded
        if state in explored: continue
        explored.add(state); expanded += 1
        for nxt, km in successors(state):
            if nxt not in explored:
                frontier.push((nxt, path + [nxt], cost + km))
    return None, None, expanded

path, cost, n = search("Mirpur", lambda s: s == "Motijheel",
                       lambda s: ROADS[s].items(), FIFO())
print("path    :", " -> ".join(path), "|", len(path) - 1, "roads")
print("cost    :", cost, "km | expanded:", n, "of", len(ROADS), "areas")
alt = ["Mirpur", "Mohammadpur", "Dhanmondi", "Motijheel"]
print("another :", sum(ROADS[a][b] for a, b in zip(alt, alt[1:])), "km via Dhanmondi")

path    : Mirpur -> Farmgate -> Motijheel | 2 roads
cost    : 13 km | expanded: 7 of 9 areas
another : 12 km via Dhanmondi

এবার একই loop ছোট ৬ node-এর graph-এ (অংশ ৬-এর graph) এক ধাপ এক ধাপ করে চলতে দেখুন। প্রতিটি ধাপে frontier থেকে বাঁ দিকের node-টি তোলা হয়।

1frontier.push(S)2while frontier:3    s = frontier.pop()4    if is_goal(s): return path5    if s in explored: continue6    explored.add(s)7    push children not explored

৮ · Search algorithm মাপার চার মাপকাঠি — b, d আর m

পরের পর্বগুলোতে অনেক algorithm আসবে। তাদের তুলনা হবে চারটি প্রশ্নে:

DSA কোর্সে graph algorithm-এর খরচ লেখা হয় O(V + E) দিয়ে, যেখানে V আর E হলো node আর edge-এর সংখ্যা (Big-O-র ঝালাই)। AI-এর search-এ সেটি প্রায়ই কাজে আসে না, কারণ graph-টি হাতে নেই, আর তার আকার 10¹³ বা অসীম হতে পারে। তাই খরচ লেখা হয় তিনটি সংখ্যায়:

• b, branching factor: একটি node-এর সর্বোচ্চ (বা গড়) কতগুলো successor.
• d, depth: সবচেয়ে কাছের (সবচেয়ে কম ধাপের) সমাধানের গভীরতা।
• m, maximum depth: যেকোনো পথের সর্বোচ্চ দৈর্ঘ্য; চক্র থাকলে tree search-এ এটি অসীম।

Depth d পর্যন্ত একটি পূর্ণ গাছে node থাকে 1 + b + b² + … + b^d, যা b-এর বেশ বড় মানে প্রায় b^d. তাই ধাপে ধাপে স্তর ধরে খোঁজা algorithm-এর খরচ সাধারণত O(b^d) লেখা হয়। হাতে একটি হিসাব: b = 3, d = 5 হলে শেষ স্তরে 3⁵ = 243টি node, আর মোট 1 + 3 + 9 + 27 + 81 + 243 = 364টি। শেষ স্তরেই মোটের দুই-তৃতীয়াংশ, এটিই exponential বৃদ্ধির চেহারা।

8-puzzle-এর গড় b আসে ফাঁকা ঘরের ৯টি অবস্থানের গড় থেকে: ৪টি কোণে ২টি করে, ৪টি কিনারায় ৩টি করে, মাঝে ৪টি, মোট (8 + 12 + 4) ÷ 9 ≈ 2.67. নিচের কোড b^d-এর বৃদ্ধি একটি টেবিলে আর log-scale chart-এ দেখায়, আর একটি অনুমানে time ও memory-র হিসাব করে: প্রতি সেকেন্ডে দশ লক্ষ node আর প্রতি node ১,০০০ byte. এই দুটি সংখ্যা উদাহরণের জন্য ধরা, কোনো যন্ত্রের মাপা মান নয়।

import numpy as np
import matplotlib.pyplot as plt

d = np.arange(0, 13)
bs = [2, 3, 4, 10]
print(" d" + "".join(f"{'b=' + str(b):>15}" for b in bs))
for k in [2, 4, 6, 8, 10]:
    print(f"{k:>2}" + "".join(f"{b**k:>15,}" for b in bs))

# all nodes of a full tree down to depth d: 1 + b + b^2 + ... + b^d
total = sum(10**k for k in range(13))
print("b=10, d=12 total nodes:", f"{total:,}")
rate, per_node = 1_000_000, 1_000                # assumed: 1e6 nodes/s, 1 KB/node
print(f"at {rate:,} nodes/s: {total / rate / 86400:,.1f} days")
print(f"memory at {per_node} bytes/node: {total * per_node / 1e12:,.0f} TB")

fig, ax = plt.subplots(figsize=(6, 4))
for b in bs:
    ax.plot(d, [float(b) ** k for k in d], marker="o", ms=3, label=f"b = {b}")
ax.axhline(181_440, color="gray", ls="--", lw=1)
ax.text(0.2, 2.5e5, "8-puzzle reachable states (181,440)", fontsize=8, color="gray")
ax.set_yscale("log")
ax.set_xlabel("depth d")
ax.set_ylabel("nodes at depth d (b^d)")
ax.set_title("Search tree growth")
ax.legend(fontsize=8)
plt.show()

 d            b=2            b=3            b=4           b=10
 2              4              9             16            100
 4             16             81            256         10,000
 6             64            729          4,096      1,000,000
 8            256          6,561         65,536    100,000,000
10          1,024         59,049      1,048,576 10,000,000,000
b=10, d=12 total nodes: 1,111,111,111,111
at 1,000,000 nodes/s: 12.9 days
memory at 1000 bytes/node: 1,111 TB

৯ · বাস্তবে search, আর মডিউলের বাকি পথ

Search শুধু খেলনা ধাঁধার জন্য নয়, যদিও আসল সিস্টেমগুলো এই পর্বের সরল loop-এর চেয়ে অনেক জটিল, আর কোম্পানিগুলো নিজেদের ভেতরের নকশা সব সময় প্রকাশ করে না:

• রুট খোঁজা: মানচিত্রের অ্যাপ আর ডেলিভারি সিস্টেম রাস্তার graph-এ সবচেয়ে কম সময়ের পথ খোঁজে। প্রকাশিত গবেষণা অনুযায়ী বড় রাস্তার জালে সাধারণ Dijkstra বা A*-এর সঙ্গে আগে থেকে হিসাব রাখার (preprocessing) নানা কৌশল যোগ হয়, আর যানজটের খবর এলে খরচ বদলায়।
• ধাঁধা আর খেলা: 8-puzzle, Rubik's cube, Sudoku; প্রতিপক্ষ থাকলে search-এর রূপ বদলায় (পর্ব ৪২)।
• Planning: একটি গুদামের রোবট বা একটি কারখানার কাজের ক্রম। ১৯৭০-এর দশকের শুরুতে Stanford Research Institute-এর Shakey রোবটের জন্য STRIPS নামের planning ভাষা তৈরি হয়েছিল, যার ধারা পর্ব ৪৯-এ দেখবেন।
• রোবটের নড়াচড়া (motion planning): অবিচ্ছিন্ন জায়গাকে আগে grid বা নমুনা বিন্দুতে ভাগ করে graph বানানো হয়, তারপর খোঁজা; grid মোটা হলে সরু পথ হারায়।

এই মডিউলের বাকি পাঁচটি পর্ব এই পর্বের কাঠামোর ওপরই দাঁড়াবে। পর্ব ৪০ (অন্ধ search — BFS, DFS আর uniform cost)-এ একই loop-এ queue, stack আর priority queue বসিয়ে তাদের completeness, optimality, time ও space মাপা হবে। পর্ব ৪১ (Heuristic আর A*)-এ লক্ষ্যের দূরত্বের অনুমান যোগ হবে। পর্ব ৪২-এ খেলার search, পর্ব ৪৩-এ constraint satisfaction, যেখানে state-এর ভেতরের গঠন কাজে লাগে, আর পর্ব ৪৪-এ local search, যেখানে পথ নয়, শুধু একটি ভালো state খোঁজা হয়।

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

AI সহকারীর কাছে একটি ধাঁধার জন্য BFS চাইলে সে কয়েক সেকেন্ডে কোড দেবে, আর ছোট উদাহরণে তা প্রায়ই ঠিকঠাক চলবে। সমস্যা ধরা পড়ে বড় বা কিনারার উদাহরণে। Search কোডে AI সহকারীরা প্রায়ই যা করে:

• Explored set ভুলে যাওয়া, বা state list হিসেবে রেখে set-এ ঢোকাতে গিয়ে TypeError: unhashable type, তারপর সেটি এড়াতে str(state)-এর মতো ভঙ্গুর কৌশল।
• list.pop(0) দিয়ে queue, যা প্রতিবার পুরো list সরায়; বড় frontier-এ খুব ধীর। collections.deque ঠিক পছন্দ।
• ভুল দাবি: ওজনসহ graph-এ BFS-কে “সবচেয়ে ছোট পথ” বলা, বা 8-puzzle-এর 9! = 362,880টি state সবই সমাধানযোগ্য বলা। এ ধরনের বিশ্বাসযোগ্য কিন্তু ভুল সংখ্যা সহজে চোখ এড়ায়।
• বানানো বা পুরোনো API: কোনো library-তে নেই এমন function, বা ভুল parameter-এর নাম। যেমন NetworkX-এ আসল function nx.astar_path, কিন্তু অনুমানে লেখা নাম আলাদা হতে পারে।
• Formulation-এর ভুল চাপা পড়া: state-এ দরকারি তথ্য না রাখা (অংশ ৪-এর “খুব কম” নকশা), বা অসাধ্য শুরুর state-এ অসীম loop, যা কোড ঠিক থাকলেও উত্তর ভুল করে।

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

• হাতে জানা ছোট উদাহরণে (২ চালের ধাঁধা, ৬ node-এর graph) পথ, খরচ আর expansion-এর সংখ্যা মিলিয়েছি
• সমাধান নেই এমন একটি ক্ষেত্রে চালিয়ে দেখেছি যে কোড থামে আর স্পষ্ট করে “সমাধান নেই” বলে
• State hash করা যায় (tuple বা frozenset), আর explored set সত্যিই repeated state বাদ দেয়
• Frontier কোন নীতিতে চলে (FIFO, LIFO, priority) তা দেখেছি, আর “optimal” দাবিটি সেই নীতি আর path cost-এর সঙ্গে মেলে কি না ভেবেছি
• State-এ সিদ্ধান্তের জন্য দরকারি সব তথ্য আছে, অপ্রাসঙ্গিক কিছু নেই; goal test সত্যিকারের লক্ষ্য ধরে
• অচেনা প্রতিটি library function অফিসিয়াল docs-এ মিলিয়েছি, আর কোনো আসল ঠিকানা বা গ্রাহকের তথ্য AI-তে পেস্ট করিনি