ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-৪

০-১ ন্যাপস্যাক,কয়েন চেঞ্জ প্রবলেমে আশা করি তোমার এখন দক্ষতা এসে গিয়েছে। এই পর্বে আমরা দেখবো LIS, একই সাথে দেখবো কিভাবে ডিপিতে সলিউশন প্রিন্ট করতে হয় ,এটা নিয়ে তোমাদের অনেকেরই সমস্যা হয়েছে বলে জানিয়েছো। এছাড়া আগের পর্বে light oj 1231 প্রবলেমটি সলভ করতে বলেছিলাম,আমার সলিউশন পাবে লেখার একদম শেষে।

প্রথমেই শুরু করি LIS এবং এটার সলিউশন প্রিন্ট করা দিয়ে। LIS হলো Longest increasing subsequence। মনে করো তোমাকে একটি অ্যারে বা sequence দেয়া আছে:
এই অ্যারে থেকে কিছু সংখ্যা মুছে দিয়ে এবং অর্ডার ঠিক রেখে আমরা বিভিন্ন subsequence পেতে পারি। যেমন:

5 7
5 9 2
0 3 4
0 2 3 4
7 3
5 0 9 2 7 3 4 (শুন্যটি সংখ্যা বাদ দেয়া হয়েছে)
….

একটা sequence এ n টি সংখ্যা থাকলে subsequence থাকতে পারে মোট 2^n টি(কেন??)। increasing subsequence(IS) এ প্রতিটা সংখ্যা তার আগের সংখ্যাটির থেকে বড় হবে। উপরে ১ম , ৩য়, ৪র্থ subsequence গুলো increasing। যতগুলো IS আছে তারমধ্যে সবথেকে বড়টা খুজে বের করাই আমাদের লক্ষ্য। উপরে ৪নম্বরটির length ৪ এবং সবগুলো IS এর মধ্যে এটাই সব থেকে বড়।
প্রবলেমটাকে গ্রাফ দিয়ে মডেলিং করলে খুব সহজে সলভ করা যায়। গ্রাফ থিওরি না জানলেও কোনো সমস্যা হবেনা,গ্রাফ দেখাচ্ছি খালি বোঝার সুবিধার জন্য। প্রথমেই মনে করি অ্যারের প্রতিটি ইনডেক্স হলো একটি করে নোড:

এখন দুটি শর্ত খেয়াল করো। u নম্বর নোড থেকে v নম্বরে নোডে যাওয়া যাবে যদি:

১. v>u হয়। কারণ আমাদের মূল sequence এর অর্ডার ঠিক রাখতে হবে।
২. value[v]>value[u] হয়,কারণ sequence টা increasing হতে হবে।

তাহলে ১ থেকে ২ এ যেতে পারবোনা কারন value[1] < value[2],তবে ১ থেকে ৩ এ যেতে পারবো। তাহলে আমরা গ্রাফের edge গুলো আকি:

lis3

দেখতে হিজিবিজি হলেও ভয় পাবার কিছু নাই,উপরের শর্ত দুটি মেনে গ্রাফটি আকা হয়েছে। গ্রাফের যেকোনো পাথ অনুসরণ করলে আমরা একটা ইনক্রিসিং সিকোয়েন্স পাবো। যেমন গ্রাফে ২-৬-৭ পাথে গেলে ০-৩-৪ সাবসিকোয়েন্সটা পাবো। তাহলে বুঝতেই পারছো সবথেকে লম্বা পথটাই আমার সলিউশন, যতদূরে যেতে পারবো সিকোয়েন্স তত বড় হবে, এক্ষেত্রে একটি path এ যে কয়টি নোড আছে সেটাই পাথের দৈর্ঘ্য।

মনে করি আমাদের একটা ফাংশন আছে longest(u) যেটা u নম্বর নোড থেকে longest path রিটার্ন করে। যেমন longest(6)=2 কারণ ৬ নম্বর নোড থেকে খালি ৬-৭ এই পাথে যাওয়া যায়। এখন লক্ষ করো:

