Heuristic আর A* — অনুমান দিয়ে দ্রুত পথ

আগের পর্বে (পর্ব ৪০ · অন্ধ search — BFS, DFS আর uniform cost) দেখেছেন, BFS, DFS আর UCS লক্ষ্য কোন দিকে তা জানে না। তারা চারদিকে সমানভাবে ছড়ায়, ঠিক যেন অন্ধকার ঘরে হাতড়ে চাবি খোঁজা। কিন্তু বাস্তবের বেশিরভাগ সমস্যায় আমরা লক্ষ্যের দিক মোটামুটি জানি। মিরপুর থেকে মতিঝিলের দিকে যাওয়া রিকশাচালক উত্তরা হয়ে ঘোরার কথা ভাবেন না, কারণ উত্তরা উল্টো দিকে। এই “মোটামুটি জানা” কে একটি সংখ্যায় লিখলে তাকে বলে heuristic. এই পর্বের প্রশ্ন: এই অনুমান search-কে কতটা দ্রুত করে, আর কখন অনুমান ভুল হলেও উত্তর ঠিক থাকে? Search সমস্যার গঠন (state, action, goal, path cost) পর্ব ৩৯-এ; graph, BFS আর Dijkstra-র ডেটা-স্ট্রাকচারের দিক DSA কোর্সের graph, BFS, Dijkstra আর heap পর্বে আছে। এখানে সেগুলো আবার শেখানো হবে না।

১ · Heuristic কী — বাকি পথের একটি সস্তা অনুমান

বাজারঘরের (এই কোর্সের কাল্পনিক অনলাইন দোকান) একজন ডেলিভারি রাইডার মিরপুরের গুদাম থেকে মতিঝিলের এক ক্রেতার কাছে যাবেন। নিচের ম্যাপে ঢাকার ১২টি এলাকা আর ১৯টি রাস্তা। সব দূরত্ব আর অবস্থান বানানো, শুধু শেখার জন্য; এলাকার নাম আসল হলেও কিলোমিটারগুলো আসল নয়। প্রতিটি এলাকার একটি কাল্পনিক (x, y) স্থানাঙ্ক আছে কিলোমিটারে, যাতে দুই এলাকার মধ্যে সরলরেখার দূরত্ব হিসাব করা যায়।

প্রতিটি node n-এর জন্য তিনটি সংখ্যা মনে রাখুন:

• g(n): শুরু থেকে n পর্যন্ত এখন পর্যন্ত পাওয়া পথের আসল খরচ (যা ইতিমধ্যে চলা হয়েছে)।
• h(n): n থেকে লক্ষ্য পর্যন্ত বাকি খরচের অনুমান, যা heuristic function দেয়।
• h*(n): n থেকে লক্ষ্যের আসল সেরা খরচ, যা আমরা জানি না (জানলে search লাগত না)।

ম্যাপে সবচেয়ে স্বাভাবিক heuristic হলো সরলরেখার দূরত্ব, মানে Euclidean distance: h(n) = √((x_n − x_{লক্ষ্য})² + (y_n − y_{লক্ষ্য})²). মিরপুর (2, 9) আর মতিঝিল (6, 0)-এর মধ্যে এটি √(16 + 81) = √97 ≈ 9.85 km. কাকের উড়ে যাওয়ার দূরত্ব কখনো রাস্তার দূরত্বের চেয়ে বেশি হতে পারে না, কারণ দুই বিন্দুর মধ্যে সবচেয়ে ছোট পথ সরলরেখা। এই ম্যাপে প্রতিটি রাস্তার দৈর্ঘ্য তার দুই প্রান্তের সরলরেখার দূরত্বের সমান বা বেশি রাখা হয়েছে; নিচের কোডের একটি assert প্রতিটি রাস্তায় এটি যাচাই করে।

নিচের টেবিলে প্রতিটি এলাকার h আর আসল সেরা বাকি খরচ h* পাশাপাশি (h* বের করা হয়েছে মতিঝিল থেকে উল্টো দিকে Dijkstra চালিয়ে, লেখকের যন্ত্রে)। লক্ষ করুন, প্রতিটি সারিতে h ≤ h*: অনুমান কখনো বাড়িয়ে বলে না।

Grid-এর জগতে (একটি গোলকধাঁধা, যেখানে শুধু উপরে-নিচে-ডানে-বাঁয়ে এক ঘর করে যাওয়া যায়) সরলরেখার চেয়ে ভালো অনুমান Manhattan distance: |Δসারি| + |Δকলাম|. দেয়াল না থাকলে এটিই হুবহু আসল খরচ, আর দেয়াল থাকলে পথ শুধু লম্বা হয়, তাই এটিও কখনো বাড়িয়ে বলে না। নামটি এসেছে নিউইয়র্কের Manhattan-এর ছকের মতো রাস্তা থেকে, যেখানে কোনাকুনি যাওয়া যায় না।

২ · Greedy best-first search — f = h, দ্রুত কিন্তু সেরা নয়

