গতিশীল প্রোগ্রামিং: বৈশিষ্ট্য, উদাহরণস্বরূপ, সুবিধা, অসুবিধা - প্রযুক্তি - 2025

গতিশীল প্রোগ্রামিং মডেল অ্যালগরিদম সমাধান একটি জটিল সমস্যা হল দ্বারা বিভাজক এটা, subproblems মধ্যে সংরক্ষণ ফলাফল উহার ফলাফল পুনঃগণনা করা এড়ানো।

এই সময়সূচীটি ব্যবহার করা হয় যখন আপনার সমস্যাগুলি থাকে যা একই ধরণের সাব-সমস্যায় বিভক্ত হতে পারে, যাতে তাদের ফলাফলগুলি পুনরায় ব্যবহার করা যায়। বেশিরভাগ ক্ষেত্রে, এই সময়সূচিটি অপ্টিমাইজেশনের জন্য ব্যবহৃত হয়।

ডায়নামিক প্রোগ্রামিং। ফিবোনাচি সিকোয়েন্সে সাব-প্রবলেমস সুপারমোজড। উত্স: উইকিমিডিয়া কমন্স, এন: ব্যবহারকারী: ডকোয়াটজি, ব্যবহারকারী দ্বারা সনাক্ত: স্ট্যানার্ড / পাবলিক ডোমেন

উপলব্ধ সাবপ্রব্লেম সমাধান করার আগে, গতিশীল অ্যালগরিদম পূর্ববর্তী সমাধান হওয়া সাব-সমস্যাগুলির ফলাফলগুলি পরীক্ষা করার চেষ্টা করবে। সাব-প্রবলেমগুলির সমাধানগুলি সর্বোত্তম সমাধান অর্জনের জন্য একত্রিত হয়।

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

এটি মেমরির সময় ঠিক করার জন্য একটি দুর্দান্ত ধারণা, যেখানে অতিরিক্ত স্থান ব্যবহার করা সমাধান খুঁজে পেতে প্রয়োজনীয় সময়ের উন্নতি করতে পারে।

গতিশীল প্রোগ্রামিং এর বৈশিষ্ট্যগুলি

ডায়নামিক প্রোগ্রামিং প্রয়োগ করার আগে আপনার অবশ্যই যে সমস্যাটি তৈরি করতে হবে তা হ'ল:

অনুকূল কাঠামো

এই বৈশিষ্ট্যটি প্রকাশ করে যে একটি অপ্টিমাইজেশান সমস্যাটি অন্তর্ভুক্ত গৌণ সমস্যাগুলির সর্বোত্তম সমাধানগুলির সংমিশ্রণের মাধ্যমে সমাধান করা যেতে পারে। এই সর্বোত্তম কাঠামো পুনরাবৃত্তি দ্বারা বর্ণনা করা হয়।

উদাহরণস্বরূপ, একটি গ্রাফের মধ্যে একটি সর্বোত্তম কাঠামোটি সংক্ষিপ্ত পথে আরে উপস্থাপিত হবে যা একটি শীর্ষবিন্দু থেকে একটি শীর্ষস্থানীয় টিতে যাবে:

এটি হ'ল, এই সংক্ষিপ্ততম পথে আর কোনও মধ্যবর্তী ভার্টেক্স আমি নেওয়া যেতে পারে। আর যদি সত্যই সংক্ষিপ্ততম রুট হয়, তবে এটি সাব্রোয়েট আর 1 (এস থেকে আই) এবং আর 2 (আই থেকে টি) এ বিভক্ত হতে পারে, যাতে এগুলি উল্লিখিত উলম্বগুলির মধ্যে সংক্ষিপ্ততম রুটগুলি ঘুরে যায়।

অতএব, সবচেয়ে সংক্ষিপ্ততম পথগুলি সন্ধান করার জন্য সমাধানটি সহজেই পুনরাবৃত্তভাবে তৈরি করা যেতে পারে, যা ফ্লয়েড-ওয়ারশাল অ্যালগরিদম এটি করে।

ওভারল্যাপিং সাব-সমস্যাগুলি

