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

হিউরিস্টিক সার্চ (Heuristic Search)

স্মার্ট অনুমানের সাহায্যে দ্রুত সার্চ করা
scope:কোর কনসেপ্ট (মূল ধারণা)difficulty:বিগিনার (Beginner)

গোলকধাঁধায় কম্পাস

আমাদের 'স্টেট স্পেস সার্চ (State Space Search)'-এর সেই গোলকধাঁধা বা মেজ (maze)-টির কথা মনে আছে? বিএফএস (BFS) বা ডিএফএস (DFS)-এর মতো সার্চ অ্যালগরিদমগুলো আসলে অন্ধের (blind) মতো চলে — তারা জানেই না বের হওয়ার রাস্তাটি ঠিক কোন দিকে। তারা শুধু নিয়ম মেনে সব দিকে খুঁজতে থাকে আর আশা করে যে একসময় হয়তো পথটা পাওয়া যাবে।

এখন ধরুন, আপনার কাছে একটি কম্পাস (compass) আছে, যা সবসময় আপনাকে বের হওয়ার রাস্তার দিকটাই দেখায়। এর মানে এই নয় যে আপনি দেয়াল ভেদ করে দেখতে পাচ্ছেন, কিন্তু আপনার অন্তত একটা দিকের সেন্স (sense of direction) আছে। এখন রাস্তায় কোনো মোড়ে এলে, আপনার কাছে যেদিকটা লক্ষ্যের কাছাকাছি মনে হবে, আপনি সেদিকটাই বেছে নেবেন।

এই কম্পাসটিই হলো হিউরিস্টিক (heuristic) — একটি বুদ্ধিদীপ্ত অনুমান (educated guess) যা বলে দেয় আপনি লক্ষ্যের কতটা কাছাকাছি আছেন। এটি যে সবসময় সঠিক পথ দেখাবে তার শতভাগ নিশ্চয়তা দেয় না, তবে এটি খোঁজার প্রক্রিয়াটিকে জাদুর মতো দ্রুত করে দেয়।

হিউরিস্টিক আসলে কী?

হিউরিস্টিক হলো একটি ফাংশন h(n) যা কোনো নির্দিষ্ট নোড n থেকে গন্তব্য বা লক্ষ্যের সম্ভাব্য খরচের একটা হিসাব কষে দেয়। এটি একদম নিখুঁত কিছু নয় — বরং এটি কাছাকাছি একটা ধারণা দেয় (approximation)। উদাহরণস্বরূপ:

  • জিপিএস নেভিগেশন (GPS navigation): রাস্তাঘাট বাদ দিয়ে আপনার জায়গা থেকে গন্তব্যের একদম সোজা বা স্ট্রেইট লাইন দূরত্ব (straight-line distance)।
  • স্লাইডিং পাজল (Sliding puzzle): কয়টি টাইলস তাদের সঠিক জায়গা থেকে ভুল জায়গায় সরে আছে।
  • দাবা খেলা (Chess): আপনার দলের ঘুঁটিগুলোর মোট মান থেকে প্রতিপক্ষের ঘুঁটিগুলোর মোট মান বিয়োগ করা।

মূল ব্যাপারটা হলো: একটি ভালো হিউরিস্টিককে যে একদম নিখুঁত হতে হবে, এমন কোনো কথা নেই। এটি যদি আপনাকে মোটামুটি সঠিক একটি দিকও দেখাতে পারে, সেটুকুই যথেষ্ট। কারণ কম্পাস না থাকার চেয়ে অন্তত একটি সাধারণ মানের কম্পাস থাকাও অনেক ভালো।

গ্রিডি বেস্ট-ফার্স্ট সার্চ (Greedy Best-First Search)