সবচেয়ে সরল ধারণা: frontier থেকে সবসময় সেই node তুলুন, যা লক্ষ্যের সবচেয়ে কাছে মনে হয়, মানে যার h সবচেয়ে ছোট। এর নাম greedy best-first search. এখানে priority হলো f(n) = h(n); এ পর্যন্ত কত পথ চলা হলো (g), তা হিসাবে নেই। লোভী (greedy) কারণ প্রতিটি ধাপে শুধু সামনের সবচেয়ে লোভনীয় দিকটি দেখে।

ম্যাপে হাতে চালিয়ে দেখুন। মিরপুর expand করলে চার প্রতিবেশী: মোহাম্মদপুর (h 7.07), ফার্মগেট (5.39), গুলশান (8.25), উত্তরা (15.0). সবচেয়ে ছোট h ফার্মগেটের, তাই সেটি আগে। ফার্মগেট থেকে তেজগাঁও (h 5.00) আর ধানমন্ডি (h 3.61). ধানমন্ডি মতিঝিলের সরলরেখায় বেশি কাছে, তাই greedy ধানমন্ডি বাছে। ধানমন্ডি থেকে মতিঝিল (h 0), আর লক্ষ্য পাওয়া গেল। মোট পথ 5 + 4 + 6 = 15 km, মাত্র ৪টি node expand করে।

কিন্তু তেজগাঁও হয়ে পথ 5 + 3 + 6 = 14 km. ধানমন্ডি সরলরেখায় কাছে হলেও সেখান থেকে মতিঝিলের রাস্তা ঘুরপথে 6 km, আর ফার্মগেট থেকে ধানমন্ডি যেতেই 4 km লেগেছে, যা greedy দেখেনি। এটিই greedy-র মূল দুর্বলতা: যে পথ চলতে ইতিমধ্যে কত খরচ হলো, তা উপেক্ষা করা। ফলে greedy-র optimality-র কোনো নিশ্চয়তা নেই: পাওয়া পথটি সবচেয়ে কম খরচের হবে, এমন কথা বলা যায় না।

৩ · A* — চলা পথ আর বাকি অনুমান একসঙ্গে, f = g + h

সমাধানটি সরল: দুটি তথ্যই নিন। f(n) = g(n) + h(n), মানে “n হয়ে গেলে পুরো পথের আনুমানিক খরচ”। g হলো শুরু থেকে n পর্যন্ত আসল খরচ, h হলো n থেকে লক্ষ্যের অনুমান। frontier থেকে সবসময় সবচেয়ে ছোট f-এর node তোলা হয়, আর লক্ষ্য node যখন frontier থেকে তোলা হয় (শুধু খুঁজে পাওয়া নয়), তখন থামা হয়। এটিই A* (উচ্চারণ “এ-স্টার”)। দুটি চরম রূপ মনে রাখুন: h = 0 হলে f = g, মানে UCS; আর g-কে বাদ দিলে f = h, মানে greedy. A* দুইয়ের মাঝখানে।

নিচের stepper-এ একই ম্যাপে A*-এর প্রতিটি ধাপ। frontier-এর প্রতিটি entry লেখা আছে “এলাকা g + h = f” আকারে, ছোট f আগে।

1n = frontier.pop_min_f()2if n == goal: return path3for m in neighbours(n):4    g2 = g[n] + km(n, m)5    if g2 < g[m]: push(m, g2 + h(m))

এবার তিনটি অ্যালগরিদম একই কোডে, শুধু priority function বদলে। best_first function একটি f(g, n) নেয়: UCS-এ g, greedy-তে h(n), A*-এ g + h(n). frontier হলো Python-এর heapq, যা একটি min-heap (সবচেয়ে ছোট মান আগে ওঠে)। প্রথমবার চালালে ব্রাউজারে Python নামতে কয়েক সেকেন্ড লাগতে পারে।

import heapq, math
XY = {"Mirpur": (2, 9), "Uttara": (6, 15), "Mohammadpur": (1, 5), "Farmgate": (4, 5),
      "Gulshan": (8, 8), "Tejgaon": (6, 5), "Dhanmondi": (3, 2), "Badda": (10, 6),
      "Rampura": (9, 3), "Lalbagh": (2, 0), "Motijheel": (6, 0), "Khilgaon": (9, 0)}
ROADS = """Mirpur Uttara 9, Mirpur Mohammadpur 5, Mirpur Farmgate 5, Mirpur Gulshan 7,
Uttara Gulshan 8, Mohammadpur Dhanmondi 4, Mohammadpur Lalbagh 6, Farmgate Tejgaon 3,
Farmgate Dhanmondi 4, Gulshan Badda 3, Gulshan Tejgaon 4, Tejgaon Motijheel 6,
Badda Rampura 4, Rampura Khilgaon 4, Rampura Motijheel 5, Dhanmondi Motijheel 6,
Dhanmondi Lalbagh 3, Lalbagh Motijheel 5, Khilgaon Motijheel 3"""
G = {n: [] for n in XY}
for r in ROADS.split(","):
    a, b, km = r.split(); km = int(km)
    assert km >= math.dist(XY[a], XY[b])      # রাস্তা কখনো সরলরেখার চেয়ে ছোট নয়
    G[a].append((b, km)); G[b].append((a, km))
h = lambda n: math.dist(XY[n], XY["Motijheel"])   # straight-line distance