সাবপ্রব্লেম স্পেসটি অবশ্যই ছোট হতে হবে। এটি হ'ল যে কোনও পুনরাবৃত্তির অ্যালগরিদম যা সমস্যার সমাধান করে তার জন্য নতুন সাবপ্রব্লেম উত্‍পাদন না করে বারবার একই সাব-সমস্যাগুলি সমাধান করতে হবে।

উদাহরণস্বরূপ, ফিবোনাচি সিরিজ উত্পন্ন করার জন্য, এই পুনরাবৃত্তিমূলক সূত্রটি বিবেচনা করা যেতে পারে: Fn = F (n - 1) + F (n - 2), F1 = F2 = 1. কে একটি বেস কেস হিসাবে গ্রহণ করে তারপরে আমাদের কাছে থাকবে: F33 = F32 + F31, এবং F32 = F31 + F30।

আপনি দেখতে পাচ্ছেন, এফ 31 এফ 33 এবং এফ 32 উভয়ের পুনরাবৃত্ত সাবট্রির মধ্যে সমাধান করা হচ্ছে। যদিও সাব-প্রবলেমগুলির মোট সংখ্যা সত্যিই ছোট, আপনি যদি এ জাতীয় পুনরাবৃত্ত সমাধানটি গ্রহণ করেন তবে আপনি একই সমস্যা বার বার সমাধান করবেন solving

এটি ডায়নামিক প্রোগ্রামিংয়ের দ্বারা বিবেচনা করা হয়, সুতরাং এটি প্রতিটি সাবপ্রব্লেম কেবল একবারে সমাধান করে। এটি দুটি উপায়ে সম্পন্ন করা যেতে পারে:

উপরে নিচে অভিগমন

যদি কোনও সমস্যার সমাধানটি তার সাব-প্রবলেমগুলির সমাধানটি ব্যবহার করে পুনরাবৃত্তভাবে তৈরি করা যায় এবং যদি এই সাব-প্রবলেমগুলি ওভারল্যাপ হয় তবে সাব-প্রবলেমগুলির সমাধানগুলি সহজেই মুখস্থ বা একটি সারণীতে সংরক্ষণ করা যেতে পারে।

প্রতিবার নতুন সাব-প্রব্লেম সলিউশন অনুসন্ধান করা হলে, টেবিলটি আগে সমাধান করা হয়েছে কিনা তা পরীক্ষা করে দেখা হবে। যদি কোনও সমাধান সংরক্ষণ করা হয়, তবে এটি আবার গণনার পরিবর্তে ব্যবহৃত হবে। অন্যথায়, সাবপ্রব্লেমটি সমাধান করা হবে, সারণীতে সমাধানটি সংরক্ষণ করে।

নীচে আপ পদ্ধতির

সমস্যার সমাধানটি তার সাবপ্রব্লেমগুলির ক্ষেত্রে পুনরাবৃত্তভাবে সূত্রিত হওয়ার পরে, anর্ধ্বমুখী পদ্ধতিতে সমস্যাটি সংশোধন করার চেষ্টা করা সম্ভব: প্রথমত, আমরা সাব-প্রবলেমগুলি সমাধান করার চেষ্টা করব এবং বৃহত্তর সাব-প্রবলেমগুলির সমাধানে পৌঁছতে তাদের সমাধানগুলি ব্যবহার করব।

এটি সাধারণত টেবিল আকারেও করা হয়, পুনরাবৃত্তভাবে ছোট ছোট সাব-প্রবলেমের সমাধান ব্যবহার করে বৃহত্তর এবং বৃহত্তর সাব-প্রবলেমগুলির সমাধান উত্পন্ন করে। উদাহরণস্বরূপ, যদি F31 এবং F30 এর মানগুলি ইতিমধ্যে জানা থাকে তবে F32 এর মানটি সরাসরি গণনা করা যায়।

অন্যান্য কৌশলগুলির সাথে তুলনা করা

