গ্রাফ অ্যালগরিদম৮ মিনিট পড়া

এ* (A*) সার্চ

ডাইকস্ট্রার চেয়ে বুদ্ধিমান — সঠিক দিকে এগোতে একটি ইঙ্গিত ব্যবহার করুন
time:O(E) সবচেয়ে ভালো ক্ষেত্রে, O((V+E) log V) সবচেয়ে খারাপ ক্ষেত্রেoptimality:হিউরিস্টিক গ্রহণযোগ্য হলে নিশ্চিতheuristic:h(n) ≤ লক্ষ্যে পৌঁছানোর প্রকৃত খরচ

কল্পনা করুন আপনি জিপিএস (GPS) দিয়ে পথ চলছেন। ডাইকস্ট্রার অ্যালগরিদম এমন একটি জিপিএসের মতো যার গন্তব্য কোথায় সে সম্পর্কে কোনো ধারণা নেই — এটি পুকুরে ঢিল ছোড়ার মতো সমানভাবে সব দিকে ছড়িয়ে পড়ে, যতক্ষণ না এটি আপনার গন্তব্যে পৌঁছায়।

এ* (A-star) হলো এমন একটি জিপিএস যা মোটামুটিভাবে জানে গন্তব্য কোন দিকে। সব দিকে ছড়িয়ে পড়ার পরিবর্তে, এটি হিউরিস্টিক (heuristic) নামক একটি অনুমানের সাহায্যে গন্তব্যের দিকে অনুসন্ধানকে পক্ষপাতদুষ্ট (bias) করে। ফলাফল: এটি অনেক কম নোড অন্বেষণ করে গন্তব্যে পৌঁছায়।

মূল্যায়ন ফাংশন (The Evaluation Function): f(n) = g(n) + h(n)

প্রতিটি নোড n একটি অগ্রাধিকার স্কোর পায়:

  • g(n) — শুরু থেকে n পর্যন্ত এখন পর্যন্ত জানা সেরা পথের প্রকৃত খরচ
  • h(n) — n থেকে লক্ষ্য পর্যন্ত খরচের হিউরিস্টিক অনুমান
  • f(n) = g(n) + h(n) — n এর মধ্য দিয়ে যাওয়া সবচেয়ে সস্তা পথের আনুমানিক মোট খরচ

অগ্রাধিকার কিউ (priority queue) f(n) দ্বারা সাজানো হয়। কম আনুমানিক মোট খরচ সহ নোডগুলো আগে প্রসারিত হয়। এটি স্বাভাবিকভাবেই অনুসন্ধানকে গন্তব্যের দিকে নিয়ে যায়।

যখন সমস্ত n এর জন্য h(n) = 0 হয়, তখন f(n) = g(n) হয় এবং এ* হুবহু ডাইকস্ট্রার অ্যালগরিদমে পরিণত হয়। এ* হলো একটি কঠোর সাধারণীকরণ (strict generalization)।

গ্রহণযোগ্যতা (Admissibility) — নির্ভুলতার চাবিকাঠি

একটি হিউরিস্টিক h গ্রহণযোগ্য হবে যদি এটি কখনও প্রকৃত খরচকে বেশি অনুমান না করে: সমস্ত n এর জন্য h(n) ≤ actual_cost(n, goal)।

যদি h বেশি অনুমান করে, তবে এ* সর্বোত্তম পথটিকে কম অগ্রাধিকার দিতে পারে (ভেবে যে এটি বাস্তবের চেয়ে বেশি ব্যয়বহুল) এবং একটি উপ-সর্বোত্তম (suboptimal) পথে থিতু হতে পারে। গ্রহণযোগ্যতা গ্যারান্টি দেয় যে এ* প্রথমবার গন্তব্যে পৌঁছালে, তা সর্বোত্তম পথ দিয়েই হবে।

গ্রহণযোগ্য হিউরিস্টিকের উদাহরণ:

  • ম্যানহাটন দূরত্ব (Manhattan distance) |Δx| + |Δy| — ৪-দিকের গ্রিড চলাচলের জন্য
  • ইউক্লিডীয় দূরত্ব (Euclidean distance) √(Δx² + Δy²) — মুক্ত-দিকের চলাচলের জন্য

ধারাবাহিকতা (Consistency) — দক্ষতার গ্যারান্টি

একটি শক্তিশালী বৈশিষ্ট্য: h ধারাবাহিক হবে যদি c খরচের প্রতিটি প্রান্ত (n, n') এর জন্য আমাদের কাছে h(n) ≤ c + h(n') থাকে। এটি হিউরিস্টিকের ক্ষেত্রে প্রযোজ্য ত্রিভুজ অসমতা (triangle inequality)। ধারাবাহিকতা গ্রহণযোগ্যতা বোঝায় এবং অতিরিক্তভাবে নিশ্চিত করে যে প্রতিটি নোড কেবল একবার প্রক্রিয়া করা হয় — ডাইকস্ট্রার মতো কোনো পুনরায় সম্প্রসারণের (re-expansions) প্রয়োজন নেই।