def best_first(start, goal, f):          # f(g, n) দিয়ে frontier সাজানো
    frontier, best, expanded = [(f(0, start), 0, start, [start])], {start: 0}, []
    while frontier:
        _, g, n, path = heapq.heappop(frontier)
        if g > best[n]: continue          # পুরোনো, বেশি খরচের entry
        expanded.append(n)
        if n == goal: return path, g, expanded
        for m, km in G[n]:
            if g + km < best.get(m, math.inf):
                best[m] = g + km
                heapq.heappush(frontier, (f(g + km, m), g + km, m, path + [m]))

for name, f in [("UCS    f=g", lambda g, n: g), ("Greedy f=h", lambda g, n: h(n)),
                ("A*   f=g+h", lambda g, n: g + h(n))]:
    path, cost, ex = best_first("Mirpur", "Motijheel", f)
    print(f"{name}: {cost} km, expanded {len(ex):2} | {' > '.join(path)}")
print("h(Mirpur) =", round(h("Mirpur"), 2), "km; true best = 14 km")

UCS    f=g: 14 km, expanded 10 | Mirpur > Farmgate > Tejgaon > Motijheel
Greedy f=h: 15 km, expanded  4 | Mirpur > Farmgate > Dhanmondi > Motijheel
A*   f=g+h: 14 km, expanded  6 | Mirpur > Farmgate > Tejgaon > Motijheel
h(Mirpur) = 9.85 km; true best = 14 km

৪ · Admissible heuristic — কেন A* সেরা পথ দেয়, আর বাড়িয়ে বললে কী হয়

একটি heuristic admissible যদি প্রতিটি node-এ h(n) ≤ h*(n), মানে কখনো আসল বাকি খরচের চেয়ে বেশি না বলে। এটি একটি আশাবাদী অনুমান: “অন্তত এতটুকু তো লাগবেই।” সরলরেখার দূরত্ব আর grid-এর Manhattan distance দুটিই admissible, যা অংশ ১-এর টেবিলে দেখেছেন।

সহজ যুক্তি: আশাবাদী অনুমান কোনো ভালো পথ লুকাতে পারে না

ধরুন A* লক্ষ্যে একটি পথ পেয়েছে, খরচ C. অন্য কোনো, এখনো না-খোলা, পথ যদি আরও সস্তা হতো, তাহলে সেই পথের কোনো একটি node n এই মুহূর্তে frontier-এ বসে আছে। সেই n-এর f(n) = g(n) + h(n). h কখনো বাড়িয়ে বলে না, তাই f(n) ≤ ওই সস্তা পথের আসল মোট খরচ < C. অর্থাৎ f(n) লক্ষ্যের f = C-এর চেয়ে ছোট, তাই A* লক্ষ্য তোলার আগেই n-কে তুলত। ফলে A* কখনো একটি খরচ-বেশি লক্ষ্য আগে তুলে থামতে পারে না। ক্রিকেটের ভাষায়: সম্ভাব্য সর্বনিম্ন রান যার এখনো আমাদের সেরা স্কোরের চেয়ে কম, তাকে বাদ দেওয়া যায় না।

উল্টোটা দেখুন। রাইডারের নিজের অভিজ্ঞতা থেকে বানানো একটি অনুমান-টেবিল ভাবুন, যেখানে সব এলাকায় সরলরেখার দূরত্বই আছে, শুধু তেজগাঁওয়ের পাশে লেখা “জ্যাম, 12 km”. অথচ তেজগাঁও থেকে মতিঝিলের আসল খরচ মাত্র 6 km. এক জায়গায় এই বাড়িয়ে বলাই যথেষ্ট:

1h_bad = straight_line.copy()2h_bad["Tejgaon"] = 12   # আসল h* = 63A*(f = g + h_bad)

এই run-টি লেখকের যন্ত্রে অংশ ৩-এর একই best_first দিয়ে চালানো হয়েছে, শুধু h বদলে; ফল ছিল (['Mirpur', 'Farmgate', 'Dhanmondi', 'Motijheel'], 15). মজার ব্যাপার, inadmissible heuristic সবসময় ভুল পথ দেয় না; শুধু নিশ্চয়তা হারায়। কোথায় বাড়িয়ে বলা হলো, তার ওপর নির্ভর করে ফল ঠিক থাকতেও পারে। কিন্তু “সাধারণত ঠিক আসে” আর “প্রমাণসহ সবসময় ঠিক” এক কথা নয়।

৫ · Consistency — ত্রিভুজ-অসমতা আর graph search-এ আবার খোলা

একটি heuristic consistent (কখনো monotone-ও বলা হয়) যদি প্রতিটি রাস্তা n → n′-এর জন্য:

h(n) ≤ c(n, n′) + h(n′)

