ডিপি

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

(সবগুলো পর্ব) ডাইনামিক প্রোগ্রামিং দিয়ে ট্রি(Tree) সংক্রান্ত অনেক সমস‍্যার সমাধান করা যায়। সাধারণ গ্রাফে পলিনোমিয়াল টাইমে সমাধান করা যায় না এমন অনেক প্রবলেম ট্রি গ্রাফে সহজেই ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায় কারণ ট্রি তে কোন সাইকেল থাকে না। এই পর্বে আমরা সেরকমই একটা ক্লাসিক প্রবলেম দেখবো যার নাম মিনিমাম ভারটেক্স কভার। ধরা যাক একটি শহরে কিছু রাস্তা আছে, এখন প্রতি রাস্তায় মোড় বা জাংশনে আমরা পাহারাদার বসাতে চাই। কোনো মোড়ে পাহারাদার বসালে সে মোড়ের সাথে যুক্ত রাস্তাগুলো একাই পাহারা দিতে পারে। এখন তোমাকে বলতে হবে সব কয়টা রাস্তা পাহারা দিতে নূন্যতম কয়জন পাহারাদার দরকার? একট...
Read More

ডাইনামিক প্রোগ্রামিং ৮ (বিটমাস্ক, ট্রাভেলিং সেলসম‍্যান)

(সবগুলো পর্ব) বিটমাস্ক ব‍্যবহার করে বেশ কিছু NP-Complete/NP-Hard প্রবলেম সলভ করা যায়। বিটমাস্কের ব‍্যবহার জানা থাকলে এটা তেমন কঠিন কিছু নয়। এই লেখা পড়ার আগে তোমার জানা লাগবে কিভাবে বিট ম‍্যানিপুলেশন করতে হয়, সেজন‍্য তুমি এই লেখাটা পড়তে পারো। এই প্রবলেম সলভ করতে গ্রাফ থিওরি জানার দরকার নেই। আজকে আমরা বিখ‍্যাত ট্রাভেলিং সেলসম‍্যান প্রবলেম বিটমাস্ক দিয়ে সলভ করবো।  প্রবলেমটা হলো তোমাকে কিছু শহর এবং রাস্তা একটা গ্রাফ হিসাবে দেয়া আছে। তোমাকে প্রথম শহর থেকে শুরু করে সবগুলো শহর ঠিক একবার করে ভ্রমণ করে প্রথম শহরে ফিরে আসতে হবে। প্রশ্ন হলো সর্বনিম্ন কত দূরত্ব অতিক্রম করে তুমি কাজটা করতে পারব...
Read More

ডাইনামিক প্রোগ্রামিং ৭ (ম‍্যাট্রিক্স চেইন মাল্টিপ্লিকেশন)

(সবগুলো পর্ব) ম‍্যাট্রিক্স চেইন মাল্টিপ্লিকেশন আরেকটা ক্লাসিক ডাইনামিক প্রোগ্রামিং প্রবলেম যেখানে আমাদেরকে বের করতে হবে কিছু ম‍্যাট্রিক্সকে কিভাবে সবথেকে কম অপারেশন ব‍্যবহার করে গুণ করা যাবে।  ডিভাইড এন্ড কনকোয়ার পদ্ধতির খুবই চমৎকার একটা উদাহরণ এই প্রবলেমটা। আমি আশা করবো ম‍্যাট্রিক্স কিভাবে গুণ করতে হয় সেটা সবাই জানো, আমি সেটা নিয়ে বিস্তারিত বলবো না। আমি খালি কয়েকটা প্রোপার্টির কথা মনে করিয়ে দিতে চাই। ধরা যাক আমাদের দুটি ম‍্যাট্রিক্স আছে $A_{1}$ এবং $A_{2}$ এবং তাদের ডাইমেনশন হলো $(r_{1} \times c_{1})$ এবং $(r_{2} \times c_{2})$। $A_{1}$ এবং $A_{2}$ গুণ করা যাবে শুধুমাত্র যদি $...
Read More

ডাইনামিক প্রোগ্রামিং ৬ (সাবসেট সাম, কম্বিনেটরিক্স, ডিসিশন প্রবলেম)

