মিনিমাম ভারটেক্স কভার প্রবলেম

অক্টোবর ৪, ২০১২May 3, 2020 by Shafaet Ashraf

(নোটিশ: ডাইনামিক প্রোগ্রামিং এর একটি নতুন সিরিজ আমি শুরু করেছি, এই লেখাটির নতুন ভার্সন পাওয়া যাবে এখানে)

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

এটি একটি NP-hard প্রবলেম,অর্থাৎ এই প্রবলেমের কোনো পলিনমিয়াল টাইম সলিউশন নেই। তবে গ্রাফটি যদি Tree হয় অর্থাত n-1 টা edge থাকে আর কোনো সাইকেল না থাকে তাহলে ডাইনামিক প্রোগ্রামিং বা ম্যাক্স ফ্লো/বাইপারটাইট ম্যাচিং এর সাহায্যে প্রবলেমটি সলভ করা সম্ভব।

(নোটিশ: ডাইনামিক প্রোগ্রামিং এর একটি নতুন সিরিজ আমি শুরু করেছি, এই লেখাটির নতুন ভার্সন পাওয়া যাবে এখানে)

ডাইনামিক প্রোগ্রামিং সলিউশনটা আমি বিস্তারিত লিখছি,তারপর ম্যাক্স ফ্লো/বাইপারটাইট ম্যাচিং দিয়ে কিভাবে করতে হয় লিখবো।

ডিপি সলিউশনে ২টি কেস আমাদের লক্ষ্য করতে হবে:

১. কোনো নোডে পাহারাদার না বসালে তার সাথে সংযুক্ত সব নোডে অবশ্যই পাহারাদার বসাতে হবে,এছাড়া সব রাস্তা কভার হবে না। অর্থাৎ যদি u আর v সংযুক্ত থাকে তাহলে u তে পাহারাদার না বসালে v তে অবশ্যই বসাতে হবে।
২. কোনো নোডে পাহারাদার বসালে সংযুক্ত নোডগুলোতে পাহাদার বাসানো বাধ্যতামূলক না তবে বসালে লাভ হতে পারে। তাই u তে পাহারাদার বসালে v তে পাহারাদার একবার বসিয়ে এবং একবার না বসিয়ে দেখবো কোনটা লাভজনক

সব ডিপির প্রবলেমের মতো এখানেও একটা রিকার্সিভ ফাংশন ডিফাইন করবো। আমাদের স্টেট হবে বর্তমানে কোন নোডে আছি,এবং সেই নোডে কোনো পাহারাদার বসানো হয়েছে নাকি।

F(u,1) = বর্তমানে u নম্বর নোডে আছি এবং এই নোডে পাহারাদার আছে। f(u,1) রিটার্ণ করবে বাকি নোডগুলোতে মোট পাহারাদার সংখ্যা।
F(u,0) = বর্তমানে u নম্বর নোডে আছি এবং এই নোডে পাহারাদার নাই। f(u,0) রিটার্ণ করবে বাকি নোডগুলোতে মোট পাহারাদার সংখ্যা।

ধরি ১ নম্বর নোডের সাথে ২,৩,৪ নম্বর নোড যুক্ত।

বুঝাই যাচ্ছে ১ নম্বর নোডে পাহারা না বসালে অবশ্যই ২,৩,৪ সবগুলোয় পাহারা বসাতে হবে। তাহলে আমরা বলতে পারি:

F(1,0)=F(2,1)+F(3,1)+F(4,1) + 0 ,অর্থাত ১ এর সাথে সংযুক্ত সব নোডগুলোতে পাহারা বসালে প্রয়োজনীয় মোট পাহারাদার সংখ্যা।

সবশেষে ০ যোগ করছি কারণ বর্তমান নোডে পাহারাদার বসাইনি।

এবার F(1,1) এর মান বের করি। ১ নম্বর নোডে পাহারা বসালে সংযুক্ত নোডগুলোতে পাহারা বসালেও চলে,না বসালেও চলে,তবে যেটা অপটিমাল রেজাল্ট দেয় সেটা আমরা নিব:

