বাস্তব জীবনের সমস্যা সমাধানে Greedy Technique
Greedy Algorithm (লোভী কৌশল) এমন একটি পদ্ধতি যা সমস্যার প্রতিটি ধাপে লোভী পছন্দ করে এবং সর্বোত্তম সমাধান অর্জন করতে চেষ্টা করে। এটি সর্বদা একটি স্থানীয়ভাবে সর্বোত্তম (locally optimal) সিদ্ধান্ত নেয়, যা শেষ পর্যন্ত একটি গ্লোবালি অপটিমাল (globally optimal) সমাধান হতে পারে বা নাও হতে পারে, তবে সাধারণত Greedy কৌশল সহজ এবং দ্রুত সমাধান দেয়। এই কৌশলটি অনেক বাস্তব জীবনের সমস্যায় কার্যকরী হয়।
Greedy Algorithm এর বৈশিষ্ট্য:
- স্থানীয়ভাবে সর্বোত্তম সিদ্ধান্ত: প্রতিটি পদক্ষেপে সেরা অপশনটি নির্বাচন করা হয়, এবং এটি সমস্যার সমাধান করতে সহায়তা করে।
- নতুন সিদ্ধান্তের উপর নির্ভরশীলতা: একে অপরের উপর ভিত্তি করে সিদ্ধান্তগুলো নেওয়া হয়।
- গ্লোবালি সর্বোত্তম সমাধান নয়: Greedy কৌশলটি সেরা সমাধান দেয় না সব সময়, তবে এটি খুব দ্রুত কাজ করতে সক্ষম।
Greedy Algorithm এর বাস্তব জীবনের সমস্যার উদাহরণ
- ক্যাশ চেঞ্জ সমস্যা (Coin Change Problem)
ক্যাশ চেঞ্জ বা কয়েন পরিবর্তন একটি ক্লাসিক উদাহরণ যেখানে একজন দোকানদারকে কোনো পরিমাণ টাকার পরিবর্তে কয়েন দেওয়া হয়। Greedy কৌশল ব্যবহার করলে আমরা প্রতিটি পদক্ষেপে সর্বোচ্চ মানের কয়েন বেছে নিয়ে পরিমাণ পূর্ণ করতে পারি।
সমস্যা:
ধরা যাক, আপনাকে 63 টাকা ফেরত দিতে হবে এবং কয়েনের মূল্য হচ্ছে 25, 10, 5, এবং 1। Greedy কৌশল অনুযায়ী, আপনি প্রথমে সর্বোচ্চ কয়েন (25) ব্যবহার করবেন, তারপর 10, 5, এবং অবশেষে 1। এটি দ্রুত এবং সঠিক সমাধান প্রদান করে।
Greedy কৌশলের পদক্ষেপ:
- প্রথমে 25 টাকা দিয়ে শুরু করুন: 63 - 25 = 38
- তারপর 25 টাকা আরও একটি কয়েন দিন: 38 - 25 = 13
- তারপর 10 টাকা দিন: 13 - 10 = 3
- তারপর 5 টাকা দিন (যদিও এটি বৃহত্তম নয়, কিন্তু পরবর্তী পর্যায়ে 1 টাকা প্রয়োজন): 3 - 3 = 0
এইভাবে সমাধানটি দ্রুত এবং কার্যকরী হয়। কিন্তু যদি কয়েনের মান ভিন্ন হতো, যেমন 1, 3, 4 এর মতো, তখন Greedy কৌশলটি সর্বোত্তম সমাধান নাও দিতে পারে।
- হাফ-টিমিং এবং কাজের শিডিউলিং (Job Scheduling Problem)
কাজের শিডিউলিং সমস্যা যেখানে কাজগুলির শেষ সময় এবং মুনাফা দেওয়া থাকে, এবং লক্ষ্য থাকে যে আপনি সর্বাধিক মুনাফা অর্জন করতে পারেন।
সমস্যা:
আপনি যদি বিভিন্ন কাজের একটি তালিকা পান, যেখানে প্রতিটি কাজের একটি নির্দিষ্ট সময়সীমা এবং মুনাফা দেওয়া থাকে, তাহলে Greedy কৌশল দ্বারা আপনাকে এমন কাজগুলো বেছে নিতে হবে যা সর্বোচ্চ মুনাফা দেবে এবং কোনো কাজের সাথে সময়ের সংঘর্ষ হবে না।
Greedy কৌশল:
- প্রথমে সেই কাজগুলো বেছে নিন যেগুলোর মুনাফা সবচেয়ে বেশি, এবং সময়কালগুলোতে একে অপরকে ছাপিয়ে না যাওয়ার নিশ্চয়তা দিন।
- এর মাধ্যমে আপনি সর্বোচ্চ মুনাফা পেতে পারবেন।
- হফম্যান কোডিং (Huffman Coding)
হফম্যান কোডিং একটি ডিজিটাল এনকোডিং স্কিমা যা তথ্য সংরক্ষণ করতে ব্যবহৃত হয়। এটি একটি প্রকারের Greedy কৌশল যেখানে দৈর্ঘ্যভিত্তিক কোড দেওয়া হয়, এবং সবার জন্য সেরা টিউনিং করতে ছোট ডেটার জন্য কম বিট এবং বড় ডেটার জন্য বেশি বিট ব্যবহৃত হয়।
Greedy কৌশল:
- প্রতিটি চরিত্রের ফ্রিকোয়েন্সি হিসাব করুন।
- সর্বনিম্ন ফ্রিকোয়েন্সির দুটি চরিত্রের জন্য একটি নতুন নোড তৈরি করুন এবং তাদেরকে একটি নতুন আর্বি ট্রি (Huffman Tree) হিসেবে সমন্বিত করুন।
- এই প্রক্রিয়া চলতে থাকবে যতক্ষণ না আপনি একটি পূর্ণাঙ্গ হাফম্যান ট্রি পেয়ে যাবেন।
এই পদ্ধতিতে সেরা এনকোডিং পাওয়া যায় এবং এটি ডেটা কম্প্রেশনেও ব্যবহৃত হয়।
- প্রধান রাস্তা নির্মাণ (Minimum Spanning Tree - MST)
গ্রাফের মধ্যে সবগুলো নোড সংযুক্ত করতে এমন একটি গাছ (tree) খুঁজে বের করার সমস্যা যা মোট ওয়েট বা ব্যয় কমায়।
সমস্যা:
যেমন ধরুন, আপনি বিভিন্ন শহরকে রাস্তা দিয়ে সংযুক্ত করতে চান, কিন্তু মোট খরচ কম রাখতে চান।
Greedy কৌশল:
- Kruskal's Algorithm এবং Prim's Algorithm দুটোই MST তৈরি করার জন্য Greedy কৌশল ব্যবহার করে।
- Prim’s Algorithm: এটি একে একে গ্রাফের নোডগুলো যোগ করে এবং প্রতিটি পদক্ষেপে সর্বনিম্ন ব্যয়ের রাস্তাটি বেছে নেয়।
- Kruskal’s Algorithm: এটি গ্রাফের সকল এজগুলোকে একে একে বেছে নেয় এবং সর্বনিম্ন ব্যয়ের এজগুলো সংযুক্ত করে।
এইভাবে Greedy কৌশল MST তৈরি করতে সক্ষম হয়।
- ডিক্সট্রা অ্যালগরিদম (Dijkstra’s Algorithm)
এটি একটি গ্রাফের মধ্যে সর্বনিম্ন পথ খুঁজে বের করার জন্য ব্যবহৃত হয়। বিশেষত, Greedy কৌশল ব্যবহার করে ডিক্সট্রা অ্যালগরিদম প্রতিটি নোডের জন্য সর্বনিম্ন ব্যয় (distance) নির্বাচন করে।
সমস্যা:
আপনি যদি একটি গ্রাফে একটি নোড থেকে অন্য নোডে যাওয়ার সর্বনিম্ন পথ খুঁজতে চান, তবে ডিক্সট্রা অ্যালগরিদম ব্যবহার করা হয়।
Greedy কৌশল:
- প্রথমে সর্বনিম্ন দূরত্ব সহ একটি নোড নির্বাচন করা হয়, তারপর প্রতিটি ভিজিটেড নোডের জন্য সেই নোডে যাওয়ার নতুন রাস্তা খুঁজে বের করা হয়।
- এই প্রক্রিয়া পুনরাবৃত্তি করা হয় যতক্ষণ না সব নোডের জন্য সর্বনিম্ন পথ পাওয়া না যায়।
সারসংক্ষেপ
- Greedy Technique একটি সমস্যার প্রতিটি ধাপে সর্বোত্তম সিদ্ধান্ত নেয়, তবে এটি সর্বোত্তম গ্লোবাল সমাধান দেয় না সবসময়।
- বাস্তব জীবনের বিভিন্ন সমস্যায় Greedy কৌশল কার্যকরী হয়, যেমন ক্যাশ চেঞ্জ সমস্যা, টাস্ক শিডিউলিং, হফম্যান কোডিং, গ্রাফের মিনিমাম স্প্যানিং ট্রি ইত্যাদি।
- এটি সাধারণত দ্রুত এবং সহজ সমাধান প্রদান করে, তবে কখনও কখনও এটি গ্লোবাল অপটিমাল সলিউশন নিশ্চিত করে না।
Read more