কোনো নোড থেকে longest path হবে সেই নোড থেকে যেসব নোডে যাওয়া যায় সেগুলো থেকে longest path এর maximum + ১।

আমরা সহজেই একটা রিকার্সিভ রিলেশন বের করে ফেলতে পারি:

longest(2)=1+max(longest(3),longest(4),longest(5),longest(6),longest(7))
longest(1)=1+max(longest(3),longest(5))
longest(3) =1 (এটা একটা বেসকেস কারণ ৩ থেকে কোথাও যাওয়া যায়না)

…………
অর্থাৎ u থেকে v1,v2,v3…,vk নোডে যাওয়া গেলে:
longest(u)=1+max(longest(v1),longest(v2)….,longest(vk))

এখন আমরা সহজেই কোড করে প্রতিটা নোড থেকে longest path বের করে ফেলতে পারি:

longest(u) প্রতিটা নোড u থেকে longest path রিটার্ন করে,এদের মধ্যে আবার যেটা ম্যাক্সিমাম সেটাই আমাদের LIS। এই সলিউশনটা কমপ্লেক্সিটি O(n^2)(আরো ভালো একটা সলিউশন আছে বাইনারী সার্চ ব্যবহার করে)। এখন সলিউশন প্রিন্ট করার পালা।
আসলে মুল কাজটা আমরা উপরের কোডেই করে ফেলসি। dir[] নামের একটি অ্যারে রেখেছি যে প্রতিটা নোডের জন্য যে ডিরেকশনে সর্বোচ্চ মান পাওয়া যায় সেটা সেভ করে রাখে। কোনো নোড থেকে অন্য কোথাও যাওয়া না গেলে ডিরেকশন হবে -১। এখন সলিউশন ফাংশন হবে এরকম:

অর্থাৎ ডিরেকশন অ্যারে দেখে আমরা সামনে যাবো যতক্ষণ যাওয়া যায়।

এখানে লক্ষ্য করার কিছু বিষয় হলো উপরের গ্রাফটিতে কোনো সাইকেল নেই দেখে আমরা ডিপি করতে পেরেছি,এধরণের গ্রাফকে বলা হয় directed acyclic graph বা ড্যাগ। কোনো প্রবলেমকে তুমি যদি ড্যাগ এ কনভার্ট করতে পারো তাহলে খুব ভালো সম্ভাবনা আছে যে প্রবলেমটি ডিপি চালিয়ে সলভ করা যাবে। গ্রাফে সাইকেল থাকলে longest path একটি np-complete প্রবলেম,অর্থাৎ পলিনমিয়াল সলিউশন জানা নেই। এখন একটি প্রশ্ন: একটা sequence এর কয়টি LIS আছে সেটা বের করতে বলা হলে কি করবে? চিন্তা করে জানাও :-)।

আমরা জানি ০-১ন্যাপস্যাকে স্টেট থাকে ২টা,সেক্ষেত্রে ডিরেকশন অ্যারের স্টেটও হবে ২টা। নিচের কোডটা দেখো:

ন্যাপস্যাকের কোডটাকে সামন্য পরিবর্তন করে ডিরেকশন রাখা হয়েছে। আমাদের starting state হলো (i=1,w=0),কারণ শুরুতে আমরা ১ নম্বর জিনিসটা নিয়ে ট্রাই করবো এবং এখন পর্যন্ত নেয়া জিনিসের ওজন ০। ডিপি শেষ হবার পর যদি:

dir[i][w] = ১ হয় তাহলে i নম্বর জিনিসটি নিবো, i প্রিন্ট করে আমরা চলে যাবো (i+1,w+weight[i]) স্টেটে।
dir[i][w] = ২ হয় তাহলে i নম্বর জিনিসটি নিবো না,i প্রিন্ট না করেই আমরা চলে যাবো (i+1,w) স্টেটে।
dir[i][w] = -১ হলে আমরা থেমে যাবো।