গতিশীল প্রোগ্রামিংয়ের মাধ্যমে সমস্যার সমাধান করা যায় এমন একটি সমস্যার উল্লেখযোগ্য বৈশিষ্ট্য হ'ল এতে সাব-প্রবলেমগুলি ওভারল্যাপিং হওয়া উচিত। এটিই ডায়নামিক প্রোগ্রামিংকে বিভাজন এবং বিজয়ী কৌশল থেকে পৃথক করে, যেখানে সাধারণ মানগুলি সংরক্ষণ করার প্রয়োজন হয় না।

এটি পুনরাবৃত্তির অনুরূপ, যেহেতু বেস কেসগুলি গণনা করার সময়, চূড়ান্ত মান inductively নির্ধারণ করা যেতে পারে। এই তল-আপ পদ্ধতিটি কার্যকর হয় যখন কোনও নতুন মান কেবল পূর্ববর্তী গণনা করা মানগুলিতে নির্ভর করে।

উদাহরণ

সর্বনিম্ন পদক্ষেপ 1 পৌঁছানোর

যেকোন ধনাত্মক পূর্ণসংখ্যার জন্য "ই" নিম্নলিখিত তিনটি ধাপের কোনও সম্পাদন করা যেতে পারে।

- সংখ্যা থেকে 1 বিয়োগ করুন। (e = e-1)।

- যদি এটি 2 দ্বারা বিভাজ্য হয় তবে এটি 2 দিয়ে বিভক্ত (যদি e% 2 == 0 হয়, তবে ই = ই / 2)।

- যদি এটি 3 দ্বারা বিভাজ্য হয় তবে এটি 3 দ্বারা ভাগ করা হয় (যদি ই% 3 == 0 হয়, তবে ই = ই / 3)।

উপরের পদক্ষেপের উপর ভিত্তি করে, এই পদক্ষেপগুলির সর্বনিম্ন সংখ্যাটি 1 এ আনতে হবে example উদাহরণস্বরূপ:

- যদি ই = 1, ফলাফল: 0।

- যদি ই = 4, ফলাফল: 2 (4/2 = 2/2 = 1)।

- যখন ই = 7, ফলাফল: 3 (7-1 = 6/3 = 2/2 = 1)।

ফোকাস

কেউ সর্বদা এমন পদক্ষেপটি বেছে নেওয়ার কথা ভাবতে পারে যা যথাসম্ভব কম করে তোলে এবং এটি 1 অবধি পৌঁছানো অবধি এভাবে চালিয়ে যাবেন তবে তবে দেখা যায় যে এই কৌশলটি এখানে কাজ করে না।

উদাহরণস্বরূপ, e = 10 হলে পদক্ষেপগুলি হবে: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 পদক্ষেপ)। তবে সর্বোত্তম ফর্মটি হল: 10-1 = 9/3 = 3/3 = 1 (3 পদক্ষেপ)। সুতরাং, প্রাপ্ত প্রতিটি মানের জন্য যে সমস্ত সম্ভাব্য পদক্ষেপগুলি করা যেতে পারে তার চেষ্টা করা উচিত, এই সম্ভাবনার সর্বনিম্ন সংখ্যা বেছে নেওয়া choosing

