প্রিম’স অ্যালগোরিদম : মিনিমাম স্প্যানিং ট্রি

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

 

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

 

Capture

 

অ্যালগোরিদমের আইডিয়াটা খুবই সহজ! 😀 এটি গ্রিডী এপ্রোচে কাজ করে। প্রথমে যেকোন একটি Random নোডকে সোর্স ধরে আমরা সোর্সের এডজেসেন্ট সবগুলো নোডের মধ্যে (অর্থাৎ সোর্স নোড থেকে আর যে যে নোডে যাওয়া যায়) যে নোডের কস্ট/ওয়েট সবচেয়ে কম, সেই নোডে যাব। প্রত্যেকবার আমরা যে যে নোডে যাব, তার এডজেসেন্ট সবগুলো নোডকেই আমরা পরের মিনিমাম কস্ট এজ নেয়ার ক্ষেত্রে বিবেচনা করব!

 

একটা ভিজ্যুয়াল GIF দেখলে ব্যাপারটা আরও সহজ হবে…

 

 

 output_ZVQYO4

 

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

 

মনে আছে তো, স্প্যানিং ট্রিতে কিন্তু কোন সাইকেল থাকবে না! তুমি নিশ্চয়ই একই বাড়িতে ২ টা লাইন বসাতে চাও না, তাহলে তোমার কোম্পানীর বিশাল লস হয়ে যাবে। সুতরাং যখনই আমরা কোন একটি নোড নেব, তখন দেখতে হবে সেই নোডটা আগে নেয়া হয়েছে কিনা! নেয়া হয়ে থাকলে সেই নোড আর নেয়া যাবে না। সেজন্যেই যখন আমরা ২ এর কাছের নোডগুলোর মধ্যে মিনিমাম কস্ট ১৩ থাকা সত্ত্বেও ১ নাম্বার নোডে আবার যেতে পারছি না, কারণ নোডটি আগেই নেয়া হয়েছে এবং আবার নিলে সেটা একটা সাইকেল তৈরি করবে! শেষে কমলা রঙ দিয়ে চিহ্নিত ট্রিই আমাদের কাঙ্ক্ষিত মিনিমাম স্প্যানিং ট্রি।

 

আমাদের মোটমাট খরচ পড়ল তাহলে,
৯+৮+১২+১৪+৮+১১+৯+১১ = ৮২

 

অন্য কোন স্প্যানিং ট্রি নিয়েও চেক করে দেখতে পারো, ৮২ এর কম কস্টে কখনোই লাইন বসাতে পারবে না।

 

আইডিয়া বুঝতে পারলে কোড তো লিখে ফেলা ব্যাপারই না! শুধু আরেকটা জিনিস বলে রাখি, প্রতিবার মিনিমাম কস্ট নেয়ার জন্যে আমরা এজ এবং কস্টগুলোকে stl এর priority_queue তে রাখতে পারি। কোড দেখার আগে নিজে নিজে একবার কোডটা লিখে ফেলার চেষ্টা করে দেখো (এখানে আমি শুধু প্রিম’স অ্যালগোরিদমের ফাংশনটা লিখেছি, মেইন ফাংশনে গ্রাফ ইনপুট নেয়া হয়েছে)

 


#define pii pair<int,int> 
#define vpi vector<pii>
#define ff first
#define ss second

vpi V[3005];                             //graph is stored here as adjacency list
int vis[3005]={0};

int prim()
{
    priority_queue<pii> p;               //stored as <cost,node> pair
    int cost = 0;
    p.push(mp(0,0));                     //source is 0, and cost of source to source is 0
    while(!p.empty())
    {
        pii tem = p.top();
        p.pop();
        int v = tem.ss;
        if(!vis[v])
        {
            vis[v] = 1;
            cost += -tem.ff;
            For(i,V[v].sz)
                if(!vis[V[v][i].ff])
                    p.push(mp(-(V[v][i].ss),V[v][i].ff));
        }
    }
    return cost;
}

 

খেয়াল করে দেখো, প্রায়োরিটি কিউতে কস্ট পুশ করার সময় কস্টকে নেগেটিভ করে পুশ করা হয়েছে। প্রায়োরিটি কিউ সম্পর্কে জানলেই বুঝতে পারবে কেন, তাই এটার উত্তর বের করাটা তোমাদের হাতেই ছেড়ে দিলাম।

 

কমপ্লেক্সিটিঃ প্রায়োরিটি কিউতে পুশ করতে লগারিদম টাইম লাগে। এখানে প্রতিটা নোড একবার করে পুশ হবে, যেহেতু আমরা কোন নোড পুশ করার আগে দেখে নিচ্ছি সেটা আগেই ভিজিট করা হয়েছে কিনা। সুতরাং, এজ সংখ্যা |E| ও নোড সংখ্যা |V| হলে প্রিমসের টাইম কমপ্লেক্সিটি O((|V| + |E|) log |V|) = O(|E| log |V|)

 

কনসেপ্ট ক্লিয়ার হয়ে গেলে নিচের প্রব্লেমগুলো সলভ করে ফেলোঃ

 

https://www.hackerrank.com/challenges/primsmstsub
http://www.spoj.pl/problems/MST/
http://uva.onlinejudge.org/external/5/544.html

http://uva.onlinejudge.org/external/9/908.html
http://uva.onlinejudge.org/external/100/10034.html
http://uva.onlinejudge.org/external/112/11228.html
http://uva.onlinejudge.org/external/104/10462.html
Advertisements

2 thoughts on “প্রিম’স অ্যালগোরিদম : মিনিমাম স্প্যানিং ট্রি

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s