এখানে c(n, n′) হলো n থেকে n′-এর এক ধাপের খরচ। এটি একটি triangle inequality (ত্রিভুজ-অসমতা): n থেকে লক্ষ্যের অনুমান, এক ধাপ চলে n′ থেকে লক্ষ্যের অনুমানের সঙ্গে সেই ধাপের খরচ যোগের চেয়ে বেশি হতে পারবে না। সহজ কথায়, এক ধাপ এগোলে অনুমান ধাপের খরচের চেয়ে বেশি কমতে পারে না। সরলরেখার দূরত্ব এটি মানে, কারণ ত্রিভুজের এক বাহু অন্য দুই বাহুর যোগের চেয়ে বড় নয়; Manhattan distance grid-এ এক ধাপে ঠিক 1 বা তার কম বদলায়। লেখকের যন্ত্রে ম্যাপের ১৯টি রাস্তার দুই দিকেই পরীক্ষা করে একটিও অসঙ্গত রাস্তা পাওয়া যায়নি।

কেন দরকার? Consistent হলে একটি পথ ধরে f কখনো কমে না: f(n′) = g(n) + c + h(n′) ≥ g(n) + h(n) = f(n). ফলে কোনো node প্রথমবার যখন frontier থেকে ওঠে, তখনই তার g সেরা। তাই graph search একবার খোলা node-কে closed set-এ রেখে নিশ্চিন্তে ভুলে যেতে পারে। Consistent হলে admissible-ও হয় (লক্ষ্য থেকে উল্টো দিকে এই অসমতা যোগ করলেই আসে), কিন্তু উল্টোটা সবসময় নয়।

একটি ছোট উদাহরণ, যা হাতে মিলিয়ে নেওয়া যায়। রাস্তা: S → A (1), S → B (3), A → B (1), B → G (3). সেরা পথ S → A → B → G, খরচ 5. Heuristic: h(S) = 0, h(A) = 4, h(B) = 1, h(G) = 0. এটি admissible (h*(A) = 4, h*(B) = 3), কিন্তু A → B রাস্তায় h(A) = 4 > 1 + h(B) = 2, তাই inconsistent.

লেখকের যন্ত্রে দুই রূপই চালিয়ে মেলানো হয়েছে: closed node না খুললে পথ SBG, খরচ 6; আবার খুললে SABG, খরচ 5. অর্থাৎ শুধু admissible heuristic নিয়ে graph search করলে হয় closed node আবার খোলার ব্যবস্থা রাখতে হবে (আরও কাজ), নয়তো heuristic consistent হতে হবে। বাস্তবে বেশিরভাগ স্বাভাবিক admissible heuristic (সরলরেখা, Manhattan, পরের অংশের h1 আর h2) consistent-ও, তাই সমস্যাটি সাধারণত হাতে বানানো বা কয়েকটি heuristic মেশানোর সময় দেখা দেয়।

৬ · Grid গোলকধাঁধায় A* — Manhattan distance আর কতগুলো ঘর খুলতে হলো

গুদামের ভেতরে একটি পণ্য-তোলার রোবট বা একটি ভিডিও গেমের চরিত্র ভাবুন, যে ঘরে ঘরে চলে: উপরে, নিচে, ডানে বা বাঁয়ে, প্রতি ধাপে খরচ 1. কিছু ঘরে দেয়াল (তাক)। লক্ষ্য (r_T, c_T) হলে Manhattan heuristic h(r, c) = |r − r_T| + |c − c_T|. নিচের কোড একটি ২০ × ২০ grid বানায়, যার প্রায় ২৮% ঘরে এলোমেলো দেয়াল (seed 7, তাই সবার একই ছবি)। একই astar function একটি ওজন w নেয়: w = 0 মানে h-কে শূন্য ধরা, অর্থাৎ UCS; w = 1 মানে সাধারণ A*. সমান f-এ ছোট h-এর ঘর আগে ওঠে (tie-breaking). এই block-এর function পরের অংশের weighted A* block-ও ব্যবহার করবে।

import heapq
import numpy as np
import matplotlib.pyplot as plt

def astar(wall, S, T, w=1.0):            # w = 0 হলে UCS, w = 1 হলে A*
    H, W = wall.shape
    h = lambda p: abs(p[0] - T[0]) + abs(p[1] - T[1])    # Manhattan
    g, par, closed = {S: 0}, {S: None}, set()
    fr = [(w * h(S), 0, 0, S)]           # (f, w*h, g, ঘর)
    while fr:
        f, _, gs, p = heapq.heappop(fr)
        if p in closed: continue
        closed.add(p)
        if p == T: break
        for q in ((p[0]+1, p[1]), (p[0]-1, p[1]), (p[0], p[1]+1), (p[0], p[1]-1)):
            if 0 <= q[0] < H and 0 <= q[1] < W and not wall[q] and gs + 1 < g.get(q, 1e9):
                g[q], par[q] = gs + 1, p
                heapq.heappush(fr, (gs + 1 + w * h(q), w * h(q), gs + 1, q))
    path, p = [], T
    while p is not None: path.append(p); p = par.get(p)
    return g.get(T), closed, path[::-1]

rng = np.random.default_rng(7)
wall = rng.random((20, 20)) < 0.28
S, T = (0, 0), (19, 19)
wall[S] = wall[T] = False
fig, axes = plt.subplots(1, 2, figsize=(8, 4))
for ax, w, name in zip(axes, (0, 1), ("UCS (h = 0)", "A* (Manhattan h)")):
    cost, closed, path = astar(wall, S, T, w)
    img = np.where(wall, 0.0, 1.0)
    for c in closed: img[c] = 0.6       # expand হওয়া ঘর ধূসর
    ax.imshow(img, cmap="gray", vmin=0, vmax=1)
    ax.plot([c[1] for c in path], [c[0] for c in path], "r-", lw=2)
    ax.set_title(f"{name}: cost {cost}, expanded {len(closed)}"); ax.axis("off")
    print(name, "| cost:", cost, "| expanded:", len(closed), "| free cells:", (~wall).sum())