আগের পর্বগুলোয় যেসব প্রবলেম দেখেছি তার মধ‍্যে ফিবোনাচ্চি সবগুলোতেই আমাদেরকে কিছু না কিছু ম‍্যাক্সিমাইজ বা মিনিমাইজ করতে হয়। এগুলো ছাড়া ডাইনামিক প্রোগ্রামিং এর আরো কিছু ব‍্যবহার আছে, একটা হলো কোন একটা কাজ কত ভাবে করা যায় সেটা বের করা, আরেকটা হলো ডিসিশন প্রবলেম সলভ করা (অর্থাৎ কোন একটা কাজ করা যাবে কি যাবে না সেটা বের করা)। শুরুতেই দেখবো সাবসেট সাম প্রবলেম। এই প্রবলেমটা অনেকটাই কয়েন চেঞ্জ প্রবলেমের মত, আশা করবো তুমি কয়েন চেঞ্জ নিয়ে লেখাটা পড়ে ফেলেছো, কারণ এবার আমি আগের মত এত বিস্তারিত বর্ণনা করবো না। সাবসেট সাম তোমাকে একটা ইন্টিজার অ‍্যারে $C$ দেয়া আছে এবং একটা ভ‍্যালু $W$ দে...
Read More

ডাইনামিক প্রোগ্রামিং ৫ (কয়েন চেঞ্জ, ০-১ ন‍্যাপস‍্যাক)

(আগের পর্ব) আজকে আরো দুটি ক্লাসিকাল ডাইনামিক প্রোগ্রামিং প্রবলেম শিখবো। প্রথমটা হলো কয়েন চেঞ্জ। প্রবলেমটার নাম শুনেই বোঝা যাচ্ছে এটা টাকা ভাংতি করা নিয়ে প্রবলেম, তোমাকে সবথেকে কম সংখ‍্যক কয়েন ব‍্যবহার করে নির্দিষ্ট পরিমাণ টাকা ভাংতি করতে হবে। মনে করো তোমার কাছে $n$ টা ভিন্ন ভিন্ন কয়েন আছে, কয়েনগুলোর ভ‍্যালুকে $C_{0},  C_{1}...C{n-1}$ দিয়ে প্রকাশ করা যায়। আর তোমাকে  একটা অ‍্যামাউন্ট দেয়া আছে $W$। এখন  তোমাকে বলতে সর্বনিম্ন কয়টা কয়েন ব‍্যবহার করে তুমি $W$ অ‍্যামাউন্টটা বানাতে পারবে। প্রতিটা ভ‍্যালুর কয়েন আছে মাত্র ১টা করে। একটা উদাহরণ দেখি। ধরা যাক কয়েনগুলোর ভ‍্যালু হলো $C = \...
Read More

ডাইনামিক প্রোগ্রামিং ৪ (লংগেস্ট কমন সাবসিকোয়েন্স)

আগের পর্ব গুলোতে আমরা যেসব প্রবলেম দেখে এসেছি সেগুলোর সাবপ্রবলেমের স্টেট ছিল মাত্র ১টা। এইবার আমরা আরেকটু জটিল সমস‍্যা সমাধান করবো যার নাম লংগেস্ট কমন সাবসিকোয়েন্স বা LCS। এটা শেখার পরে আমি এডিট ডিসটেন্স প্রবলেম নিয়ে অল্প কিছু কথা বলবো এবং তোমার কাজ হবে সেটা নিজে নিজে সমাধান করা। এই প্রবলেমে তোমাকে দুটি স্ট্রিং দেয়া থাকবে $S$ এবং $W$। তোমাকে তাদের মধ‍্যে লংগেস্ট কমন সাবসিকোয়েন্স এর দৈর্ঘ‍্য বের করতে হবে। সাবসিকোয়েন্সের সংজ্ঞাটা মনে করিয়ে দেই, একটা স্ট্রিং থেকে কিছু ক‍্যারেক্টার মুছে দিলে যা বাকি থাকে সেটাই স্ট্রিংটা সাবসিকোয়েন্স। একটা স্ট্রিং এর $2^{n}$ টা সাবসিকোয়েন্স থাকতে পার...
Read More

ডাইনামিক প্রোগ্রামিং-৩ (লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স, পাথ প্রিন্টিং)

আমরা এরই মধ‍্যে ডাইনামিক প্রোগ্রামিং এর বেসিক শিখে গিয়েছি, আমরা ফিবোনাচ্চি এবং DAG এ শর্টেস্ট পাথ বের করতে পারি। এবার আমরা শিখবো Longest Increasing Subsequence বা LIS বের করা। এতদিন আমরা শুধু অপটিমাল সলিউশনটা বের করতে শিখেছি, কোন পথ ধরে সলিউশনে পৌছাতে হয় সেটা বের করা শিখিনি। এবার আমরা নেক্সট-পয়েন্টার ব‍্যবহার করে সেটা বের করাও শিখবো। ধরা যাক আমাদের নিচের ছবির মতো একটা অ‍্যারে আছে যার নাম $A$। একটা অ‍্যারের সাবসিকোয়েন্স বলতে বুঝায় অ‍্যারে থেকে কিছু এলিমেন্ট মুছে দিলে বাকি যে সিকোয়েন্সটা থাকে সেটা। এলিমেন্টগুলোর অর্ডারিং পরিবর্তন করা যাবে না। $n$ সাইজের একটা অ‍্যারের $2^{n}$ টি স...
Read More

