ন্যূনতম খরচের পথের জন্য সি প্রোগ্রাম

এখানে, আমরা সি-তে ন্যূনতম খরচের পথের সমস্যাটি সমাধান করব। ইমপ্লিকেশনটি একটি 2D-ম্যাট্রিক্সে করা হয় যেখানে প্রতিটি কোষের ভ্রমণের খরচ রয়েছে। আমাদের ন্যূনতম ভ্রমণ খরচ সহ বাম উপরের কোণ থেকে নীচের ডান কোণে একটি পথ খুঁজে বের করতে হবে। আপনি একটি প্রদত্ত সেল থেকে শুধুমাত্র নীচের দিকে এবং ডানদিকে নীচের কক্ষগুলি অতিক্রম করতে পারেন৷

এই বিশেষ সমস্যাটি সমাধানের জন্য ডায়নামিক প্রোগ্রামিং পুনরাবৃত্তির চেয়ে অনেক ভালো।

প্রদত্ত খরচ ম্যাট্রিক্স c ost[ ][ ] এবং একটি অবস্থান (m,n) , আমাদের একটি ফাংশন লিখতে হবে যা (0,0) থেকে (m,n) পৌঁছানোর সর্বনিম্ন পথের খরচ প্রদান করে। একটি পথের মোট খরচ (m, n) পৌঁছানোর জন্য সেই পথের সমস্ত খরচের যোগফল। (উৎস এবং গন্তব্য উভয় সহ)।

অনুমান - সমস্ত খরচ ইতিবাচক। ইনপুট ম্যাট্রিক্সে নেতিবাচক খরচ চক্র বিদ্যমান নেই

উদাহরণ

(2,2)

খরচ নিজেই ছবির মধ্যে দেওয়া হয়. পথটি হবে (0, 0) ⇒ (0, 1) ⇒ (1, 2) ⇒ (2, 2)। পথের মান হল আট (1 +2+2+3)।

পন্থা − প্রদত্ত ম্যাট্রিক্সের মতো একই আকারের একটি উত্তর ম্যাট্রিক্স তৈরি করুন।

এই ম্যাট্রিক্সটি নীচে-উপরের পদ্ধতিতে পূরণ করুন।

প্রদত্ত − arrA[ ][ ]। প্রতিটি কক্ষে, আমাদের কাছে 2টি বিকল্প রয়েছে (ডানে বা নীচে যান) এবং যে কোনও i,j সেলের জন্য আমরা ন্যূনতম 2টি নির্বাচন করতে পারি৷

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] = minimum value to achieve (i, j) from (0, 0)

স্পষ্টতই,

minimumCostPath[0][0] = costMatrix[0][0]
minimumCostPath[i][0] = minimumCostPath[i - 1][0] + costMatrix[i][0], for all values of i > zero
minimumCostPath[0][j] = minimumCostPath[0][j - 1] + costMatrix[0][j], for all values of j >zero

এর পরে, আমরা অ্যালগরিদমে যে অনুরূপ সূত্র প্রয়োগ করেছি তা প্রয়োগ করে সর্বনিম্ন খরচের পথ ম্যাট্রিক্স পূরণ করব। যেহেতু পূর্ববর্তী সমস্ত মানগুলি ইতিমধ্যেই ন্যূনতম খরচ পাথ ম্যাট্রিক্সের মধ্যে গণনা করা হয়েছে, তাই আমরা অ্যালগরিদমিক উত্তরের মতো করে এইগুলি পুনরায় গণনা করব না৷

minimumCostPath[i][j] = costMatrix[i][j] +minimum(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)।

উদাহরণ

#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