আনইনফর্মড সার্চ এবং আর্টিফিসিয়াল ইন্টেলিজেন্স বাকিটা ইতিহাস

আর্টিফিসিয়াল ইন্টেলিজেন্স বা এআই এর একটি গুরুত্বপূর্ন বিষয় আনইনফর্মড সার্চ। তো প্রথমে শুরু করি এই জিনিষটা কি তা দিয়ে। গুগল মামাকে জিজ্ঞেস করে জানা গেল-

An uninformed (a.k.a. blind, brute-force) search algorithm generates the search tree without using any domain specific knowledge.

কিছু বুঝা গেলনা? আমিও বুঝিনি। তাই সহজ বাংলা ভাষায় বলা যায়-

যেসব সার্চ স্ট্রাটেজি তাদের গোল/ডেস্টিনেশন কোথায় আছে তা নিয়ে মাথা ঘামায় না এবং তারা কোথায় যাচ্ছে তা নিয়েও মাথা ঘামায় না যতক্ষন না তারা তাদের গোল/ডেস্টিনেশনে না পৌছায়।

অর্থাৎ তাদের পথ নিয়ে কোন মাথাব্যাথা নেই। পৌছুতে পারলেই হল।

যেহেতু এই টাইপের সার্চিং স্ট্রাটেজিগুলো তাদের পথ নিয়ে মাথা ঘামায় না, সেহেতু আমরা আশা করতে পারিনা এগুলো সবসময় আমাদের সহজ অথবা ছোট পথে ডেস্টিনেশনে নিয়ে যাবে। এটা এই সার্চের একটা লিমিটেশন।

এরকম কিছু অন্ধ্য খোঁজ অথবা আনইনফর্মড সার্চ অ্যালগরিদম হলো-

·        Breadth First Search

·        Depth First Search

·        Depth Limited Search

·        Iterative Deepening Search

অনেক বোরিং থিওরি আলোচনা হল। আমার এই লেখার মুল উদ্দেশ্য আনইনফর্মড সার্চ এর থিওরি কপচানো না। উপরের চারটা অ্যালগরিদম কিভাবে C++ দিয়ে ইম্পিমেন্ট করা যায় তা দেখা। ডাটা স্ট্রাকচার অথবা অ্যালগরিদমে আমরা যে বিএফএস, ডিএফএস পড়েছি এখানে সেটার মতই, শুধু একটু মডিফাই করতে হবে। মুলত বিএফএস, ডিএফএস গ্রাফ ট্রাভার্সাল টেকনিক। কিন্তু এখানে সেই টেকনিককে আমরা পাথ ফাইন্ডিং এ কাজে লাগাবো। পরবর্তি দুটি অ্যালগরিদম ডিএফএস এর ই মডিফায়েড ভার্সন। আমরা সবগুলো ইম্পলিমেন্টেশন রিকার্সিভ প্রসিডিওর ফলো করে করবো। রিকার্সিভ ফাংশন হলো যে বার বার নিজেকে কল করে। নিজের ঢোল নিজে পেটায়।

শুরুর আগে আমরা নিম্মোক্ত বিষয়গুলো পড়ে আসলে ভালো হয়:

• Recursion
• BFS  
• DFS 
• Adjacency Matrix
• C++ Vector
• C++ Queue
• Ascii Table 

না পড়লেও সমস্যা নেই। পড়াশোনা করে কেউ কখনো বড়লোক হয়না।

তো প্রথমে আমরা Breadth First Search নিয়ে আলোচনা করি।

Breadth  অর্থ প্রসার/প্রস্থ। অ্যালগরিদম তোমার কাম কি? নামেই পরিচয়। এই অ্যালগরিদম সবসময় প্রস্থ বরাবর সার্চ করে যায়। যেটাকে আমরা লেভেল বলি। একটি গ্রাফের লেভেল বুঝতে শুধুমাত্র এক ছবিই যথেষ্ট।

যদি আমরা উপরের পড়াশোনা করে আসি তাহলে আমরা জানি প্রত্যেকবার আমরা একটা নোডে এন্টার করবো এবং সেটা থেকে কোন কোন নোডে যাওয়া যায় সেগুলোতে সিরিয়ালি ভিজিট করবো। যেহেতু সিরিয়ালের ব্যাপার চলে আসছে সেহেতু আমাদের কিউ লাগবে। প্রথমে আমরা সোর্স নোডকে কিউতে রাখবো।

q.push(strt);

তারপর যেহেতু আমরা সোর্সনোড ভিজিট করবো সেহেতু সোর্সনোড যে ভিজিট করছি তার ট্রেস রাখবো।

vis[node]=1;

যেহেতু আমরা এই নোড ভিজিট করছি সেহেতু এটাকে আমরা path নামক ভেক্টর এ পুশ করবো।

path.push_back(node);

যদি কিউ খালি হয় তাহলে আমরা রিটার্ন করবো কারন তখন কোথাও কেউ নাই।

if(q.empty()) return;

তারপর আমরা কিউতে প্রথমে যে এলিমেন্ট আছে তাকে নিব