ডাইনামিক প্রোগ্রামিং-২ (শর্টেস্ট পাথ)

আগের পর্বে আমরা ফিবোনাচ্চি নাম্বার নিয়ে আলোচনা করেছি। আমরা দেখেছি কিভাবে ডাইনামিক প্রোগ্রামিং ব‍্যবহার করে রিকার্সিভলি এবং ইটারেটিভলি ফিবোনাচ্চি সংখ‍্যা জেনারেট করা যায়। এই পর্বে আমরা কথা বলবো শর্টেস্ট পাথ প্রবলেম নিয়ে এবং সেটা নিয়ে আলোচনা করার সময় ডিপির কিছু নতুন প্রোপার্টি নিয়ে জানবো। যদিও শর্টেস্ট পাথ গ্রাফ থিওরির একটা প্রবলেম, এই লেখা বুঝতে গ্রাফ নিয়ে না জানলেও চলবে। মনে করো আমাদেরকে এক শহর থেকে অন‍্য শহরে যাবার শর্টেস্ট পাথ খুজে বের করতে হবে। শহর আছে মোট $n$ টি। $0$ হলো প্রথম শহর, এবং $n - 1$ হলো শেষ শহর। কোন শহর থেকে কোন শহরে সরাসরি যাওয়া যায় এবং শহরগুলোর মধ‍্যে দুরত...
Read More

ডাইনামিক প্রোগ্রামিং – ১ (ফিবোনাচ্চি)

ডাইনামিক প্রোগ্রামিং নামটা শুনতে একটু কঠিন মনে হলেও এর পিছনে কনসেপ্টটা বেশ সহজ। ডাইনামিক প্রোগ্রামিং কে এক কথায় বর্ণনা করতে গেলে বলা যায় - একটা সমস‍্যাকে ছোট ছোট ভাগ করে সাব-প্রবলেমগুলো সমাধান করবো তবে একই সাবপ্রবলেম একবারের বেশি সমাধান করবো না। মোটা দাগে বলতে গেলে এটাই ডাইনামিক প্রোগ্রামিং। তবে কখন একটা প্রবলেমকে ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যাবে সেটা বুঝতে একটু অভিজ্ঞতা প্রয়োজন। তো এই সিরিজে আমরা দেখবো ডাইনামিক প্রোগ্রামিং কি এবং কিছু কমন সমস‍্যা যেগুলো ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায়। ডাইনামিক প্রোগ্রামিং বা ডিপি টার্মটা একটু কনফিউজিং কারণ 'ডাইনামিক' শব্...
Read More

ম‍্যাট্রিক্স চেইন মাল্টিপ্লিকেশন

