এখানে, আমরা C-তে মিনিমাম কস্ট পাথ প্রোব্লেম সমাধান করব। ইমপ্লিমেন্টেশন করা হয়েছে একটি ২D-ম্যাট্রিক্স (2D-matrix)-এ যেখানে প্রতিটি সেলে (cell) ট্রাভেল করার একটি কস্ট (cost) আছে। আমাদের বাম উপরের কোণার (left top corner) থেকে ডান নিচের কোণার (bottom right corner) পর্যন্ত এমন একটি পাথ খুঁজে বের করতে হবে যেন ট্রাভেল কস্ট ন্যূনতম হয়। আপনি একটি সেল থেকে শুধু নিচে (down) এবং ডান নিচে (right lower) সেলগুলোতে যেতে পারেন।
এই বিশেষ সমস্যাটি সমাধান করতে রিকার্সন (recursion)-এর চেয়ে ডাইনামিক প্রোগ্রামিং (dynamic programming) খুব ভালো অ্যাপ্রোচ।
দেওয়া কস্ট ম্যাট্রিক্স cost[][] এবং একটি পজিশন (m,n), আমাদের একটি ফাংশন লিখতে হবে যা (০,০) থেকে (m,n) পৌঁছানোর মিনিমাম পাথ কস্ট রিটার্ন করে। (m, n) পৌঁছানোর একটি পাথের টোটাল কস্ট হল সেই পাথের সব কস্টের যোগফল (সোর্স এবং ডেস্টিনেশন উভয়ই অন্তর্ভুক্ত)।
অসাম্পশন (Assumption) − সব কস্ট পজিটিভ। ইনপুট ম্যাট্রিক্সে নেগেটিভ কস্ট সাইকেল (negative cost cycles) নেই।
উদাহরণ (Example)
(২,২) পজিশনে পৌঁছানোর মিনিমাম কস্ট পাথ বের করুন।
কস্টগুলো ছবিতে দেয়া আছে। পাথ হবে (0, 0) → (0, 1) → (1, 2) → (2, 2)। পাথের মান আট (১+২+২+৩)।
অ্যাপ্রোচ (Approach) − দেওয়া ম্যাট্রিক্সের মতো একই সাইজের একটি সলিউশন ম্যাট্রিক্স (solution matrix) তৈরি করা।
এই ম্যাট্রিক্সটিকে বটম-আপ (bottom-up) ম্যানারে পূরণ করা।
দেওয়া (Given) − arrA[][]. প্রতিটি সেলে, আমাদের ২ অপশন থাকে (ডান বা নিচে যাওয়া) এবং আমরা সেই ২টির মিনিমাম বেছে নেব, যেকোনো i,j সেলের জন্য।
solution[i][j] = A[0][j] if i=0, 1st row
= A[i][0] if j=0, 1st column
= A[i][j] + Min(solution[i-1][j], solution[i][j-1]) if i>0 && j>0
আলগরিদমিক সমাধানগুলোতে ফলো করা অ্যাপ্রোচ ডাইনামিক প্রোগ্রামিং-এ প্রয়োগ করে এই সমস্যাটি দক্ষতার সাথে সমাধান করা যায়। m,n সাইজের একটি মিনিমাম কস্ট পাথ টেবিল তৈরি করুন এবং ডিফাইন করুন−
minimumCostPath[i][j] = (0, 0) থেকে (i, j) পৌঁছানোর মিনিমাম ভ্যালু
স্পষ্টতই,
minimumCostPath[0][0] = costMatrix[0][0] minimumCostPath[i][0] = minimumCostPath[i-1][0] + costMatrix[i][0], for all i > 0 minimumCostPath[0][j] = minimumCostPath[0][j-1] + costMatrix[0][j], for all j > 0
পরবর্তী, আমরা মিনিমাম কস্ট পাথ ম্যাট্রিক্সটি উপরের ফর্মুলা প্রয়োগ করে পূরণ করব যা আমরা অ্যালগরিদমে প্রয়োগ করেছিলাম। যেহেতু সব আগের মানগুলো ইতিমধ্যে মিনিমাম কস্ট পাথ ম্যাট্রিক্সে ক্যালকুলেটেড আছে, আমরা সেগুলো রিকার্সিভ সমাধানের মতো বারবার ক্যালকুলেট করব না।
minimumCostPath[i][j] = costMatrix[i][j] + min(minimumCostPath[i-1][j-1], minimumCostPath[i-1][j], minimumCostPath[i][j-1])
এখানে, minimumCostPath[i][j] ক্যালকুলেট করার জন্য আমরা minimumCostPath[i-1][j-1], minimumCostPath[i-1][j] এবং minimumCostPath[i][j-1] ব্যবহার করি কারণ শুধু এই তিনটি পারমিশেবল সেল থেকে আমরা minimumCostPath[i][j]-এ পৌঁছাতে পারি। একেবারে শেষে, আমরা minimumCostPath[m][n] রিটার্ন করি।
ডাইনামিক প্রোগ্রামিং অ্যালগরিদমের টাইম কমপ্লেক্সিটি O(mn)।
উদাহরণ (C++ প্রোগ্রাম)
#include <iostream>
using namespace std;
int min_(int a, int b, int c) {
if (a < b)
return (a < c) ? a : c;
else
return (b < c) ? b : c;
}
int min_cost(int cost[4][4], int m, int n) {
int i, j;
int tot_cost[4][4];
tot_cost[0][0] = cost[0][0];
for (i = 1; i <= m; i++)
tot_cost[i][0] = tot_cost[i-1][0] + cost[i][0];
for (j = 1; j <= n; j++)
tot_cost[0][j] = tot_cost[0][j-1] + cost[0][j];
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
tot_cost[i][j] = min_(tot_cost[i-1][j-1], tot_cost[i-1][j], tot_cost[i][j-1]) + cost[i][j];
return tot_cost[m][n];
}
int main() {
int cost[4][4] = {
{9, 9, 4},
{8, 0, 9},
{1, 2, 8}
};
cout << "The minimum cost is " << min_cost(cost, 2, 2);
return 0;
}
আউটপুট
The minimum cost is 17
নোট: প্রদত্ত উদাহরণে ম্যাট্রিক্স ৩x৩ কিন্তু ফাংশন কল min_cost(cost, 2, 2) করা হয়েছে (০-বেসড ইনডেক্স)। আউটপুট ১৭ যা ম্যাট্রিক্সের সাথে মেলে না (ছবিতে ৮ দেখা গেছে)। কোডে min_ ফাংশন তিনটি আর্গুমেন্ট নেয় কিন্তু সাধারণত মিনিমাম কস্ট পাথ-এ তিনটি ডায়рекশন (ডায়াগোনাল, আপ, লেফট) বিবেচনা করা হয়। এই কোডে ডায়াগোনাল মুভও আলাউড (allowed)।