F(1,1)=1+min ( F(2,1),F(2,0) ) +min ( F(3,1),F(3,0) ) +min ( F(4,1),F(4,0) )

১ নম্বর নোডে পাহারাদার বসাচ্ছি তাই সবশেষে ১ যোগ হচ্ছে,প্রতি নোডে একবার পাহারা বসিয়ে,আবার না বসিয়ে দেখছি কোনটা অপটিমাল।

একটা ব্যাপার লক্ষ রাখতে হবে যে প্যারেন্ট নোড নিয়ে কখনো হিসাব করবোনা। উপরের ছবিতে ১ থেকে ২ এ গেলে parent[2]=1,তাই ২ থেকে আবার ১ নম্বর নোডে যাবোনা।

এবার base case এ আসি। কোনো নোড থেকে নতুন কোনো নোডে যাওয়া না গেলে 1 বা 0 রিটার্ন করে দিতে হবে,পাহারাদার বসালে 1,না বসালে 0। কোনো ট্রি তে একটি মাত্র নোড থাকলে ১ রিটার্ণ করতে হবে(কিছু প্রবলেমে ০ ও রিটার্ণ করতে হতে পারে)।

Spoj এর PT07X(vertex cover) প্রবলেমটি straight forward প্রবলেম। এটার জন্য আমার কোডটা এরকম:

#define MAXN 100002
int dp[MAXN][5];
int par[MAXN];
vectoredges[MAXN];

int f(int u, int isGuard)
{
    if (edges[u].size() == 0)
        return 0;
    if (dp[u][isGuard] != -1)
        return dp[u][isGuard];
    int sum = 0;
    for (int i = 0; i < (int)edges[u].size(); i++) {
        int v = edges[u][i];
        if (v != par[u]) {
            par[v] = u;
            if (isGuard == 0)
                sum += f(v, 1);
            else
                sum += min(f(v, 1), f(v, 0));
        }
    }
    return dp[u][isGuard] = sum + isGuard;
}

int main()
{
    memset(dp, -1, sizeof(dp));
    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(1, 1), f(1, 0));
    printf("%d\n";, ans);
    return 0;
}

#define MAXN 100002

int dp[MAXN][5];

int par[MAXN];

vectoredges[MAXN];

int f(int u, int isGuard)

{

if (edges[u].size() == 0)

return 0;

if (dp[u][isGuard] != -1)

return dp[u][isGuard];

int sum = 0;

for (int i = 0; i < (int)edges[u].size(); i++) {

int v = edges[u][i];

if (v != par[u]) {

par[v] = u;

if (isGuard == 0)

sum += f(v, 1);

else

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

}

return dp[u][isGuard] = sum + isGuard;

}

int main()

{

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

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(1, 1), f(1, 0));

printf("%d\n";, ans);

return 0;

}

আমি ট্রি এর root সবসময় ১ ধরে কোড লিখেছি। ৩৮ নম্বর লাইনে মেইন ফাংশনে root এ পাহারাদার একবার বসিয়ে আর একবার না বসিয়ে অপটিমাল রেজাল্ট টা নিচ্ছি।
ফাংশনে u হলো current node,isguard কারেন্ট নোডে পাহারাদার আছে নাকি নাই সেটা নির্দেশ করে।
১০ নম্বর লাইনে ট্রি এর সাইজ ১ হলে ১ রিটার্ণ করে দিয়েছি।
১৩ নম্বর লাইনে লুপের ভিতর current নোড থেকে সবগুলো child নোডে যাচ্ছি। কারেন্ট নোডে পাহারাদার না থাকলে পরেরটায় বসাচ্ছি,আর থাকলে ২ভাবেই চেষ্টা করছি। ১৫ নম্বর লাইনের কন্ডিশন দিয়ে প্যারেন্ট নোডে যেতে দিচ্ছিনা।
সবশেষে sum+isGuard রিটার্ণ করছি। অর্থাত কারেন্ট নোডে পাহারাদার থাকলে 1 যোগ করছি,নাহল 0।

