ডাইনামিক প্রোগ্রামিং ৯ (ট্রি, মিনিমাম ভারটেক্স কভার)

(সবগুলো পর্ব) ডাইনামিক প্রোগ্রামিং দিয়ে ট্রি(Tree) সংক্রান্ত অনেক সমস‍্যার সমাধান করা যায়। সাধারণ গ্রাফে পলিনোমিয়াল টাইমে সমাধান করা যায় না এমন অনেক প্রবলেম ট্রি গ্রাফে সহজেই ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায় কারণ ট্রি তে কোন সাইকেল থাকে না। এই পর্বে আমরা সেরকমই একটা ক্লাসিক প্রবলেম দেখবো যার নাম মিনিমাম ভারটেক্স কভার।

ধরা যাক একটি শহরে কিছু রাস্তা আছে, এখন প্রতি রাস্তায় মোড় বা জাংশনে আমরা পাহারাদার বসাতে চাই। কোনো মোড়ে পাহারাদার বসালে সে মোড়ের সাথে যুক্ত রাস্তাগুলো একাই পাহারা দিতে পারে। এখন তোমাকে বলতে হবে সব কয়টা রাস্তা পাহারা দিতে নূন্যতম কয়জন পাহারাদার দরকার?

একটা উদাহরণ দেখি। নিচের শহরে লাল নোডগুলোতে পাহারাদার বসানো হয়েছে:

বাম পাশের পদ্ধতিতে আমাদের ৩জন পাহারাদার লেগেছে কিন্তু ডানপাশে আমি দেখিয়েছি যে ২জন পাহারাদার দিয়েই কাজটা করা সম্ভব।

এই রাস্তা আর জাংশনগুলোকে আমরা গ্রাফ থিওরি ভাষায় এজ এবং ভারটেক্স বা নোড বলতে পারি। তাহলে প্রবলেমটা হলো সবথেকে কম ভারটেক্স বা নোডে পাহারাদার বসিয়ে এজগুলোকে পাহারা দেয়া।

সাধারণ গ্রাফের জন‍্য এটা কিন্তু একটা NP-Hard প্রবলেম, অর্থাৎ এটার কোন পলিনোমিয়াল সমাধান আমাদের জানা নেই। তবে গ্রাফটি একটা ট্রি (Tree) হলে আমরা সহজেই ডায়নামিক প্রোগ্রামিং দিয়ে প্রবলেমটা সলভ করতে পারবো। একটা গ্রাফ তখনই ট্রি হবে যখন সেটায় $n-1$ টা নোড থাকবে।

উপরের ছবিতে $8$ নোডের একটা ট্রি এর জন‍্য সমাধান দেখানো হয়েছে।

সাবপ্রবলেম বা স্টেট নির্ধারণ

এই প্রবলেমটা সলভ করার জন‍্য আমাদের ২টি অবজার্ভেশন করতে হবে:

কোনো নোডে পাহারাদার না বসালে তার সাথে সংযুক্ত সব নোডে অবশ্যই পাহারাদার বসাতে হবে, এ ছাড়া সব রাস্তা কভার হবে না। যেমন উপরের ছবিতে $1$ এ যদি পাহারাদার না বসাতাম তাহলে $0, 3, 4$ এ অবশ‍্যই পাহারাদার বসাতে হতো।
কোনো নোডে পাহারদার বসালে তার সাথে সংযুক্ত নোডগুলো পাহারাদার বসানো বাধ‍্যতামূলক না তবে বসালে মাঝেমধ‍্যে লাভ হতেও পারে। যেমন $1$ এ পাহারাদার বসানোর পর $4$ এ পাহারাদার না বসালেও কিন্তু সবগুলো রাস্তা কভার করা সম্ভব কিন্তু এক্ষেত্রে $4$ এ পাহারাদার বসালেই বেশি লাভ হচ্ছে।

আগের মতোই আমরা একটা ফাংশন ডিফাইন করার চেষ্টা করি। স্বাভাবিক ভাবে প্রথমেই হয়তো মাথায় আসবে $f(u)$ যেটা দিয়ে বুঝায় আমরা বর্তমানে কোন নোডে আছি। কিন্তু একটু চিন্তা করলে দেখবে আমাদের আরেকটা ইনফরমেশন দরকার, সেটা হলো বর্তমান নোডে পাহারাদার আছে নাকি নাই। আমরা যখন এক নোড থেকে অন‍্য নোডে যাবো তখন বর্তমান নোডে পাহারাদার আছে নাকি নেই সেই তথ‍্যটা কাজে লাগিয়ে সিদ্ধান্ত নিতে পারবো পরের নোডে পাহারাদার লাগবে নাকি লাগবে না।