UCS (h = 0) | cost: 42 | expanded: 275 | free cells: 283
A* (Manhattan h) | cost: 42 | expanded: 166 | free cells: 283

৭ · 8-puzzle — দুটি heuristic, dominance আর effective branching factor

8-puzzle হলো ৩ × ৩ বোর্ডে ১ থেকে ৮ নম্বরের আটটি টাইল আর একটি ফাঁকা ঘর। ফাঁকার পাশের একটি টাইলকে ফাঁকায় সরানো একটি action, খরচ 1. লক্ষ্য: উপরের সারি 1 2 3, মাঝে 4 5 6, নিচে 7 8 আর ফাঁকা। বোর্ডের সব সাজানো 9! = 362,880 রকম, কিন্তু শুধু অর্ধেক, 181,440টি, লক্ষ্য থেকে পৌঁছানো যায়; লেখকের যন্ত্রে লক্ষ্য থেকে BFS চালিয়ে ঠিক এই সংখ্যা আর সবচেয়ে কঠিন অবস্থার জন্য 31 ধাপ পাওয়া গেছে। দুটি পরিচিত heuristic:

• h1 = ভুল ঘরে থাকা টাইলের সংখ্যা (ফাঁকা গোনা হয় না)। প্রতিটি ভুল টাইলকে অন্তত একবার সরাতেই হবে, তাই h1 ≤ h*.
• h2 = প্রতিটি টাইলের নিজের লক্ষ্য-ঘর পর্যন্ত Manhattan distance-এর যোগ। প্রতিটি সরানো একটি টাইলকে ঠিক এক ঘর এগোয়, তাই h2 ≤ h*.

1অবস্থা    লক্ষ্য25 1 3     1 2 334 _ 2     4 5 647 8 6     7 8 _

Dominance — বড় admissible heuristic ভালো

প্রতিটি অবস্থায় h2 ≥ h1, কারণ যে টাইল ভুল ঘরে, তার Manhattan distance অন্তত 1. দুটিই admissible হলে আর সব node-এ h2 ≥ h1 হলে বলা হয় h2, h1-কে dominate করে। তখন A*-h2 কখনো A*-h1-এর চেয়ে বেশি node expand করে না (tie-breaking বাদে): A* f(n) < C*-এর প্রায় সব node খোলে, মানে h(n) < C* − g(n), আর বড় h-এ এই শর্ত কম node পূরণ করে। লেখকের যন্ত্রে ১,৮১,৪৪০টি অবস্থার প্রতিটিতে পরীক্ষা করে h1 ≤ h*, h2 ≤ h* আর h1 ≤ h2 তিনটিই সত্য পাওয়া গেছে।

Effective branching factor b*

বিভিন্ন গভীরতার সমস্যায় অ্যালগরিদম তুলনা করতে একটি সংখ্যা চাই। Branching factor b মানে প্রতিটি node থেকে গড়ে কতটি সন্তান। Effective branching factor b* হলো সেই b, যার একটি সুষম গাছ d গভীরতায় ঠিক N + 1টি node রাখে:

N + 1 = 1 + b* + (b*)² + … + (b*)^d

এখানে N হলো search-এর দেখা node-এর সংখ্যা, d সমাধানের গভীরতা। b* যত 1-এর কাছে, heuristic তত সরাসরি লক্ষ্যের দিকে নিয়ে যায়। একটি হাতে হিসাব: d = 2-এ N = 6 হলে 1 + b + b² = 7, তাই b² + b − 6 = 0, b* = 2. Russell ও Norvig তাঁদের বইয়ে N হিসেবে তৈরি হওয়া (generated) node গোনেন; এই পর্বের কোড expand হওয়া node গোনে, তাই এখানকার b* তাঁদের সংখ্যার চেয়ে ছোট আসে। ধারা জোড়া মেলানো যায় না বলে b* বের করা হয় bisection দিয়ে: একটি সীমার মাঝখান নিয়ে বারবার অর্ধেক করা।

নিচের কোড লক্ষ্য থেকে এলোমেলো চাল দিয়ে (আগের অবস্থায় না ফিরে) তিনটি সমাধানযোগ্য puzzle বানায়, seed 1. লক্ষ্য থেকে উল্টো চাল দিয়ে বানানো বলে প্রতিটি অবশ্যই সমাধানযোগ্য। তারপর UCS (h = 0), A*-h1 আর A*-h2 চালিয়ে expand হওয়া node আর b* দেখায়। পাতার ভেতরে গভীরতা ছোট রাখা হয়েছে, কারণ UCS গভীরতা ২০-এ চল্লিশ হাজারের বেশি node খোলে; বড় গভীরতা নিচে ডেস্কটপের run-এ।