মোটামুটি এই হলো ডিপি সলিউশন। ট্রি তে সাইকেল না থাকায় এটা অবশ্যই বাইপারটাইট গ্রাফ। ১৯৩১ সালে Dénes Kőnig প্রমাণ করেন কোনো বাইপারটাইট গ্রাফে maximum matching=minimum vertext cover। এটা গ্রাফ থিওরির অনেক min-max থিওরেমের একটা যেখানে কিছু একটা ম্যাক্সিমাইজ করলে অন্য আরেকটা কিছু মিনিমাইজ হয়। তুমি যদি ম্যাক্সিমাম ম্যাচিং এর অ্যালগোরিদম জানো তাহলে ট্রি টা বাইকালারিং করে ম্যাচিং বের করলেই ভারটেক্স কভার বের হয়ে যাবে। কোড সহজ হলেও complexity বেড়ে যাবে,তাই নোড বেশি থাকলে কাজ করবেনা। আবার ম্যাক্সিমাম ম্যাচিং যেহেতু ম্যাক্স-ফ্লো এর একটি ভ্যারিয়েশন তাই ফ্লো চালিয়েও সমাধান করা সম্ভব।

এরকম আরেকটা প্রবলেম uva-10243(fire fire fire)। আমি প্রথমে এটা সমাধান করে পরে spoj এর টা করেছি।

(নোটিশ: ডাইনামিক প্রোগ্রামিং এর একটি নতুন সিরিজ আমি শুরু করেছি, এই লেখাটির নতুন ভার্সন পাওয়া যাবে এখানে)

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

comments

22 thoughts on “মিনিমাম ভারটেক্স কভার প্রবলেম”

Pingback: প্রোগ্রামার শাফায়েতের যত গ্রাফ থিওরীর টিউটোরিয়াল | ACMSolver - Bangla
মুকিত says:

অক্টোবর ৫, ২০১২ at ১১:২০ am

আচ্ছা, state এর ভ্যালু যখন -১,তখন dp[u][-1] হয় না ??? এটা কিভাবে সম্ভব !!! নাকি -১ এর পরিবর্তে ২ দিয়ে কাজ করব? এখানেতো জাস্ট ২ টা ভিন্ন মান নিয়ে কাজ করলেই হবে, তাই না? একটা ঐ node এ পাহারাদার বসাচ্ছি বুঝানোর জন্য, আরেকটি পাহারাদার বসাইনি,বুঝানোর জন্য,তাই না?

Reply
1. শাফায়েত says:
  
  অক্টোবর ৫, ২০১২ at ১১:২৩ am
  
  ঠিক। অথবা if(dp[u][state]!=-1) return dp[u][state]; এর জায়গায় if(dp[u][state+1]!=-1) return dp[u][state+1]; লিখলেও এটা handle করা যাবে।
  
  Reply
মুকিত says:

অক্টোবর ৫, ২০১২ at ১১:৪৯ am

vis[] array দিয়েই তো back[] array এর কাজ possible,তাই না ??? back[] এর প্রয়োজন আছে ? আর base case টা বুঝিনি? undirected graph এ কখনো কি edge[u].size()=0 হয় ? কমপক্ষে একটাতো সবসময় থাকে,তাইনা ???

Reply
1. শাফায়েত says:
  
  অক্টোবর ৫, ২০১২ at ১১:৫৬ am
  
  হ্যা vis অ্যারে দিয়েও সম্ভবত চেক করা যাবে। edge[u].size() সাইজ হবে যদি ১ সাইজের সাবগ্রাফ হয়,মানে একটা নোড যারা সাথে অন্য কোনো নোডের কানেকশন নাই। বেস কেসের ব্যাপারটা কোডে কমেন্টে লিখসি,ওটা দেখেইতো বুঝার কথা…….। এটা সম্ভবত আমার ব্লগের সবথেকে বাজে আর্টিকেল,অনেক আগে লেখা,আরো যত্ন করে লেখা দরকার ছিল।
  
  Reply
মুকিত says:

অক্টোবর ৫, ২০১২ at ১২:৩২ pm

আরে নাহ !!! তুমি লিখস ঠিক মতই… আমারই বুঝতে প্রবলেম হচ্ছে !!!

