Table of Contents

    Class - XII: SEMESTER – IV: Unit – 3: Foundation of Artificial Intelligence (AI): Section 3: Search as Optimization (only Basic Concepts) (COMS Only)

    Rumman Ansari May 26, 2026 8 views Subject Details

    Search as Optimization

    ১. Introduction

    Artificial Intelligence-এ অনেক problem solve করা হয় "search problem" হিসেবে। Search as Optimization বলতে বোঝায় এমন একটি process যেখানে possible solution-গুলোর মধ্যে best solution খুঁজে বের করা হয়। [1](https://painlessprogramming.com/search-algorithms-in-ai/)

    Search Problem = Initial State → Goal State-এ যাওয়ার সঠিক path খুঁজে বের করা।
    উদাহরণ:
    GPS navigation → shortest path খুঁজে বের করা
    Puzzle solving → correct configuration খুঁজে পাওয়া

    ২. State Space Search

    State Space Search হলো AI search-এর মৌলিক ধারণা। এখানে problem-কে states (অবস্থা) এবং actions (কাজ)-এর মাধ্যমে প্রকাশ করা হয়।

    • State: Problem-এর একটি অবস্থা
    • Initial State: শুরু অবস্থা
    • Goal State: যে অবস্থা আমরা পেতে চাই
    • Action: এক state থেকে অন্য state-এ যাওয়া
    State Space = সব possible states-এর collection

    ৩. Strategies for State Space Search

    Search strategy নির্ধারণ করে কোন node আগে explore করা হবে।

    • Search tree বা graph ব্যবহার করা হয়
    • Different strategies efficiency বাড়ায়
    • Search হতে পারে blind বা informed

    ৪. Data Driven and Goal Driven Search

    Data Driven Search

    এটি forward search নামেও পরিচিত। Initial state থেকে শুরু করে step-by-step goal পর্যন্ত যাওয়া হয়।

    Start → Intermediate Steps → Goal

    Goal Driven Search

    এটি backward search নামেও পরিচিত। Goal থেকে শুরু করে পিছনের দিকে solve করা হয়।

    Goal → Previous Step → Initial State

    ৫. Heuristic Search

    Heuristic search হলো intelligent search method যেখানে problem solve করার জন্য additional knowledge ব্যবহার করা হয়। [2](https://www.geeksforgeeks.org/machine-learning/search-algorithms-in-ai/)

    Heuristic = “best guess” বা estimation function
    • Faster solution দেয়
    • Optimal path খুঁজতে সাহায্য করে
    • Complex problem solve করতে useful

    ৬. Breadth First Search (BFS)

    BFS level by level search করে। এটি একে একে সব nearest nodes explore করে। [2](https://www.geeksforgeeks.org/machine-learning/search-algorithms-in-ai/)

    • Queue ব্যবহার করে
    • Shortest path guarantee করে
    • Memory বেশি লাগে
    Tree traversal: level 1 → level 2 → level 3

    ৭. Depth First Search (DFS)

    DFS এক দিকে যতদূর সম্ভব যায়, তারপর backtrack করে। [2](https://www.geeksforgeeks.org/machine-learning/search-algorithms-in-ai/)

    • Stack ব্যবহার করে
    • Memory কম লাগে
    • Shortest path guarantee নয়
    Path follow করে deepest node পর্যন্ত

    ৮. BFS এবং DFS-এর পার্থক্য

    BFS DFS
    Level-wise search Depth-wise search
    Queue ব্যবহার Stack ব্যবহার
    Shortest path পায় Shortest path guarantee নয়
    Memory বেশি লাগে Memory কম লাগে

    ৯. A* Search Algorithm

    A* Search একটি advanced heuristic search algorithm। এটি best path খুঁজে বের করার জন্য actual cost এবং estimated cost combine করে।

    f(n) = g(n) + h(n)
    • g(n) = actual cost
    • h(n) = heuristic cost

    A* search efficient এবং optimal solution দেয় যদি heuristic function সঠিক হয়।

    GPS navigation system shortest path বের করতে A* ব্যবহার করে

    ১০. Heuristic vs Uninformed Search

    Uninformed Search Heuristic Search
    Extra knowledge ব্যবহার করে না Knowledge ব্যবহার করে
    Slow হতে পারে Faster
    BFS, DFS A*, Greedy

    ১১. Chapter Summary

    Search as Optimization AI-এর একটি গুরুত্বপূর্ণ concept। এখানে problem solve করতে state space explore করা হয় এবং best solution খুঁজে বের করা হয়।

    • State space search fundamental concept
    • Data-driven forward search
    • Goal-driven backward search
    • BFS shortest path দেয়
    • DFS memory efficient
    • Heuristic search speed বাড়ায়
    • A* best optimized search technique

    ১২. Short Questions

    • Search problem কী?
    • State space কী?
    • BFS কী?
    • DFS কী?
    • Heuristic search কী?
    • A* algorithm কী?