প্রোগ্রামারদের জানা আবশ্যক দশটি মৌলিক ব্যবহারিক অ্যালগরিদম এবং তাদের ব্যাখ্যা

লেখক:ছোট্ট স্বপ্ন, তৈরিঃ ২০১৬-১২-০৯ ১১ঃ৩৭ঃ৩৬, আপডেটঃ ২০১৬-১২-০৯ ১১ঃ৩৯ঃ২০

প্রোগ্রামারদের জানা আবশ্যক দশটি মৌলিক ব্যবহারিক অ্যালগরিদম এবং তাদের ব্যাখ্যা

  • অ্যালগরিদম ১ঃ দ্রুত সাজানোর অ্যালগরিদম

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

    দ্রুত বাছাই একটি তালিকাকে দুটি উপ-তালিকায় বিভক্ত করার জন্য বিভক্ত এবং বিজয় কৌশল ব্যবহার করে।

    অ্যালগরিদম ধাপঃ

    • ১, সংখ্যা কলাম থেকে একটি উপাদান বাছাই করুন, যা পিভট নামে পরিচিত।

    • ২, পুনরায় সাজানো সংখ্যা কলাম, সমস্ত উপাদান যা বেঞ্চমার্কের চেয়ে ছোট তা বেঞ্চমার্কের সামনে এবং সমস্ত উপাদান যা বেঞ্চমার্কের চেয়ে বড় তা বেঞ্চমার্কের পিছনে রাখা হয় (একই সংখ্যা যে কোনও দিকে যেতে পারে) । এই পার্টিশনটি প্রস্থান করার পরে, বেঞ্চমার্কটি সংখ্যা কলামের মাঝখানে অবস্থিত। এটিকে পার্টিশন অপারেশন বলা হয়।

    • ৩, পুনরাবৃত্ত (recursive) যা বেঞ্চমার্ক এলিমেন্টের চেয়ে ছোট এবং বেঞ্চমার্ক এলিমেন্টের চেয়ে বড় সাব-এলিমেন্টের সারিবদ্ধকরণ করে।

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

  • অ্যালগরিদম ২ঃ স্ট্যাক সোর্টিং অ্যালগরিদম

    Heapsort হল এমন একটি সাজানোর অ্যালগরিদম যা এই ধরনের ডেটা স্ট্রাকচার ব্যবহার করে ডিজাইন করা হয়েছে। একটি স্ট্যাক একটি প্রায় সম্পূর্ণ দ্বিপদী গাছের কাঠামো, এবং একই সাথে স্ট্যাকের বৈশিষ্ট্য পূরণ করেঃ অর্থাৎ একটি সাব-নোটের কী মান বা সূচক সর্বদা তার পিতা-নোটের চেয়ে ছোট বা বড় হয়।

    স্ট্যাক সোর্টিং এর গড় সময় জটিলতা O ((nlogn) ।

    অ্যালগরিদম ধাপঃ

    • ১, H [০...n-1] এর একটি স্ট্যাক তৈরি করুন

    • ২, স্ট্যাকের শিরোনাম (সর্বোচ্চ) এবং স্ট্যাকের শেষ পরিবর্তন করুন

    • ৩, স্ট্যাকের আকার ১ দ্বারা ছোট করুন এবং shift_down ((০) কল করুন, যার উদ্দেশ্য হল নতুন অ্যারে শীর্ষের ডেটা সংশোধন করা।

    • ৪, ধাপ ২ পুনরাবৃত্তি করুন, যতক্ষণ না ময়দা ১ হয়।

  • অ্যালগরিদম ৩ঃ সমন্বয় এবং বাছাই

    মার্জসোর্ট (Mergesort) হল একটি কার্যকর শ্রেণিবদ্ধকরণ অ্যালগরিদম যা মার্জসোর্ট অপারেশনের উপর ভিত্তি করে তৈরি। এই অ্যালগরিদমটি বিভাজন এবং বিজয় পদ্ধতির একটি খুব সাধারণ প্রয়োগ।

    অ্যালগরিদম ধাপঃ

    • ১, অ্যাপ্লিকেশন স্পেস, যার আকার দুইটি সাজানো সারি যোগফলের সমান, যা একত্রিত সারি সংরক্ষণের জন্য ব্যবহৃত হয়

    • ২, দুটি পয়েন্টার সেট করুন, যার শুরুতে দুটি সোর্টিং সারি রয়েছে

    • ৩। দুটি পয়েন্টারের পয়েন্টারগুলি তুলনা করুন, একটি তুলনামূলকভাবে ছোট উপাদান নির্বাচন করুন, এটিকে সংমিশ্রণ স্পেসে রাখুন এবং পয়েন্টারটিকে পরবর্তী অবস্থানে সরান

    • ৪, ধাপ ৩ পুনরাবৃত্তি করুন যতক্ষণ না কোন পয়েন্টার ক্রম শেষে আসে

    • ৫, অন্য ক্রমের বাকি সমস্ত উপাদানকে সরাসরি সংযুক্ত ক্রমের শেষে অনুলিপি করুন

  • অ্যালগরিদম চারঃ বাইনারি অনুসন্ধান অ্যালগরিদম

    দ্বিপদী অনুসন্ধান একটি সার্চ অ্যালগরিদম যা একটি সুনির্দিষ্ট উপাদানকে একটি সুশৃঙ্খল অ্যারেতে অনুসন্ধান করে। অনুসন্ধান প্রক্রিয়াটি অ্যারের মধ্যবর্তী উপাদান থেকে শুরু হয়, যদি মধ্যবর্তী উপাদানটি সঠিকভাবে সন্ধান করা হয় তবে অনুসন্ধান প্রক্রিয়াটি শেষ হয়; যদি কোনও নির্দিষ্ট উপাদানটি মধ্যবর্তী উপাদানটির চেয়ে বড় বা ছোট হয় তবে অনুসন্ধানটি অর্ধেকের মধ্যে অনুসন্ধান করা হয় এবং মধ্যবর্তী উপাদানটি থেকে শুরু করে একইভাবে তুলনা করা হয়। যদি কোনও ধাপে অ্যারেটি খালি থাকে তবে এটি পাওয়া যায় না। এই অনুসন্ধান অ্যালগরিদমটি প্রতিবার তুলনা করে অনুসন্ধানের পরিসীমা হ্রাস করে। অর্ধেক অনুসন্ধান প্রতি অর্ধেক অনুসন্ধান অঞ্চলকে অর্ধেক করে দেয়, সময় জটিলতা হ'ল ((ওলগ) ।

  • অ্যালগরিদম ৫: বিএফপিআরটি (রেখাযুক্ত অনুসন্ধান অ্যালগরিদম)

    বিএফপিআরটি অ্যালগরিদমটি একটি ক্লাসিক সমস্যার সমাধান করে, যা n টি উপাদানগুলির একটি ক্রম থেকে k বড় (k ছোট) উপাদানটি বেছে নেয়, এবং চতুর বিশ্লেষণের মাধ্যমে, বিএফপিআরটি সবচেয়ে খারাপ পরিস্থিতিতে রৈখিক সময় জটিলতা বজায় রাখার গ্যারান্টি দেয়। এই অ্যালগরিদমের ধারণাটি দ্রুত বাছাইয়ের ধারণার অনুরূপ, অবশ্যই, পাঁচটি লেখক অ্যালগরিদমটি সবচেয়ে খারাপ পরিস্থিতিতেও o (n) সময় জটিলতা অর্জন করতে সক্ষম হওয়ার জন্য সূক্ষ্মভাবে পরিচালনা করেছেন।

    অ্যালগরিদম ধাপঃ

    • ১, n টি উপাদানকে প্রতি ৫ টিতে একটি করে n/5 (উপরের সীমানা) গ্রুপে বিভক্ত করা।

    • ২, প্রতিটি গোষ্ঠীর মধ্যপন্থী সংখ্যা বের করুন, যেকোনো সাজানোর পদ্ধতি, যেমন সাজানো সন্নিবেশ করা।

    • ৩, প্রত্যাবর্তনশীল কল নির্বাচন অ্যালগরিদম পূর্ববর্তী ধাপে সমস্ত মধ্যপন্থী সংখ্যাগুলির মধ্যপন্থী সংখ্যা খুঁজে বের করে, যা x হিসাবে সেট করা হয়, যা মধ্যপন্থী সংখ্যাগুলির মধ্যে ছোট একটি বেছে নেওয়ার জন্য সেট করা হয়।

    • ৪, x দিয়ে একটি অ্যারে ভাগ করা হয়, যেখানে x এর চেয়ে ছোট এবং x এর চেয়ে বড় সংখ্যা k হয়।

    • ৫, যদি i==k হয়, তাহলে x ফেরত দেয়; যদি ik হয়, তাহলে x এর চেয়ে বড় একটি উপাদানের মধ্যে i-k-মিনিয়র উপাদানটি খুঁজে বের করতে প্রত্যাবর্তন করে।

      সমাপ্তি শর্তঃ n=1 হলে, i ছোট্ট উপাদানটি ফিরে আসে।

  • অ্যালগরিদম ৬ঃ ডিএফএস (গভীরতা অগ্রাধিকার অনুসন্ধান)

    গভীর-প্রথম অনুসন্ধান (ইংরেজিঃ Depth-First-Search) হল একটি অনুসন্ধান অ্যালগরিদম, যা গাছের গভীরতাগুলির সাথে গাছের গভীরতাগুলিকে অতিক্রম করে, গাছের শাখাগুলিকে যতটা সম্ভব গভীর করে তোলে। যখন v-এর সমস্ত দিক অনুসন্ধান করা হয়, তখন অনুসন্ধানটি v-এর দিকের শুরুতে ফিরে আসে। এই প্রক্রিয়াটি সমস্ত পাওয়া যায় এমন নোডগুলি পর্যন্ত চলতে থাকে। যদি কোনও পাওয়া নোড না থাকে তবে এটির মধ্যে একটিকে উত্স নোড হিসাবে বেছে নেওয়া হয় এবং সমস্ত নোডগুলি অ্যাক্সেস করা পর্যন্ত পুরো প্রক্রিয়াটি পুনরাবৃত্তি করা হয়। DFS অন্ধ অনুসন্ধানের অন্তর্ভুক্ত।

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

    আলগোরিদিমের ধাপগুলি গভীরতার সাথে অগ্রাধিকার দিনঃ

    • ১, শীর্ষ v-এ অ্যাক্সেস;

    • ২। v এর অ্যাক্সেসযোগ্য পার্শ্ববর্তী সংযোগস্থল থেকে শুরু করে, গ্রাফের গভীরতা অগ্রাধিকার ভ্রমণ করুন; গ্রাফের শীর্ষগুলি এবং v এর সাথে পথের সম্মিলন পর্যন্ত অ্যাক্সেস করুন;

    • ৩. যদি এই সময়ে গ্রাফের কোন শীর্ষটি অ্যাক্সেস করা না থাকে, তাহলে একটি অ্যাক্সেস করা শীর্ষ থেকে শুরু করে আবার গভীরতা অগ্রাধিকার ভ্রমণ করুন, যতক্ষণ না গ্রাফের সমস্ত শীর্ষগুলি অ্যাক্সেস করা হয়।

      উপরের বর্ণনাটি কিছুটা বিমূর্ত হতে পারে, উদাহরণস্বরূপঃ

      ডিএফএস অ্যাক্সেস গ্রাফের কোন একটিতে একটি শীর্ষ v দিয়ে শুরু করে, v থেকে প্রস্থান করে, এর যে কোন পার্শ্ববর্তী শীর্ষ w1 এ অ্যাক্সেস করে; তারপর w1 থেকে প্রস্থান করে, w2 এর সাথে সংযুক্ত শীর্ষ w1 এ অ্যাক্সেস করে, কিন্তু এখনও অ্যাক্সেস করা হয়নি; তারপর আবার w2 থেকে প্রস্থান করে, অনুরূপ অ্যাক্সেস করে,... এবং এভাবেই চলতে থাকে, যতক্ষণ না সমস্ত পার্শ্ববর্তী শীর্ষগুলি অ্যাক্সেস করা শীর্ষ u এ পৌঁছায়।

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

  • অ্যালগরিদম ৭: বিএফএস (বিস্তার অগ্রাধিকার অনুসন্ধান)

    ব্রেডথ-ফার্স্ট-সার্চ (ইংরেজিঃ Breadth-First-Search) একটি গ্রাফিক্যাল সার্চ অ্যালগরিদম। সহজ কথায় বলতে গেলে, BFS হল একটি গাছের নোডের ব্রেডথ জুড়ে ব্রেডথ-ফার্স্ট-সার্চ। যদি সমস্ত নোড অ্যাক্সেস করা হয় তবে অ্যালগরিদমটি বন্ধ হয়ে যায়।

    অ্যালগরিদম ধাপঃ

    • ১, প্রথমে রুট নোডকে ক্যোয়ারে রাখুন.

    • ২। ক্যোয়ারী থেকে প্রথম নোডটি বের করুন এবং এটি লক্ষ্য কিনা তা পরীক্ষা করুন।

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

    • ৩. যদি সারিটি ফাঁকা থাকে, তাহলে পুরো গ্রাফটি পরীক্ষা করা হয়েছে এবং গ্রাফের কোন লক্ষ্য খুঁজে পাওয়া যায়নি।

    • ৪। ধাপ ২ পুনরাবৃত্তি করুন।

  • অ্যালগরিদম ৮ঃ ডিজেকস্ট্রা অ্যালগরিদম

    ডিকস্ট্রা অ্যালগরিদম (ইংরেজিঃ Dijkstra's Salgorithm) ডাচ কম্পিউটার বিজ্ঞানী ইজহর ডিকস্ট্রা দ্বারা উদ্ভাবিত। ডিকস্ট্রা অ্যালগরিদমটি একটি অ-নেতিবাচক ক্ষমতাপ্রাপ্ত অঙ্কিত গ্রাফের একক উত্সের সংক্ষিপ্ততম পথের সমস্যার সমাধানের জন্য একটি বিস্তৃত অগ্রাধিকার অনুসন্ধান ব্যবহার করে, যা শেষ পর্যন্ত একটি সংক্ষিপ্ততম পথ গাছ পায়। এই অ্যালগরিদমটি প্রায়শই রাউটিং অ্যালগরিদম বা অন্যান্য গ্রাফ অ্যালগরিদমের একটি উপ-মডিউল হিসাবে ব্যবহৃত হয়।

    এই অ্যালগরিদমের ইনপুট একটি ওজনযুক্ত ডাইরেক্টরিয়াল গ্রাফ জি, এবং একটি উত্স শীর্ষ S গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ গ

    সুতরাং w ((u,v) হল শীর্ষ u থেকে শীর্ষ v এর অ-নেতিবাচক ওজন; পার্শ্বের ওজন দুটি শীর্ষের মধ্যে দূরত্ব হিসাবে কল্পনা করা যেতে পারে; যে কোনও দুটি পয়েন্টের মধ্যে একটি পথের ওজন হল সেই পথের সমস্ত পক্ষের ওজন সমষ্টি; V এর একটি শীর্ষ s এবং t রয়েছে এবং Dijkstra অ্যালগরিদমটি s থেকে t পর্যন্ত সর্বনিম্ন ওজনযুক্ত পথ খুঁজে পেতে পারে; উদাহরণস্বরূপ, সংক্ষিপ্ততম পথ) । এই অ্যালগরিদমটি একটি গ্রাফের মধ্যে একটি শীর্ষ s থেকে অন্য কোনও শীর্ষ পর্যন্ত সংক্ষিপ্ততম পথও খুঁজে পেতে পারে; অ-নেতিবাচক ক্ষমতাযুক্ত নির্দেশিত গ্রাফের জন্য, Dijkstra অ্যালগরিদমটি বর্তমানে দ্রুততম একক উত্সের সংক্ষিপ্ততম পথের অ্যালগরিদম।

    অ্যালগরিদম ধাপঃ

    • ১, প্রাথমিক সময়সূচী S={V0}, T={অবশিষ্ট শীর্ষ}, T এর মধ্যে শীর্ষগুলির জন্য দূরের মান যদি ,d ((V0,Vi) থাকে তবে এর উপর একটি ওজন যদি না থাকে, d ((V0,Vi) ∞ হয়

    • ২, T থেকে একটি শীর্ষ W নির্বাচন করুন যার দূরত্বের মান সর্বনিম্ন এবং S এর মধ্যে নেই, এবং S যোগ করুন

    • ৩, বাকি T এর শীর্ষগুলির দূরত্বের মান পরিবর্তন করা হয়েছেঃ যদি W কে মধ্যম শীর্ষ হিসাবে যুক্ত করা হয় এবং V0 থেকে Vi এর দূরত্বের মান হ্রাস করা হয় তবে এই দূরত্বের মান পরিবর্তন করা হবে

      S এর মধ্যে সমস্ত শীর্ষগুলি উপস্থিত না হওয়া পর্যন্ত, W = Vi পর্যন্ত, উপরে দেওয়া ধাপ ২, ৩ পুনরাবৃত্তি করুন।

  • অ্যালগরিদম ৯ঃ গতিশীল পরিকল্পনা অ্যালগরিদম

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

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

    ডায়নামিক প্ল্যানিংয়ের সবচেয়ে প্রচলিত প্রশ্ন হল ব্যাকপ্যাকিং।

    অ্যালগরিদম ধাপঃ

    ১, সর্বোত্তম উপ-আকৃতিগত বৈশিষ্ট্য। যদি সমস্যাটির সর্বোত্তম সমাধানের অন্তর্গত উপ-সমস্যাটির সমাধানও সর্বোত্তম হয়, তাহলে আমরা সমস্যাটিকে সর্বোত্তম উপ-আকৃতিগত বৈশিষ্ট্য (অর্থাৎ সর্বোত্তম অপ্টিমাইজেশান নীতি পূরণ করে) বলি। সর্বোত্তম উপ-আকৃতিগত বৈশিষ্ট্যগুলি গতিশীল পরিকল্পনা অ্যালগরিদমের সমস্যার সমাধানের জন্য গুরুত্বপূর্ণ সূত্র সরবরাহ করে।

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

  • অ্যালগরিদম ১০ঃ বেজেস শ্রেণীবিভাগের সহজ অ্যালগরিদম

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

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

    এই সরল চিন্তাভাবনা এবং অত্যধিক সরলীকৃত অনুমান সত্ত্বেও, একটি সরল বেয়েজ শ্রেণিবদ্ধকারী অনেক জটিল বাস্তবতার ক্ষেত্রে বেশ ভাল কাজ করতে পারে।


আরো