import heapq, random
GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)               # 0 = ফাঁকা ঘর
POS = {t: divmod(i, 3) for i, t in enumerate(GOAL)}
def h1(s): return sum(1 for i, t in enumerate(s) if t and t != GOAL[i])
def h2(s): return sum(abs(i // 3 - POS[t][0]) + abs(i % 3 - POS[t][1])
                      for i, t in enumerate(s) if t)
def h0(s): return 0                               # h = 0 মানে UCS
def moves(s):
    z = s.index(0); r, c = divmod(z, 3)
    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        if 0 <= r + dr < 3 and 0 <= c + dc < 3:
            j = (r + dr) * 3 + c + dc; t = list(s)
            t[z], t[j] = t[j], t[z]; yield tuple(t)
def astar(s, h):
    best, fr, closed = {s: 0}, [(h(s), 0, s)], set()
    while fr:
        f, g, x = heapq.heappop(fr)
        if x in closed: continue
        closed.add(x)
        if x == GOAL: return g, len(closed)       # খরচ, expand হওয়া node
        for y in moves(x):
            if g + 1 < best.get(y, 99):
                best[y] = g + 1; heapq.heappush(fr, (g + 1 + h(y), g + 1, y))
def bstar(N, d):                     # N + 1 = 1 + b + ... + b^d, bisection
    lo, hi = 1.0, 3.0
    for _ in range(40):
        b = (lo + hi) / 2
        lo, hi = (b, hi) if sum(b**i for i in range(d + 1)) < N + 1 else (lo, b)
    return b
rng = random.Random(1); print(" d   UCS  A*h1  A*h2 | b*h1  b*h2")
for walk in (8, 12, 16):             # পাতায় ছোট গভীরতা; বড়গুলো ডেস্কটপে
    s, prev = GOAL, None
    for _ in range(walk): s, prev = rng.choice([m for m in moves(s) if m != prev]), s
    (d, n0), (_, n1), (_, n2) = astar(s, h0), astar(s, h1), astar(s, h2)
    print(f"{d:2} {n0:5} {n1:5} {n2:5} | {bstar(n1, d):.2f}  {bstar(n2, d):.2f}")

 d   UCS  A*h1  A*h2 | b*h1  b*h2
 8   180    20    16 | 1.20  1.15
12  1249    79    20 | 1.27  1.08
16  8211   563    88 | 1.37  1.18

ডেস্কটপে বড় পরীক্ষা — প্রতিটি গভীরতায় ২০টি puzzle

লেখকের যন্ত্রে সত্যিকারের run (Python 3.14.4, শুধু standard library). একই astar, h1, h2 আর bstar; পার্থক্য হলো, প্রথমে লক্ষ্য থেকে পুরো BFS চালিয়ে প্রতিটি অবস্থার আসল দূরত্ব বের করা হয়েছে, তারপর প্রতিটি জোড় গভীরতা d থেকে ঠিক d দূরত্বের ২০টি অবস্থা এলোমেলোভাবে (seed 2026) নেওয়া হয়েছে। টেবিলে expand হওয়া node-এর গড়, আর সেই গড় থেকে b*.

~/bazarghar-ai$ python puzzle_bench.py
reachable states: 181440 | max depth: 31
h1 <= h* everywhere: True
h2 <= h* everywhere: True
h1 <= h2 everywhere: True

mean nodes expanded over 20 random puzzles per depth (seed 2026)
 d      UCS    A*-h1  A*-h2 | b*UCS b*h1  b*h2
 4        22       5      5 | 1.81  1.10  1.09
 6        72      10      8 | 1.79  1.13  1.08
 8       192      16     12 | 1.74  1.16  1.08
10       506      40     20 | 1.71  1.24  1.13
12      1310      93     32 | 1.69  1.29  1.15
14      3340     233     65 | 1.67  1.34  1.19
16      8679     576    123 | 1.66  1.37  1.22
18     19938    1357    218 | 1.65  1.39  1.23
20     44102    3488    447 | 1.63  1.41  1.25
22     79249    8334    994 | 1.60  1.43  1.28
24    122546   18479   1830 | 1.56  1.43  1.28
total time 17 s, Python 3.14.4

তিনটি পর্যবেক্ষণ। এক, গভীরতা ২৪-এ UCS গড়ে ১,২২,৫৪৬টি node খোলে, পুরো ১,৮১,৪৪০-এর দুই-তৃতীয়াংশ; A*-h2 মাত্র ১,৮৩০টি, প্রায় ৬৭ গুণ কম। দুই, b*UCS গভীরতার সঙ্গে কমছে (1.81 থেকে 1.56), কারণ state space সসীম আর graph search আগে দেখা অবস্থা বাদ দেয়, তাই গাছটি আসলে সুষম নয়। তিন, A*-h1 আর A*-h2-এর পার্থক্য গভীরতার সঙ্গে বাড়ে: d = 8-এ মাত্র 16 বনাম 12, d = 24-এ ১০ গুণ। এসব একটি যন্ত্রের একটি run, expand-গণনা দিয়ে; generated node গুনলে বা অন্য tie-breaking নিলে সংখ্যা বদলাবে, কিন্তু ক্রম (UCS > h1 > h2) বদলানোর কথা নয়।

৮ · Heuristic বানানো — নিয়ম শিথিল করা আর pattern database

h1 আর h2 আকাশ থেকে পড়েনি। দুটিই একই কৌশলে পাওয়া যায়: সমস্যার কিছু নিয়ম তুলে দিয়ে একটি সহজ সমস্যা বানানো, যাকে বলে relaxed problem, আর সেই সহজ সমস্যার আসল সেরা খরচকে মূল সমস্যার heuristic হিসেবে নেওয়া। 8-puzzle-এর নিয়ম: “একটি টাইল A থেকে B-তে যেতে পারে, যদি A আর B পাশাপাশি হয় এবং B ফাঁকা হয়।”

• “B ফাঁকা হতে হবে” শর্তটি তুলে দিলে প্রতিটি টাইল অন্যদের ওপর দিয়ে পাশের ঘরে যেতে পারে; সেরা খরচ হয় প্রতিটি টাইলের Manhattan distance-এর যোগ, মানে h2.
• দুটি শর্তই তুলে দিলে প্রতিটি টাইল এক চালে যেকোনো ঘরে লাফ দিতে পারে; সেরা খরচ হয় ভুল ঘরের টাইলের সংখ্যা, মানে h1.

কেন এভাবে পাওয়া heuristic admissible? মূল সমস্যার প্রতিটি সমাধান শিথিল সমস্যারও একটি সমাধান (নিয়ম কমলে আগের সব বৈধ চাল বৈধই থাকে), তাই শিথিল সমস্যার সেরা খরচ মূলের সেরা খরচের চেয়ে বেশি হতে পারে না। আর এটি শিথিল সমস্যার আসল খরচ বলে consistent-ও হয়। ম্যাপের সরলরেখার দূরত্বও একই কৌশল: “শুধু রাস্তা ধরে চলতে হবে” নিয়মটি তুলে দিলে রাইডার কাকের মতো সোজা উড়ে যেতে পারেন।

কয়েকটি admissible heuristic থাকলে, যার কোনোটি অন্যটিকে সব জায়গায় dominate করে না, প্রতিটি node-এ তাদের সর্বোচ্চটি নেওয়া যায়: h(n) = max(h_a(n), h_b(n)). সর্বোচ্চটিও admissible (প্রতিটি ≤ h*), আর প্রত্যেকটিকে dominate করে। খরচ: প্রতিটি node-এ সবগুলো হিসাব করতে হয়।

৯ · Weighted A*, memory-র সমস্যা আর বাস্তবে A*

অনেক সময় একেবারে সেরা পথের চেয়ে দ্রুত উত্তর বেশি জরুরি: গেমের চরিত্রকে এক ফ্রেমের মধ্যে নড়তে হবে, রাইডারকে এখনই একটি রুট দিতে হবে। Weighted A* heuristic-কে একটি ওজন w ≥ 1 দিয়ে গুণ করে:

f(n) = g(n) + w · h(n)

w = 1 হলে সাধারণ A*; w বড় হলে আচরণ greedy-র দিকে যায়। Ira Pohl ১৯৭০ সালের আশেপাশে এই ধরনের ওজন নিয়ে কাজ করেন বলে পরিচিত। এর একটি সুন্দর নিশ্চয়তা আছে: h admissible হলে weighted A*-এর পাওয়া পথের খরচ সেরা খরচের সর্বোচ্চ w গুণ। আগের grid block-এর astar function দিয়ে এবার ৬০ × ৬০ grid (প্রায় ৩০% দেয়াল, seed 6):

# আগের grid block-এর astar() এখানে আবার ব্যবহার হচ্ছে (একই namespace)
rng = np.random.default_rng(6)
big = rng.random((60, 60)) < 0.30
S2, T2 = (0, 0), (59, 59)
big[S2] = big[T2] = False
print("free cells:", (~big).sum(), "| Manhattan h(start) =", 59 + 59)
opt = None
for w in (0, 1, 1.5, 3):
    cost, closed, path = astar(big, S2, T2, w)
    opt = opt or cost                # w = 0 (UCS) দেয় আসল সেরা খরচ
    print(f"w = {w:<3}  cost = {cost:3}  ({cost / opt:.2f} x optimal)"
          f"  expanded = {len(closed):4}")

free cells: 2516 | Manhattan h(start) = 118
w = 0    cost = 126  (1.00 x optimal)  expanded = 2467
w = 1    cost = 126  (1.00 x optimal)  expanded = 1455
w = 1.5  cost = 152  (1.21 x optimal)  expanded =  831
w = 3    cost = 174  (1.38 x optimal)  expanded =  754

Memory: A*-এর আসল দুর্বলতা

A* প্রতিটি দেখা node মনে রাখে: frontier আর explored দুটিই। গভীরতা ২৪-এর 8-puzzle-এ এটি সমস্যা নয়, কিন্তু ১৫-puzzle-এ (৪ × ৪ বোর্ড) পৌঁছানো যায় এমন অবস্থা 16!/2, প্রায় ১০ লক্ষ কোটি (১.০৫ × ১০^১৩); কঠিন উদাহরণে A* সময় শেষ হওয়ার অনেক আগেই memory শেষ করে ফেলে। IDA* (iterative deepening A*, Richard Korf ১৯৮৫) এর একটি সমাধান: DFS-এর মতো এক পথ ধরে গভীরে যায়, কিন্তু যে node-এর f একটি সীমা ছাড়ায়, সেখানে থামে। এক দফা শেষ হলে সীমাটিকে সবচেয়ে ছোট ছাড়িয়ে-যাওয়া f-এ বাড়িয়ে আবার শুরু। memory লাগে শুধু বর্তমান পথের সমান, আর admissible h-এ উত্তর optimal থাকে; দাম হলো একই node বারবার দেখা। Korf এই পদ্ধতিতে ১৫-puzzle-এর এলোমেলো উদাহরণগুলোর সেরা সমাধান বের করেছিলেন বলে পরিচিত। একই উদ্দেশ্যে RBFS আর SMA*-এর মতো আরও কিছু পদ্ধতি আছে, যা এখানে শুধু নামে রইল।

বাস্তবে A* কোথায়

• গেমের pathfinding: অনেক ভিডিও গেমে চরিত্রের পথ খুঁজতে grid বা navigation mesh (হাঁটার উপযোগী জায়গাকে বহুভুজে ভাগ করা ম্যাপ)-এর ওপর A* বা তার রূপভেদ ব্যবহার হয়, এটি গেম-ডেভেলপমেন্টের বই আর লেখায় ব্যাপকভাবে বর্ণিত। কোনাকুনি চলা গেলে Manhattan আর admissible থাকে না; তখন octile distance (অনুশীলন ৪) লাগে। গতির জন্য প্রায়ই weighted A* বা আগে থেকে হিসাব করা তথ্য ব্যবহার হয়।
• রুট খোঁজা: মহাদেশ-আকারের সড়ক-জালে (কোটি কোটি সংযোগ) সরল A* একা যথেষ্ট দ্রুত নয়। গবেষণায় আগে থেকে হিসাব রেখে search দ্রুত করার নানা পদ্ধতি আছে, যেমন landmark আর ত্রিভুজ-অসমতা দিয়ে আরও ভালো admissible heuristic বানানো (ALT, Goldberg ও Harrelson ২০০৫) বা contraction hierarchies. কোন বাণিজ্যিক ম্যাপ-অ্যাপ ঠিক কী ব্যবহার করে, তা সাধারণত প্রকাশিত নয়, তাই এখানে কোনো দাবি করা হচ্ছে না। ট্রাফিকের মতো বদলানো খরচ সমস্যাকে আরও জটিল করে।

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

“Python-এ A* লিখে দাও” বললে AI সহকারী কয়েক সেকেন্ডে চলনসই কোড দেয়, আর সেই কোড প্রায়ই একটি পথ ফেরত দেয়ও। সমস্যা হলো, পথটি সেরা কি না তা চোখে দেখে বোঝা যায় না। এই বিষয়ে AI সহকারীরা প্রায়ই যা করে:

• লক্ষ্য খুঁজে পাওয়ামাত্র থামা: লক্ষ্যকে frontier-এ ঢোকানোর সময় থামলে A*-এর optimality-র যুক্তি ভেঙে যায় (অংশ ৩-এর ধাপ ৪-এ 15 km-এর মতো)। থামতে হয় লক্ষ্য frontier থেকে তোলার সময়।
• ভুল heuristic: কোনাকুনি চলা যায় এমন grid-এ Manhattan, বা km-এর ম্যাপে মিনিটে মাপা h; একক না মেলালে admissibility হারায়।
• closed set-এর ভুল: inconsistent heuristic-এ closed node আর না খোলা, বা উল্টো দিকে, closed set একেবারে না রেখে বারবার একই node খোলা।
• heap-এর খুঁটিনাটি: ভালো g পেলে পুরোনো entry বাদ না দেওয়া, অথবা heapq-এ তুলনা করা যায় না এমন বস্তু (যেমন dict) রাখা, ফলে সমান f-এ TypeError.
• বানানো তুলনা: “A* সবসময় BFS-এর চেয়ে ১০ গুণ দ্রুত” ধরনের সাধারণ দাবি, বা না চালিয়েই node-সংখ্যার টেবিল। লাভ heuristic আর সমস্যার ওপর নির্ভর করে, মাপতে হয়।

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

• একই সমস্যায় h = 0 (UCS) চালিয়ে দেখেছি, A*-এর খরচ হুবহু মেলে
• লক্ষ্য-পরীক্ষা হয় frontier থেকে তোলার সময়, আর পুরোনো বেশি-খরচের heap entry বাদ পড়ে
• heuristic admissible কি না যুক্তি দিয়ে বা ছোট সমস্যায় আসল h*-এর সঙ্গে মিলিয়ে দেখেছি; একক (km, মিনিট, ধাপ) এক
• closed set থাকলে heuristic consistent কি না দেখেছি, নইলে reopen রাখা আছে
• node-সংখ্যা আর সময়ের প্রতিটি দাবি নিজে চালিয়ে মেপেছি, seed লিখে রেখেছি
• লাইব্রেরির (যেমন heapq) আচরণ অফিসিয়াল docs-এ মিলিয়েছি; আসল ক্রেতার ঠিকানা বা ব্যক্তিগত ডেটা AI-তে পেস্ট করিনি