Reply
1. শাফায়েত says:
  
  অক্টোবর ৫, ২০১২ at ১:০২ pm
  
  এই লেখাটা নিয়ে সবারই সমস্যা হচ্ছে,উপরে ফেসবুক কমেন্টগুলা দেখলেই বুঝবা। যাই হোক আমি আবার নতুন করে লিখলাম,কোডটাও সিম্পল করে লিখলাম,এখন আশা করি সমস্যা হবেনা।
  
  Reply
মুকিত says:

অক্টোবর ৭, ২০১২ at ১১:০১ am

minimum vertex cover এর প্রবলেম আর কোথায় পাব ? কিছু প্রবলেম দিতে পারবে ? edges[u].size() কখন 0 হয়,তা ক্লিয়ার ছিল না… UVA এর প্রবলেম টা করতে গিয়ে ক্লিয়ার হলাম… 🙂
আরো কিছু প্রবলেম করলে আরো ক্লিয়ার হবে 🙂
আর ডিপি solution জানা থাকলে max flow দিয়ে শিখার প্রয়োজন আছে ? নাকি ডিপি solution এরও কিছু limitation থাকতে পারে,যা max flow দিয়ে cover হবে ?
সব শেষে ধন্যবাদ আরেকটি মজার algorithm শিখানোর জন্য …… 🙂

Reply
1. শাফায়েত says:
  
  অক্টোবর ৭, ২০১২ at ২:২৫ pm
  
  এটা করতে পারো: ANGELS । আরেকটু কঠিন একটা প্রবলেম: SAM I AM। ম্যাচিং/ফ্লো দিয়ে শেখার অবশ্যই দরকার আছে,তাহলে অনেক ভ্যারিয়েশন হ্যন্ডেল করতে পারবে। উপরের দুইটা আমি ম্যাচিং দিয়ে করসি। আর ফ্লো দিয়ে অনেক টাইপের প্রবলেম সলভ করা যায় খুবই elegant ভাবে,আমার মতে ফ্লো ভালোভাবে না জানলে অ্যালগোরিদম শেখা অসম্পূর্ণ থেকে যাবে।
  
  Reply
মুকিত says:

অক্টোবর ৮, ২০১২ at ১১:৫০ am

দু’টো প্রবলেমই কঠিন লাগলো !!! 🙁
হুম… তাহলে আর কি !!! অপেক্ষায় আছি, কখন flow/matching নিয়ে tutorial পাবো !!!

Reply
1. শাফায়েত says:
  
  অক্টোবর ৮, ২০১২ at ৮:০৪ pm
  
  টপকোডার টিউটোরিয়াল দেখো,flow/matching এর জন্য টপকোডার বেস্ট।
  
  Reply
মুকিত says:

অক্টোবর ৮, ২০১২ at ৮:০৭ pm

thank u… আপাতত তোমার আরেকটি টিউটোরিয়াল
দেখছি… 🙂

Reply
মাজহারুল says:

অক্টোবর ৩১, ২০১২ at ১:১০ pm

এখানে এই আলগও কি কাজ করবে না
সবচে বেশি ডিগ্রীর নোড নিব
এর সাথে যুক্ত সব নোড ভিসিটেড দিব
ভিসিটেড হয় নাই & সবচে বেশি ডিগ্রীর নোড নিব

Reply
শাফায়েত says:

অক্টোবর ৩১, ২০১২ at ৫:৩৫ pm

@মাজহারুল: না greedy কাজ করবেনা। এই গ্রাফে ভুল আসবে:
1 2
2 5
1 3
3 6
1 4
4 7
greedy তে ৪ আসবে(১,৫,৬,৭) কিন্তু ৩টা নোড দিয়ে কভার করা যায়(২,৩,৪)।

Reply
Mohiuddin Ahmed says:

নভেম্বর ২০, ২০১২ at ১০:৪২ pm

Dear Brother,
I really love your tutorial. Inspired by your tutorial, I started solving the problem uva-10243(fire fire fire)…