[নোটিশ ২৩ এপ্রিল ২০২০: ডাইনামিক প্রোগ্রামিং এর নতুন সিরিজ শুরু করেছি। লেখাটি নতুন ভার্সন এখানে পাওয়া যাবে। আমরা এবার আরো একটি ক্লাসিক ডাইনামিক প্রোগ্রামিং প্রবলেম দেখবো যেটার নাম ম‍্যাট্রিক্স চেইন মাল্টিপ্লিকেশন। এটা শেখা খুবই গুরুত্বপূর্ণ কারণ এটার ধারণা ব‍্যবহার করে অনেক ধরণের সমস‍্যা সমাধান করে ফেলা যায়। এই লেখাটা পড়ার আগে তোমার ডাইনামিক প্রোগ্রামিং এর ধারণা থাকতে হবে। এছাড়া ম‍্যাট্রিক্স নিয়েও ধারণা থাকতে হবে। আমি নিশ্চিত তোমরা সবাই ম‍্যাট্রিক্স গুণের শর্তগুলো জানো, তাও আমি মনে করিয়ে দিতে চাই। ধরি আমাদের দুটি ম‍্যাট্রিক্স আছে $A_1, A_2$ এবং তাদের ডিমেনশন $m * n$ আর $p * q$। তা...
Read More

ডাইনামিক প্রোগ্রামিং: লংগেস্ট কমন সাবসিকোয়েন্স [পুরানো ভার্সন]

[নোটিস: ডাইনামিক প্রোগ্রামিং নিয়ে আমি নতুন একটা সিরিজ শুরু করেছি। নতুন ভার্সন পড়তে হলে এখানে ক্লিক করো] ডাইনামিক প্রোগ্রামিং এর সম্ভবত সবথেকে গুরুত্বপূর্ণ দুটি উদাহরণ হলো লংগেস্ট কমন সাবসিকোয়েন্স এবং এডিট ডিসটেন্স বের করা কারণ এদের অনেক প্র্যাক্টিকাল অ্যাপ্লিকেশন আছে। এই লেখাটা পড়ার আগে আমি আশা করবো তোমরা কিছু বেসিক ডাইনামিক প্রোগ্রামিং যেমন কয়েন চেঞ্জ, ন্যাপস্যাক পারো। যদি না পারো তাহলে আমার আগের লেখাগুলো দেখতে পারো। এই লেখায় লংগেস্ট কমন সাবসিকোয়েন্স বের করা, সলিউশন প্রিন্ট করাএবং সবগুলো সম্ভাব্য সলিউশন বের করা দেখবো। তুমি যদি আগেই এসব টপিক নিয়ে জানো তাহলে লেখার শেষে রিলেটেড...
Read More

বিটমাস্ক ডাইনামিক প্রোগ্রামিং

[ডাইনামিক প্রোগ্রামিং নিয়ে আমি নতুন একটা সিরিজ শুরু করেছি। এই লেখাটার নতুন ভার্সন পাওয়া যাবে এখানে] আশা করি তুমি এখন lis,knapsack,coin-change প্রবলেম সলভ করতে পারো খুব সহজেই, ডিপির সলিউশন প্রিন্ট করতেও তোমার সমস্যা হয়না। এখন আমরা একটু অন্যরকম ডিপি দেখবো যেটার নাম বিটমাস্ক ডিপি। নামটা শুনে ভয় লাগলেও জিনিসটা সহজ, অনেক ক্ষেত্রেই বিটমাস্ক ডিপি প্রবলেম পড়ার সাথে সাথে সলিউশন মাথায় চলে আসে। তবে এই পর্বটা পড়ার আগে তোমাকে বিট নিয়ে কাজ করা শিখতে হবে, যেমন কোনো নির্দিষ্ট পজিশনের বিট অন করা/অফ করা ইত্যাদি। এজন্য তুমি এই চমৎকার টিউটোরিয়ালটা দেখতে পারো, পুরোটা খুবই ভালো করে পড়বে কারণ এটা তোমাদে...
Read More

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

(নোটিশ: ডাইনামিক প্রোগ্রামিং এর একটি নতুন সিরিজ আমি শুরু করেছি, এই লেখাটির নতুন ভার্সন পাওয়া যাবে এখানে) মিনিমাম ভারটেক্স কভার একটি ক্লাসিক গ্রাফ প্রবলেম। ধরা যাক একটি শহরে কিছু রাস্তা আছে,এখন প্রতি রাস্তায় মোড়ে আমরা পাহারাদার বসাতে চাই। কোনো নোডে পাহারাদার বসালে সে নোডের সাথে যুক্ত রাস্তাগুলো একাই পাহারা দিতে পারে। উপরের ছবিতে নোডগুলো হলো রাস্তার মোড়। এখন সব কয়টা রাস্তা পাহারা দিতে নূন্যতম কয়জন পাহারাদার দরকার? ছবিতে লাল নোডগুলোতো পাহারাদার বসানো হয়েছে। এটা অপটিমাল না,নিচের ছবির মত বসালে পাহারাদার কম লাগত: এটি একটি NP-hard প্রবলেম,অর্থাৎ এই প্রবলেমের কোনো পলিনমিয়াল...
Read More

ইউভিএ ১০৭০২(ট্রাভেলিং সেলসম্যান)

ট্রাভেলিং সেলসম্যান মূলত একটি NP-complete ক্লাসিকাল প্রবলেম। uva 10702 মূল প্রবলেমের পরিবর্তিত রূপ যা ডাইনামিক প্রোগ্রামিং এর মাধ্যমে সমাধান করা সম্ভব। একজন ফেরিওয়ালা এক শহর থেকে অন্য শহরে ঘুরে জিনিসপত্র বিক্রি করে। সে কোনো শহরে একাধিক বার যেতে পারে(ক্লাসিক tsp প্রবলেমে একটি নোড একবারের বেশি ভিজিট করা যায়না)। একটি শহর থেকে আরেকটি শহরে গেলে নির্দিষ্ট পরিমাণ লাভ হয়। ফেরিওয়ালা নির্দিষ্ট কিছু শহরে তার যাত্রা শেষ করে এবং যাত্রা শেষ করার আগে নির্দিষ্ট সংখ্যক বার বিভিন্ন শহরে ভ্রমণ করে(inter-city travel)। বলতে হবে সে সর্বোচ্চ কত লাভ করতে পারবে। এই প্রবলেমে গ্রাফটি complete,সব শহর থেকে সব শহরে যা...
Read More