সবচেয়ে সহজ হিউরিস্টিক সার্চটি হলো গ্রিডি বেস্ট-ফার্স্ট সার্চ (Greedy Best-First Search)। এটি প্রতিটি ধাপে হিউরিস্টিকের ওপর ভিত্তি করে যে নোডটিকে লক্ষ্যের সবচেয়ে কাছাকাছি মনে হয়, সেটাকেই বেছে নেয়। এটি খুব দ্রুত কাজ করে ঠিকই, কিন্তু একে খুব সহজেই বোকা বানানো যায় — অনেকটা কম্পাসের দিক ধরে সোজা হেঁটে গিয়ে দেয়ালের সাথে ধাক্কা খাওয়ার মতো ব্যাপার।

A* (এ-স্টার) সার্চ: দ্য গোল্ড স্ট্যান্ডার্ড

A* (এ-স্টার) হলো সবচেয়ে জনপ্রিয় হিউরিস্টিক সার্চ অ্যালগরিদম। এটি মূলত দুটি ভিন্ন ভিন্ন তথ্যের সমন্বয়ে কাজ করে:

  • g(n) — একদম শুরুর বিন্দু থেকে n নম্বর নোড পর্যন্ত আসার প্রকৃত খরচ বা একচুয়াল কস্ট (actual cost)।
  • h(n) — n নম্বর নোড থেকে গন্তব্য বা লক্ষ্যের সাম্ভাব্য খরচ (এটাই মূলত হিউরিস্টিক)।

A* সবসময় সেই নোডটিকেই বেছে নেয় যার f(n) = g(n) + h(n)-এর মান সবচেয়ে কম হয়। এটি মূলত "আমি কত দূর এসেছি (g)" এবং "আমার আর কত দূর যেতে হবে বলে আমার মনে হয় (h)" — এই দুটোর মধ্যে ভারসাম্য তৈরি করে।

A*-এর জাদুকরী দিকটি হলো: যদি আপনার হিউরিস্টিক কখনোই প্রকৃত খরচের চেয়ে বেশি অনুমান না করে (never overestimates) (যাকে আমরা অ্যাডমিসিবল বা admissible বলি), তবে A* আপনাকে গ্যারান্টি দিয়ে সবচেয়ে ছোট বা অপ্টিমাল পথটি খুঁজে দেবে। অর্থাৎ, আপনি এতে হিউরিস্টিকের গতি বা স্পিডও পাবেন, আবার সে সাথে বিএফএস (BFS)-এর মতো সেরা ফলাফলটিও পেয়ে যাবেন। আক্ষরিক অর্থেই—একের ভেতর দুই!

A* সার্চ ইমপ্লিমেন্ট করা

import heapq


def a_star(graph, start, goal, h):
    """একটি হিউরিস্টিক ফাংশন h-এর সাহায্যে A* সার্চ।"""
    # প্রায়োরিটি কিউ (Priority queue): (f_score, node, path, g_score)
    open_set = [(h(start), start, [start], 0)]
    visited = set()
    
    while open_set:
        f, node, path, g = heapq.heappop(open_set)
        
        if node == goal:
            print(f"{g} খরচে পথ পাওয়া গেছে")
            return path
        
        if node in visited:
            continue
        visited.add(node)
        
        for neighbor, cost in graph[node]:
            if neighbor not in visited:
                new_g = g + cost
                new_f = new_g + h(neighbor)
                heapq.heappush(open_set, (new_f, neighbor, path + [neighbor], new_g))
    
    return None


# গ্রাফ (Graph): node -> [(neighbor, cost), ...]
city_map = {
    'Home':    [('Cafe', 2), ('Park', 5)],
    'Cafe':    [('Library', 3), ('Park', 2)],
    'Park':    [('Library', 1), ('Office', 6)],
    'Library': [('Office', 2)],
    'Office':  []
}


# হিউরিস্টিক: 'Office' পর্যন্ত সরাসরি বা স্ট্রেইট-লাইন দূরত্ব অনুমান করা
estimate = {'Home': 7, 'Cafe': 5, 'Park': 4, 'Library': 2, 'Office': 0}