তাহলে আমরা ধরতে পারি আমাদের ফাংশনটা হলো $f(u, guard)$ যেখানে $guard$ একটা বুলিয়ান ‍ভ‍্যালু যা দিয়ে বুঝাচ্ছে $u$ তে গার্ড আছে নাকি নেই।

আমরা যেকোন নোড থেকেই পাহারাদার বসানো শুরু করতে পারি, যদিও ছবি দেখে মনে হচ্ছে $0$ প্রথম নোড। আমরা আসলে বুঝতে সুবিধার জন‍্য কোনো একটা নোডকে Root হিসাবে কল্পনা করি, এক্ষেত্রে $0$ কে রুট ধরেছি। রুট ডিফাইন করলে আমরা ট্রি এর এজগুলোকে ডিরেক্টেড করে দিতে পারি।

এভাবে চিন্তা করলে সমাধান করা অনেকটা সহজ হয়ে যাবে। তুমি বর্তমানে যে নোডে আছে, সবসময় সেই নোডের নিচের নোডগুলো আর এজগুলোকে নিয়ে চিন্তা করবে, আর ধরে নিবে অন‍্যসব নোড এবং এজগুলোর জন‍্য ম‍্যাজিকালি সমাধান করা হয়ে গিয়েছে।

এখন যদি $1$ এ পাহারাদার না বসাই তাহলে আমাদেরকে $f(1, false)$ সম‍স‍্যাটার সমাধান করতে হবে। উপরে বামের ছবিতে সেটাই দেখানো হয়েছে। যেহেতু $1$ এ পাহারাদার নাই, নিচের রাস্তা দুটি গার্ড দেয়ার জন‍্য $1$ এবং $2$ তে পাহারা বসাতেই হবে এবং $f(3, true)$ আর $f(4, true)$ সাবপ্রবলেমদুটো সলভ করতে হবে:

$f(1, false) = f(3, true) + f(4, true)$

আবার যদি $1$ এ পাহারা বসাই তাহলে $3$ এবং $4$ এ পাহারাদার বসানো অপশনাল। আমরা একবার বসিয়ে এবং একবার না বসিয়ে সবপ্রবলেমগুলো সলভ করে দেখবো কোনটা অপটিমাল হয়:

$f(1, true) = 1 + min(f(3, true), f(3, false)) + min(f(4, true) + f(4, false))$

এবার অতিরিক্ত $1$ যোগ করেছি পাহারাদার বসানোর কারণে।

আমরা তাহলে এক সাবপ্রবলেম থেকে অন‍্য সাবপ্রবলেমে কিভাবে যেতে হবে সেটা বুঝে গিয়েছি। $0$ কে প্রথম নোড ধরলে আমাদেরকে $min(f(0, true), f(0, false))$ সমস‍্যাটির সমাধান. করতে হবে।

রিকার্সিভ ফর্মুলা

জেনারেলাইজ করে লিখতে পারি:

(true/false কে 0/1 লেখা হয়েছে) বেস কেস আলাদা ভাবে ডিফাইন করার দরকার নাই, সবথেকে নিচের লেভের নোডে গিয়ে রিকার্সন শেষ হয়ে যাবে।

সি++ কোড

কোডের আসল অংশটা হবে এরকম:

#define MAXN 100
#define EMPTY_VALUE -1

int mem[MAXN][2];
int par[MAXN];

vector<int> edges[MAXN];

int f(int u, int isGuard){    
    if (mem[u][isGuard] != EMPTY_VALUE) {
        return mem[u][isGuard];
    }
        
    int answer = isGuard;
    
    for(auto v: edges[u]) {
        if (v == par[u]) continue;
        par[v] = u;
        if (isGuard == 0) {
            answer += f(v, 1);
        } else {
            answer += min(f(v, 1), f(v, 0));
        }
    }
    
    return mem[u][isGuard] = answer;
}

#define MAXN 100

#define EMPTY_VALUE -1

int mem[MAXN][2];

int par[MAXN];

vector<int> edges[MAXN];