ব্যবহারিক প্রভাব

১০০০×১০০০ গ্রিডে, কোনো পথ খুঁজে পেতে ডাইকস্ট্রা প্রায় ৫০০,০০০ নোড অন্বেষণ করতে পারে। ম্যানহাটন দূরত্বের সাথে এ* হয়তো মাত্র ৫,০০০ অন্বেষণ করতে পারে — ১০০ গুণ গতি বৃদ্ধি। হিউরিস্টিক যত ভালো হবে (অতিক্রম না করে প্রকৃত খরচের কাছাকাছি), এ* তত কম নোড অন্বেষণ করবে।

কখন এ* বনাম ডাইকস্ট্রা ব্যবহার করবেন

এ* ব্যবহার করুন যখন: আপনার একটি একক লক্ষ্য আছে এবং একটি অর্থপূর্ণ হিউরিস্টিক উপলব্ধ। ডাইকস্ট্রা ব্যবহার করুন যখন: আপনার সব গন্তব্যের জন্য ক্ষুদ্রতম পথের প্রয়োজন, অথবা কোনো ভালো হিউরিস্টিক নেই (h = 0 এমনিতেই ডাইকস্ট্রাতে পরিণত হয়)। গেম পাথফাইন্ডিং, জিপিএস নেভিগেশন এবং রোবোটিক্সে এ* একটি স্ট্যান্ডার্ড অ্যালগরিদম।

দ্রষ্টব্য: হিউরিস্টিক হলো একটি প্রতিশ্রুতি: 'লক্ষ্য থেকে আমরা কত দূরে তা আমি কখনও বাড়িয়ে অনুমান করব না।' সেই প্রতিশ্রুতি ভঙ্গ করলে এ* একটি উপ-সর্বোত্তম পথ ফিরিয়ে দিতে পারে। এটি বজায় রাখুন, এবং এ* সর্বোত্তম এবং ডাইকস্ট্রার চেয়ে সম্ভাব্য অনেক দ্রুত হবে।

গ্রিডে এ* (ম্যানহাটন দূরত্ব হিউরিস্টিক)

import heapq


def astar(grid, start, goal):
    """
    grid: 2D list, 0=free, 1=wall
    Returns shortest path length, or -1 if unreachable.
    """
    rows, cols = len(grid), len(grid[0])
    def h(r, c):  # Manhattan distance heuristic
        return abs(r - goal[0]) + abs(c - goal[1])


    dist = {start: 0}
    # heap: (f, g, node)
    heap = [(h(*start), 0, start)]


    while heap:
        f, g, (r, c) = heapq.heappop(heap)
        if (r, c) == goal:
            return g
        if g > dist.get((r, c), float('inf')):
            continue  # stale entry
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                ng = g + 1
                if ng < dist.get((nr, nc), float('inf')):
                    dist[(nr, nc)] = ng
                    heapq.heappush(heap, (ng + h(nr, nc), ng, (nr, nc)))
    return -1


grid = [
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
print(astar(grid, (0,0), (4,4)))  # 12
Output
12

Complexity

🎯 সেরা ক্ষেত্র (নিখুঁত হিউরিস্টিক)
যদি h = সঠিক অবশিষ্ট খরচ হয়, এ* কেবল সর্বোত্তম পথের নোডগুলোই প্রসারিত করে
কেবল সর্বোত্তম পথে অন্বেষণ করে O(path length)
🌊 সবচেয়ে খারাপ ক্ষেত্র (h = 0)
কোনো হিউরিস্টিক তথ্য ছাড়া, এ* ডাইকস্ট্রার মতো সমানভাবে চারদিকে অন্বেষণ করে
ডাইকস্ট্রার মতো আচরণ করে O((V+E) log V)
💾 স্পেস (Space)
সবচেয়ে খারাপ ক্ষেত্রে ওপেন এবং ক্লোজড সেটগুলো সমস্ত শীর্ষবিন্দু ধারণ করতে পারে
অন্বেষিত নোডের আনুপাতিক O(V)
✅ অপ্টিমালিটি (Optimality)
অগ্রহণযোগ্য হিউরিস্টিক উপ-সর্বোত্তম পথ খুঁজে পেতে পারে তবে এটি দ্রুত কাজ করে — আনুমানিক রেজাল্ট দরকার এমন ক্ষেত্রে এটি কার্যকর
গ্রহণযোগ্য হিউরিস্টিক প্রয়োজন h(n) ≤ true cost

ছোট কুইজ

f(n) = g(n) + h(n) কী উপস্থাপন করে?

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