কোন সমস্যা সমাধানে Top-down এবং bottom-up ডিজাইন কি? এদের মধ্যে পার্থক্য কি? উদাহরণ সহকারে জানতে চাই।

asked 14 Sep '16, 16:54

sksuranjit's gravatar image

sksuranjit
756

edited 02 Mar '17, 04:13

menon's gravatar image

menon
4.7k334

1

আপনি কিসের ক্ষেত্রে Top Down ও Bottom Up বোঝাচ্ছেন সেটা সেটা নির্দিষ্ট করলে উত্তর দিতে সুবিধা হত । আপনি কি কোন একটা সমস্যার top-donwn, bottom-up সমধানের কথা বলছেন ?

ধন্যবাদ :)

(15 Sep '16, 08:24) menon
1

জ্বী ভাই কোন একটা সমস্যার। যেমনঃ ধরেন একটা বড় প্রোগ্রামিং প্রবলেম সলভিংয়ের ক্ষেত্রে কিভাবে Top-down বা Bottom-up কৌশল প্রয়োগ করতে পারি। আর এই দুই কৌশল ই বা কি? এগুলা জানতে চাই আর কি!

আপনাকেও ধন্যবাদ রেসপন্সের জন্য :)

(15 Sep '16, 09:48) sksuranjit

ধরি, আমরা N তম Fibonacci সংখ্যা বের করব অর্থাৎ ৫ ইনপুট দেয় তবে আমাদের প্রোগ্রাম ৫ তম Fibonacci সংখ্যা আউটপুট দেখাবে । Fibonacci ধারা, 1, 2, 3, 5, 8, 13, 21, . . . n অর্থাৎ প্রতিটি সংখ্যা তার আগের দুইটি সংখ্যার যোগফল । এই সমস্যা টা আমরা প্রথমে Top-Down পরে Bottom-Up স্টাইলে সমাধান করার চেষ্টা করব ।

Top-Down সমাধান :

int fib(int n)
{
   if ( n <= 1 )
      return n;
   return fib(n-1) + fib(n-2);
}

N = 5 এর জন্য ফাংশন টি কিভাবে কাজ করছে সেটা বুঝতে সমস্যা হলে এই ছবি টা দেখন ।

fib

আমরা n তম Fibonacci সংখ্যা বের করার জন্য উপরে আমারা যেভাবে সমাধান করলাম সেটা কে বলা হয় Top-Down স্টাইল ।

Bottom Up সমাধান :

int fib(int n)
{
  int f[n+1];
  int i;
  f[0] = 0;   f[1] = 1; 
  for (i = 2; i <= n; i++)
      f[i] = f[i-1] + f[i-2];

  return f[n];
}

N তম Fibonacci সংখ্যা বের করার জন্য উপরের সমাধান কে বলব Bottom-Up স্টাইল।

এখন আপনি প্রশ্ন করতে পারেন কেন আমরা আমাদের প্রথম সমাধান কে Top-Down ও পরের সমাধান কে Bottom-Up স্টাইল বলছি । এইটা বোঝার জন্য আপনি লক্ষ করুন আমাদের প্রথম সমাধান করার স্টাইল ছিল আমাদের যদি N একটা ইনপুট থাকে তবে আমরা N থেকেই আমাদের সমাধান শুরু করছি এবং N কে আমারা ছোট ছোট অংশে ভাগ করে ( Sub Problem ) সেগুলো সমাধান করছি ।

অর্থাৎ আমারা আমাদের সমস্যা সমাধান করার জন্য সমস্যার Top থেকে শুরু করে Down এর দিয়ে আসছি এবং সব শেষে সমাধান পেয়ে যাচ্ছি ।

এখন আমাদের পরের সমাধান টা লক্ষ করেন । সেখান আমরা কি করেছি ? N সংখ্যার জন্য আমরা একদম শুরু থেকে ( ১ + ২ = ৩, ২ + ৩ + ৫, ৩ + ৫ = ৮, ... N ) শুরু করে N এ যাচ্ছি এবং পরে N এর মান রিটার্ন করছি । অর্থাৎ আমরা Bottom থেকে শুরু করে Up এর দিকে যাচ্ছি । এই জন্য এই সমাধান কে আমরা বলছি Bottom-Up সমাধান ।

অর্থাৎ Top-Down হল শেষ থেকে শুরুর দিকে এসে একটা সমস্যার সমাধান করা আর Bottom-Up হল শুরু থেকে শেষের দিকে গিয়ে একটা সমস্যার সমাধান করা । নাম টাও কিন্তু সেভাবেই দেয়া হয়েছে Top-Down, Bottom-Up :D

এখন প্রশ্ন আসতে পারে এই দুইটা মধ্যে কোনটা ভাল ?

এটা নির্ভর করবে আপনার সমস্যা টা কি ধরনের । উপরে আমারা যে সমস্যা সমাধান করলাম সেটা ক্ষেত্রে Bottom-Up সমাধান ই ভাল । কারণ এটার ক্ষেত্রে সময় কম লাগে । আর Top-Down এর ক্ষেত্রে আপনি দেখতে পাচ্ছে একই ফাংশন একাধিক বার কল হচ্ছে । তাই এটা সময় বেশি লাগবে । তবে এই সমস্যা টা DP এর মাধ্যমে সময় আরও কমান যায় ।

ধন্যবাদ :D

permanent link

answered 16 Sep '16, 13:19

menon's gravatar image

menon
4.7k334

edited 21 Sep '16, 18:17

একদম সোজা ভাষায় বলতে গেলেঃ কোন সমস্যার সমাধান কে যদি ভেঙে একটি বাইনারি ট্রি-তে পরিণত করা হয় তাহলেঃ

  1. Top-down : উপরের নড গুলো সমাধান করতে করতে বাইনারি ট্রি-এর নিচের দিকে যাওয়া।
  2. bottom-up : বাইনারি ট্রি-এর একদম শেষ লেভেল থেকে সর্বনিম্ন নোড সমাধান করতে করতে উপরের দিকে যাওয়া।
permanent link

answered 23 Oct '16, 22:39

almazi's gravatar image

almazi
212

edited 16 Oct '17, 15:47

menon's gravatar image

menon
4.7k334

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Question tags:

×7
×6
×4
×1
×1

question asked: 14 Sep '16, 16:54

question was seen: 1,021 times

last updated: 16 Oct '17, 15:47