int f(int u, int isGuard){

if (mem[u][isGuard] != EMPTY_VALUE) {

return mem[u][isGuard];

}

int answer = isGuard;

for(auto v: edges[u]) {

if (v == par[u]) continue;

par[v] = u;

if (isGuard == 0) {

answer += f(v, 1);

} else {

answer += min(f(v, 1), f(v, 0));

}

return mem[u][isGuard] = answer;

}

সহজে টেস্ট করার জন‍্য স‍্যাম্পল ইনপুট সহ মেইন ফাংশনটাও দিয়ে দিলাম:

/**
Sample Input->
* 
8
0 1
0 2
1 3
1 4
5 2
4 6
4 7
**/
int main() {
    memset(mem, -1, sizeof(mem));
    memset(par, -1, sizeof(par));
    
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);

        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    int ans = 0;
    
    ans = min(f(0, true), f(0, false));
    cout<<ans<<endl;
    
    return 0;
}

/**

Sample Input->

0 1

0 2

1 3

1 4

5 2

4 6

4 7

**/

int main() {

memset(mem, -1, sizeof(mem));

memset(par, -1, sizeof(par));

int n;

scanf("%d", &n);

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

int u, v;

scanf("%d%d", &u, &v);

edges[u].push_back(v);

edges[v].push_back(u);

}

int ans = 0;

ans = min(f(0, true), f(0, false));

cout<<ans<<endl;

return 0;

}

একটা জিনিস খেয়াল করো, আমরা ট্রি এর এজগুলোকে বাইডিরেকশনাল হিসাবেই ইনপুট নিচ্ছি কারণ ইনপুট যেকোন অর্ডারে দেয়া থাকতে পারে। $0$ কে রুট কল্পনা করার পরেই কেবলমাত্র ডিরেকশন ফিক্সড হয়ে গিয়েছে। আমরা কোন নোডের প‍্যারেন্ট নোডকে সেটা একটা অ‍্যারেতে ট্র‍্যাক রাখছি কারণ উপরের নোড নিয়ে আমরা কোনো কাজ করবো না।

কমপ্লেক্সিটি

আমাদের সাবপ্রবলেম আছে $n * 2$ টা কারণ আমাদের নোড $n$ টা এবং প্রতি নোডে আমাদের দুটি করে অপশন আছে। প্রতি সাবপ্রবলেমে আবার এজগুলোর উপর একটা লুপ চালাচ্ছি। মোট কমপ্লেক্সিটি হবে $O(n^2)$।

ইটারেটিভ ভার্সন

আমরা জানি ইটারেটিভ ভার্সনে ডিপির টেবিল বিল্ডআপ করলে ছোট সাবপ্রবলেমগুলো আগে সলভ করে আসতে হয়। এই প্রবলেমে ছোট সাবপ্রবলেমগুলো আছে ট্রি এর leaf নোডগুলোতে, অর্থাৎ সবথেকে নিচের নোডগুলোতে। প্রতিটা নোডের রেজাল্ট জানার জন‍্য আমাদেরকে Subtree গুলোর রেজাল্ট জানতে হবে। সেক্ষেত্রে আমাদেরকে আগে PostOrder Traversal করে নোডগুলোকে সাজিয়ে নিতে হবে। আমাদের উদাহরণের জন‍্য সিকুয়েন্সটা হবে ${3, 6, 7, 4, 1, 5, 2, 0}$, খেয়াল করো এই অর্ডারে ডিপি টেবিল বিল্ডআপ করলে সবসময় তুমি সাবপ্রবলেম গুলো রেজাল্ট টেবিলে পাবে। এখন PostOrder Traversal রিকার্সিভলি বা ইটারেটিভলি বের করা যায় তবে ইটারেটিভলি বের করা একটু ঝামেলার। তুমি চাইলে চেষ্টা করে দেখতে পারো।

নন-ডাইনামিক প্রোগ্রামিং সলিউশন

ডাইনামিক প্রোগ্রামিং ছাড়াও এই সমস‍্যা সমাধান করা যায় কিছুটা অ‍্যাডভান্সড গ্রাফ অ‍্যালগরিদম ‘ম‍্যাক্স ফ্লো’ বা বাইপারটাইট ম‍্যাচিং ব‍্যবহার করে। ম‍্যাক্স-ফ্লো নিয়ে জানতে চাইলে আমার এই লেখাটা পড়তে পারো।

প্র‍্যাকটিস প্রবলেম

https://leetcode.com/problems/binary-tree-cameras/
https://www.spoj.pl/problems/PT07X/
https://onlinejudge.org/external/102/p10243.pdf

আজ এই পর্যন্তই, হ‍্যাপি কোডিং।

ফেসবুকে মন্তব্য

comments

শাফায়েতের ব্লগ