এটাই হলো ডিপির সলিউশন প্রিন্টের মূল কথা। ডিপি অ্যারের পাশাপাশি ডিরেকশন অ্যারেতে সেভ করে রাখবো কোন স্টেট থেকে কোন স্টেটে যাচ্ছি সেটা। এরপর starting state থেকে ডিরেকশন অনুযায়ী আগাতে থাকবো আর প্রিন্ট করবো।

printdp

আজকের পর্ব এখানেই শেষ। light oj 1231 এর সলিউশন: http://pastebin.com/vmpWp0g1, mod করার অংশটা বুঝতে না পারলে এই লেখাটা দেখো। সলভ করার জন্য প্রবলেম:

Diving for gold
Sense of Beauty
Bicolored Horses
Testing the CATCHER
How Many Dependencies?
Longest Path

পরের পর্ব-বিটমাস্ক ডিপি
সবগুলো পর্ব

Print Friendly

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

comments

Powered by Facebook Comments

26,062 বার পড়া হয়েছে

21 thoughts on “ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-৪

  1. Lightoj 1231 নাম্বার নিয়ে একটা প্রশ্ন আছে…
    এর আগের পোস্ট থেকে জেনেছিলাম,একই আইটেম একাধিকবার নিলে জাস্ট i+1 এর পরিবর্তে i লিখলেই চলবে…কিন্তু ১২৩১ নং প্রবলেম করতে গিয়ে এটা মানা হয়নি…এটাতে আমি যখন coin[i] নিয়ে make বানানোর try করছি,তখনও i+1 দিয়ে call করছি ( এইক্ষেত্রে শুধু i লিখলে হচ্ছে না কেন ),আবার যখন coin[i] না নিয়ে try করছি,তখনও i+1 call করছি…
    উত্তরটা পেলে আরো উপকৃত হব …

    1. এখানে ব্যাপারটা একটু ভিন্ন। ভিতরের for লুপটা দিয়ে আমরা একটা আইটেম কয়বার নিবো সেটা বলে দিচ্ছি,তাই আবার i কল করা দরকার নাই। কোনো আইটেম যদি লিমিটেড সংখ্যকবার নেয়া যায় তাহলে ভিতরে লুপ চালিয়ে কয়বার নিচ্ছি সেটা বলে দেয়া যায়। আগেরবার প্রতিবার ১টা করে নিচ্ছিলাম,তাই একইটা আরেকবার নিতে চাইলে i তে কল দেয়া দরকার ছিলো।

  2. আরেকটি প্রশ্ন…
    profit1 যখন profit2 থেকে বড় হচ্ছে তখন আমি dir[] array তে 1 রাখছি(অর্থাৎ সেটি প্রিন্ট করব)…কিন্তু যখন equal হচ্ছে তখন নিচ্ছি না কেন? logic টা বললে আরো ভাল বুঝতে পারতাম… এই ব্যাপারটিতে problem হচ্ছে…

    1. আসলে profit1==profit2 হলে dir অ্যারেতে ১ বা ২ কিছু একটা রাখলেই হবে, একটা ন্যাপস্যাক প্রবলেমের অনেকগুলো সলিউশন থাকতে পারে।

  3. n element এর একটা array দেয়া আছে, সেটা থেকে exactly k সংখ্যক সংখ্যা নিতে হবে যাতে তাদের যোগফল w এর সবচেয়ে কাছাকাছি এবং <=w হয়। এই problemটা O(nkw)এর চেয়ে efficiently কিভাবে করা যাবে???

  4. How Many Dependencies? প্রবলেমে বলা আছে ‘You can assume there will be no cyclic dependencies in the input’ । কিন্তু আমার মনে হয় সাইকেল আছে । কারণ আমি ভিসিটেড অ্যারে ছাড়া কয়েকবার ট্রাই করে টিএলই খাইছি :\

Leave a Reply

Your email address will not be published. Required fields are marked *


Time limit is exhausted. Please reload CAPTCHA.