I’m very close to the solution, already get the correct answer using your programming concept. But, as I’m new in programming, just stuck in a way. When, I just took the input for one test case, it just showing result fine. but the problem is, when I tried to get the input using a while, and tried to memset the dp array, the problem stopped working….

Here is the code…

I’ll be very glade if you just have a look at my code and figure out for me the problem.

#include
#include
#include

using namespace std;

#define MAX 10002
#define min(a, b) (a > b) ? b : a

int dp[MAX][5];
int par[MAX];

vectoredges[MAX];

int f(int u, int isFire){

if( edges[u].size()==0 ) return 0;
if( dp[u][isFire] != -1 ) return dp[u][isFire];
int sum = 0;
for(int i=0; i<edges[u].size(); i++){
int v = edges[u][i];

if(v != par[u]) {
par[v] = u;

if(isFire == 0) sum += f(v, 1);
else sum += min( f(v, 0), f(v, 1));
}
}
return dp[u][isFire]= sum + isFire;
}

int main(){

freopen("in.txt", "r", stdin);

int no;
while(1){
scanf("%d", &no);
if(no==0) break;
memset(dp, -1, sizeof dp );
for(int i=1; i<=no; i++ ){
int n;
scanf("%d", &n);
if(n != 0){
for(int j=0;j<n;j++){
int v;
scanf("%d", &v);
edges[i].push_back(v);
}
}

}
printf("%d\n", min(f(1, 1), f(1, 0)));
}
return 0;
}

Thanks, in advance…

Mohiuddin Ahmed

Reply
সিয়াম says:

আগস্ট ৮, ২০১৩ at ১২:২৬ am

কোন কোন node এ বসাইছি সেটা print করবো কিভাবে ?

Reply
1. শাফায়েত says:
  
  আগস্ট ১২, ২০১৩ at ১০:৫০ pm
  
  u থেকে v তে একবার পাহারাদার বসায় এবং আরেকবার না বসায় ক্যালকুলেট করে ম্যাক্স নিচ্ছি আমরা। নেয়ার সময় চেক করো বসালে ম্যাক্স হয় নাকি না বসালে ম্যাক্স হয়। একটা ডিরেকশন অ্যারেতে ইনফরমেশনটা রেখে দাও। যেমন dir[u][v]=1 মানে v তে বসাতে হবে,dir[u][v]=0 মানে বসাতে হবেনা। এখন প্রথম নোড থেকে শুরু করে ট্রি টা আবার ট্রাভার্স করো আর করার সময় চেক করো কোন কোন নোডে বসানো হচ্ছে।
  
  ম্যাচিং দিয়ে সলভ করলে konigs theorem ব্যবহার করে সহজেই প্রিন্ট করা যায়। উইকিতে সার্চ করো।
  
  Reply
ইমরান says:

অক্টোবর ১১, ২০১৩ at ১১:৩৫ am

ভাইয়া, LightOJ এর মিনিমান ভার্টেক্স কভার রিলেটেড প্রব্লেম নাম্বারগুলো দিতে পারবেন?

Reply
রাশিক says:

ডিসেম্বর ১১, ২০১৩ at ৩:১৪ pm

ভাইয়া SAM I AM প্রবলেমটাতে ট্রি কনস্ট্রাক্ট করতে পারছিনা। সাইকেল এসে যাচ্ছে। সাইকেলে ম্যাক্স ফ্লো নির্ধারন করবও কিভাবে??

Reply
Muhaimin says:

সেপ্টেম্বর ১৩, ২০১৫ at ১২:১৮ am

More related problem from LOJ 1201 , 1230

Reply
Nazmus Sakib says:

এপ্রিল ১৭, ২০১৬ at ৫:২৫ am

Brother. Is the complexity here O(v+e)?

Reply
Avik says:

জুনe ১২, ২০১৭ at ১০:২৭ am

” ১০ নম্বর লাইনে ট্রি এর সাইজ ১ হলে ১ রিটার্ণ করে দিয়েছি। ” – ভাইয়া ১০ নম্বর লাইনে তো look up table ইউজ করেছেন নোড টা আগে ভিজিটেড হয়েছে কিনা সেটা চেক করার জন্য ।

Reply