int x=q.front();

এবং সেটাকে কিউ থেকে বাদ দিব।

q.pop();

এবার কারেন্ট নোড থেকে যেসব নোডে যাওয়া যায় এবং তার মধ্যে যেসব নোড এখনো ভিজিটেড না সেগুলোকে কিউতে রাখবো।

for(int i=1;i<=n;i++)

    {

        if(graph[x][i] && !vis[i])

        {

            q.push(i);

        }

    }

এবং কিউ থেকে পরবর্তী নোডকে আবার ফাংশনে পাঠাবো (রিকার্সিভ ওয়ে)।

কিন্তু এভাবে তো আমাদের গোল নোডে পৌছানোর পরও ফাংশন স্টপ হবেনা। কারন এরপরও অনেক নোড কিউতে থাকতে পারে। তাহলে?

সিম্পল, আমরা একটা ভেরিয়েবল রাখবো যেটা আইডেন্টিফাই করবে গোল পাওয়া গেছে কি না। পাওয়া গেলে রিটার্ন, না পাওয়া গেলে কন্টিনিউ, কারেন্ট নোড গোল নোড হলে ভেরিয়েবলের ভ্যেলু চেঞ্জ।

if(get_goal) return;

    if(node==goal)

    {

        path.push_back(node);

        get_goal=true;

        return;

    }

এই কাজগুলোকেই গুছিয়ে করা হয়েছে এখানে।

  

এবার আমরা Depth First Search নিয়ে আলোচনা করি।

শ্রদ্ধেয় শাফায়েত ভাইয়ের আর্টিকেল থেকে আমরা জানতে পেরেছি এই অ্যালগরিদম লেভেল বাই লেভেল সার্চ না করে একটা নোড থেকে তার নিচের নোড, তার থেকে তার নিচের নোড এভাবে চলে যায়। অনেক নিচু মনের অ্যালগরিদম। তো এখানে আমরা আগের মতই ভিজিট করবো, path এ পুশ করবো, গোল চেক করবো। যেটা করবো না সেটা হলে কিউ ব্যাবহার করবো না। কোন নোডের চাইল্ড নোড আনভিজিটেড পেলেই সেটাকে আমরা ফাংশনে পাঠাবো।

for(int i=1;i<=n;i++)

    {

        if(graph[node][i] && !vis[i])

        {

            dfs(i);

        }

    }

কাজগুলো গুছিয়ে করা হয়েছে এখানে-

এখন এখানে একটা বিশাল সমস্যা হতে পারে। কত বিশাল? একেবারে ডোনাল্ড ট্রাম্পের আমেরিকার মত বিশাল। যদি কখনো একটি নোডের চাইল্ড সংখ্যা অসীম হয়, তাহলে ফাংশন শুধু সেদিকে যেতেই থাকবে। অন্যদিকে যে কেউ তার জন্য অপেক্ষা করছে সেটা সে ভুলে যাবে। খারাপ কথা। তো এই সমস্যা সমাধানের জন্য ডিএফএস কে মডিফাই করে ডেভেলপ করা হলো ডিএলএস। এখানে অ্যালগরিদমের পায়ে আমরা বেড়ী দিয়ে দিব কয়েদিদের মত। তাকে বলে দেয়া হবে কত লেভেল ডেপথ পর্যন্ত সে যেতে পারে। তো সেজন্য আমরা একটা ভেরিয়েবল ইউজ করবো যেটাকে নাম দিলাম- dls_level.

প্রত্যেক নোডের চাইল্ড নোডে এন্টার করার আগে দেখবে লেভেল কি বেশী হবে কি না। যদি হয় তাহলে যাবেনা।

for(int i=1;i<=n;i++)
{
   if(graph[node][i] && !vis[i])
   {
     if(dls_level < lim)
        dls(i,lim);
   }
}

আর বাকি সব কাজ আগের মতই।

এখানেও একটা সমস্যা আছে। আমরা তাকে বললাম 2 লেভেল পর্যন্ত সার্চ করতে। কিন্তু আমাদের গোল আছে 5 লেভেলে। তখন? তখন সে গোল না পেয়েই রিটার্ন করবে। এ সমস্যা সমাধান করা হয়েছে Iterative Deepening Search এ। সহজভাবে বললে এটা ডিএলএস এর লিমিট আমরা একটা লুপের মাধ্যমে বাড়িয়ে বার বার চেক করবো গোল পাওয়া যায় কি না।

ইনপুট আউটপুট সহ পুরো প্রোগ্রাম:

যেকোন ধরনের অনিচ্ছকৃত ভূল মার্জনিয়। শুদ্ধ করে নেব।

অনেক ধন্যবাদ অমিত কুমার নাথ স্যারকে এরকম বোরিং সাবজেক্ট উৎসাহ দিয়ে পড়ানোর জন্য।

Resources:

http://cs.lmu.edu/~ray/notes/usearch/

www.google.com

Artificial Inteligence A Modern Approach by Stuart Russel & Peter Norvig

Md. Rasedur Rahman Roxy

BSc in CSE

Bangldesh University of Business & Technology