path = a_star(city_map, 'Home', 'Office', lambda n: estimate[n])
print("পথ:", path)
Output
7 খরচে পথ পাওয়া গেছে
পথ: ['Home', 'Cafe', 'Library', 'Office']
Note: অ্যাডমিসিবল (Admissible)-এর মানে হলো কখনোই ওভারএস্টিমেট না করা: একটি হিউরিস্টিককে তখন অ্যাডমিসিবল বা গ্রহণযোগ্য বলা হয়, যখন এটি প্রকৃত খরচের চেয়ে কখনোই বেশি অনুমান করে না। যেমন, রাস্তার নেভিগেশনের ক্ষেত্রে 'সোজা দূরত্ব' বা স্ট্রেইট-লাইন ডিসট্যান্স (straight-line distance) একটি অ্যাডমিসিবল হিউরিস্টিক কারণ আপনি কখনোই এর চেয়ে কম রাস্তা চালিয়ে যেতে পারবেন না। আপনার হিউরিস্টিক যদি ওভারএস্টিমেট করে, অর্থাৎ প্রকৃত খরচের চেয়ে বেশি দেখায়, তবে A* অ্যালগরিদমটি তার কাঙ্ক্ষিত সবচেয়ে ভালো পথটি (optimal path) খুঁজে না-ও পেতে পারে — তাই সঠিক হিউরিস্টিক বেছে নেওয়াটাও একটা শিল্পের মতো বিষয়।

বাস্তব জীবনে কোথায় A* ব্যবহৃত হয়

A* (এ-স্টার) বর্তমানে বিশ্বের সবচেয়ে বহুল ব্যবহৃত অ্যালগরিদমগুলোর মধ্যে একটি:

  • ভিডিও গেমস (Video games) — গেমের মধ্যে এনপিসি (NPC) বা অন্যান্য চরিত্রগুলো যখনই আপনার কাছে পৌঁছানোর জন্য দেয়াল বা বাধা এড়িয়ে পথ খুঁজে নেয়, তখন তারা মূলত A*-ই ব্যবহার করে।
  • জিপিএস অ্যাপস (GPS apps) — গুগল ম্যাপস (Google Maps) এবং ওয়েজ (Waze) সবচেয়ে দ্রুত পথ খুঁজে বের করতে A*-এর বিভিন্ন রূপ বা ভ্যারিয়েন্ট ব্যবহার করে।
  • রোবটিক্স (Robotics) — রোবটরা ঘরের আসবাপত্র, মানুষ এবং অন্যান্য বাধা এড়িয়ে নিজেদের চলাচলের পথ ঠিক করতে A* ব্যবহার করে।
  • পাজল সলভার (Puzzle solvers) — A* অ্যালগরিদম খুব দ্রুততার সাথে যেকোনো স্লাইডিং পাজল, গোলকধাঁধা এবং এমনকি রুবিকস কিউব (Rubik's Cubes)-এর সমাধান বের করতে পারে।

A*-এর সবচেয়ে সুন্দর দিকটি হলো এটি অত্যন্ত সহজ, অপ্টিমাল বা নির্ভুল এবং ফ্লেক্সিবল (flexible)। শুধু হিউরিস্টিক ফাংশনটি বদলে দিলেই একই অ্যালগরিদম দিয়ে সম্পূর্ণ ভিন্ন ভিন্ন সমস্যার সমাধান করা সম্ভব।

ছোট কুইজ

পরবর্তী কোন নোডটি খুঁজতে হবে তা ঠিক করতে A* (এ-স্টার) অ্যালগরিদম কোন কোন বিষয়গুলো ব্যবহার করে?

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

স্টেট স্পেস সার্চ (State Space Search)
লক্ষ্যে পৌঁছাতে সম্ভাব্য প্রতিটি চাল বা উপায় অন্বেষণ করা
→
মিনিম্যাক্স অ্যালগরিদম (Minimax Algorithm)
সামনের কথা ভাবুন — যদি আপনার প্রতিপক্ষ একদম নিখুঁত চালে খেলে, তবে আপনার সেরা চাল কোনটি হবে?
→
এআই (AI) কী?
রোবট ওয়েটার, দাবা খেলার ইঞ্জিন আর সিরি — কী এমন আছে এদের মধ্যে যা এদেরকে বুদ্ধিমান বানায়?
→