এটি সমস্ত পুনরাবৃত্তি দিয়ে শুরু হয়: F (e) = 1 + মিনিট {F (e-1), F (e / 2), F (e / 3) / যদি e> 1, বেস কেস হিসাবে গ্রহণ করে: F (1) = 0. পুনরাবৃত্তি সমীকরণ থাকার পরে, আপনি পুনরাবৃত্তি কোড করতে শুরু করতে পারেন।

তবে এটি দেখা যায় যে এটির ওভারল্যাপিং সাব-সমস্যা রয়েছে। তদ্ব্যতীত, প্রদত্ত ইনপুটটির সর্বোত্তম সমাধানটি তার সাব-প্রবলেমের সর্বোত্তম সমাধানের উপর নির্ভর করে।

মুখস্তকরণের মতো, যেখানে সাব-প্রব্লেমগুলি সমাধান করা সমাধানগুলি পরবর্তী ব্যবহারের জন্য সঞ্চিত হয়। বা ডায়নামিক প্রোগ্রামিংয়ের মতো আপনি নীচের দিকে শুরু করে প্রদত্ত ই-তে আপনার পথে কাজ করছেন। তারপরে উভয় কোড:

মুখস্ত

ডায়নামিক ডাউন-আপ প্রোগ্রামিং

সুবিধা

ডায়নামিক প্রোগ্রামিং ব্যবহারের অন্যতম প্রধান সুবিধা হ'ল এটি প্রক্রিয়াজাতকরণের গতি বাড়ায়, যেহেতু পূর্বে গণনা করা তথ্যগুলি ব্যবহার করা হয়। এটি একটি পুনরাবৃত্ত প্রোগ্রামিং কৌশল হিসাবে এটি প্রোগ্রামে কোডের লাইনকে হ্রাস করে।

ভেরিয়াস অ্যালগরিদম বনাম গতিশীল প্রোগ্রামিং

লোভী অ্যালগরিদমগুলি গতিশীল প্রোগ্রামিংয়ের অনুরূপ যে তারা উভয়ই অপ্টিমাইজেশনের সরঞ্জাম। তবে লোভী অ্যালগরিদম প্রতিটি স্থানীয় পদক্ষেপে একটি অনুকূল সমাধান সন্ধান করে। এটি একটি বৈশ্বিক সর্বোত্তম খুঁজে পাওয়ার প্রত্যাশায় একটি লোভী পছন্দ অনুসন্ধান করে।

অতএব, লোভী অ্যালগরিদমগুলি এমন একটি ধারণা তৈরি করতে পারে যা সেই সময়ে অনুকূল দেখায় তবে ভবিষ্যতে ব্যয়বহুল হয়ে যায় এবং এটি কোনও বৈশ্বিক অনুকূলের গ্যারান্টি দেয় না।

অন্যদিকে, ডায়নামিক প্রোগ্রামিং সাব-প্রবলেমগুলির জন্য সর্বোত্তম সমাধানটি সন্ধান করে এবং তারপরে প্রকৃতপক্ষে সর্বোত্তম সমাধানের সন্ধানের জন্য sub সাব-সমস্যাগুলির ফলাফলগুলিকে একত্রিত করে একটি জ্ঞাত পছন্দ করে।

অসুবিধেও

- প্রতিটি সাবপ্রব্লেমের গণিত ফলাফল সংরক্ষণের জন্য প্রচুর মেমরির প্রয়োজন হয়, গ্যারান্টি দিতে সক্ষম না হয়ে যে সঞ্চিত মানটি ব্যবহার করা হবে কি না।

- অনেক সময়, নির্বাহের সময় নিম্নলিখিত সাব-সমস্যায় কখনও ব্যবহার না করে আউটপুট মান সংরক্ষণ করা হয়। এটি অপ্রয়োজনীয় স্মৃতি ব্যবহারের দিকে নিয়ে যায়।

- ডায়নামিক প্রোগ্রামিংয়ে ফাংশনগুলিকে পুনরাবৃত্তভাবে বলা হয়। এটি স্ট্যাকের স্মৃতি ক্রমাগত বাড়িয়ে তোলে।

পুনরাবৃত্তি বনাম ডায়নামিক প্রোগ্রামিং

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

আপনি যদি প্রোগ্রামটি দ্রুত চালিত করতে চান এবং মেমরির কোনও বিধিনিষেধ না রয়েছে, ডায়নামিক প্রোগ্রামিং ব্যবহার করা ভাল।

অ্যাপ্লিকেশন

ডায়নামিক প্রোগ্রামিং সমস্যাগুলি সমাধানের একটি কার্যকর পদ্ধতি যা অন্যথায় যুক্তিসঙ্গত সময়ে সমাধান করা অত্যন্ত কঠিন বলে মনে হয়।

গতিশীল প্রোগ্রামিং দৃষ্টান্তের উপর ভিত্তি করে অ্যালগরিদমগুলি বিজ্ঞানের বিভিন্ন ক্ষেত্রে ব্যবহার করা হয়, কৃত্রিম বুদ্ধিমত্তার অনেক উদাহরণ সহ পরিকল্পনার সমস্যা সমাধান থেকে বক্তৃতা স্বীকৃতি পর্যন্ত।

গতিশীল প্রোগ্রামিংয়ের ভিত্তিতে অ্যালগরিদম

ডায়নামিক প্রোগ্রামিং বেশ কার্যকর এবং বিস্তৃত সমস্যার জন্য খুব ভাল কাজ করে। অনেক অ্যালগরিদম লোভী অ্যালগরিদম অ্যাপ্লিকেশন হিসাবে দেখা যেতে পারে, যেমন:

- ফিবোনাচি নম্বর সিরিজ।

- হ্যানয়ের টাওয়ারস

- ফ্লয়েড-ওয়ারশালের মধ্য দিয়ে সমস্ত জোড় সংক্ষিপ্ত রুট।

- ব্যাকপ্যাক সমস্যা।

- প্রকল্পের সময়সূচী।

- ডিজকস্ট্রার মধ্য দিয়ে সবচেয়ে সংক্ষিপ্ততম পথ।

- ফ্লাইট নিয়ন্ত্রণ এবং রোবোটিক্স নিয়ন্ত্রণ।

- গাণিতিক অপ্টিমাইজেশান সমস্যা।

- টাইমশেয়ার: সিপিইউ ব্যবহার সর্বাধিকীকরণের জন্য কাজের সময় নির্ধারণ করুন।

ফিবোনাচি নম্বর সিরিজ

ফিবোনাচি সংখ্যাগুলি নিম্নলিখিত ক্রমটিতে পাওয়া সংখ্যা: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ইত্যাদি etc.

গাণিতিক পরিভাষায়, ফিবোনাচি সংখ্যার ক্রম Fn পুনরাবৃত্ত সূত্র দ্বারা সংজ্ঞায়িত করা হয়: F (n) = F (n -1) + F (n -2), যেখানে F (0) = 0 এবং F (1) = 1।

উপরে নিচে অভিগমন

এই উদাহরণে, সমস্ত প্রাথমিক মান সহ একটি অনুসন্ধান অ্যারে -1 দিয়ে আরম্ভ করা হয়। যখনই কোনও সাব-প্রবলেমের সমাধানের প্রয়োজন হবে, এই অনুসন্ধানের ম্যাট্রিক্সটি প্রথমে অনুসন্ধান করা হবে।

যদি গণনা করা মান থাকে তবে সেই মানটি ফেরত আসবে। অন্যথায়, ফলাফলটি অনুসন্ধানের অ্যারেতে সংরক্ষণ করার জন্য গণনা করা হবে যাতে এটি পরে পুনরায় ব্যবহার করা যায়।

নীচে আপ পদ্ধতির

এই ক্ষেত্রে, একই ফিবোনাচি সিরিজের জন্য, চ (0) প্রথমে গণনা করা হয়, তারপরে চ (1), চ (2), চ (3) ইত্যাদি on সুতরাং, সাবপ্রব্লেমগুলির সমাধানগুলি নীচ থেকে উপরে তৈরি করা হচ্ছে।

তথ্যসূত্র

1. ভিণীত চৌধুরী (2020)। ডায়নামিক প্রোগ্রামিংয়ের পরিচিতি। বিকাশকারী ইনসাইডার from
2. অ্যালেক্স অ্যালাইন (2020)। সি ++ এ ডায়নামিক প্রোগ্রামিং। সি প্রোগ্রামিং। থেকে নেওয়া: cprogramming.com।
3. একাডেমির পরে (2020)। ডায়নামিক প্রোগ্রামিং এর আইডিয়া। থেকে নেওয়া: afteracademy.com।
4. অনিরুদ্ধ চৌধুরী চৌধুরী (2019)। গতিশীল প্রোগ্রামিং এবং পুনরাবৃত্তি - পার্থক্য, উদাহরণ সহ সুবিধা। সিএসই স্ট্যাক থেকে নেওয়া: csestack.org।
5. কোড শেফ (2020)। ডায়নামিক প্রোগ্রামিংয়ের জন্য টিউটোরিয়াল। থেকে নেওয়া: codechef.com।
6. প্রোগ্রামিজ (2020)। ডায়নামিক প্রোগ্রামিং। থেকে নেওয়া হয়েছে: programiz.com।