تکنیک های طراحی الگوریتم در DAA

وقتی نوبت به حل مشکلات می رسد ، به ویژه در علوم کامپیوتر ، الگوریتم ها چیزی هستند که نقش مهمی ایفا می کنند. یک الگوریتم مجموعه ای از قوانین برای حل سریع یک مشکل خاص است. اما سؤال این است که چگونه می توان یک الگوریتم را برای حل آن مشکل طراحی کرد؟بنابراین متخصصان فناوری اطلاعات در حال ارتقاء دانش خود و توسعه رویکردهای مختلف برای ساختن یک الگوریتم مؤثر برای تحقق خواسته های در حال گسترش صنعت هستند. تکنیک های مختلف طراحی الگوریتم و کاربردهای آنها در این مقاله مورد بحث قرار گرفته است.

فهرست مقاله (برای پرش کلیک کنید)

جستجوی بی رحمانه

این یک رویکرد ساده برای پرداختن به مشکلی است که به قدرت پردازش عظیم و آزمایش همه امکانات برای بهبود کارآیی متکی است. فرض کنید ترکیبی از قفل 4 رقمی را فراموش کرده اید و برای جلوگیری از خرید جدید ، باید با استفاده از روش جستجوی بی رحمانه قفل را باز کنید. برای باز کردن قفل آن باید تمام ترکیبات 4 رقمی ممکن را از 0 تا 9 امتحان کنید. این ترکیب می تواند بین 0000 تا 9999 باشد ، از این رو 10،000 ترکیب وجود دارد. بنابراین می توانیم بگوییم که در بدترین حالت ، شما باید 10 ، 000 بار امتحان کنید تا ترکیب واقعی خود را پیدا کنید.

جستجوی نیروی بی رحمانه برای ترکیبی از قفل قفل

پیچیدگی زمان نیروی بی رحمانه O (منگنز) است که می تواند به صورت O (n*m) نوشته شود. این بدان معنی است که اگر ما نیاز به جستجوی رشته های "N" در یک رشته از شخصیت های "M" داشته باشیم ، پس از آن "N*M" تلاش می کند.

تفرقه بینداز و حکومت کن

الگوریتم تقسیم و فاتح روی رویکرد از بالا به پایین کار می کند و برای مشکلات بزرگ ترجیح داده می شود. همانطور که از نام می گوید تقسیم و فتح ، مراحل زیر را دنبال می کند:

مرحله 1: مشکل را به چندین زیرنویس تقسیم کنید.

مرحله 2: هر یک از زیرنویس ها را تسخیر یا حل کنید.

مرحله 3: برای به دست آوردن نتیجه مورد نیاز ، هر یک از زیرنویس ها را با هم ترکیب کنید.

تقسیم و فاتح هر یک از زیرگروه ها را به صورت بازگشتی حل کنید ، بنابراین هر یک از این زیرگروه ها مشکل اصلی کوچکتر خواهند بود.

تفرقه بینداز و حکومت کن

الگوریتم حریص

در الگوریتم حریص ، منابع بسته به حداکثر و فوری در هر مرحله از اجرای ، به یک حلقه تقسیم می شوند. این روش برای حل مشکلات بهینه سازی که در آن مجموعه ای از مقادیر ورودی ارائه می شود ، استفاده می شود ، که باید با توجه به هدف افزایش یا کاهش یابد. الگوریتم حریص همیشه گزینه را انتخاب می کند ، که به نظر می رسد در حال حاضر بهترین است. به همین دلیل به الگوریتم حریص شناخته می شود. ممکن است همیشه راه حل بهینه سازی شده را ارائه ندهد. دو مرحله برای حل مشکل با استفاده از الگوریتم حریص وجود دارد:

1. بررسی لیست موارد.
2. بهينه سازي

این بدان معنی است که یک الگوریتم حریص بهترین گزینه فوری را انتخاب می کند و به تصمیمات خود تجدید نظر نمی کند. هنگامی که نوبت بهینه سازی یک راه حل می رسد ، این به سادگی دلالت بر این دارد که راه حل حریص به دنبال راه حل های بهینه محلی است که می تواند چندگانه باشد و ممکن است از یک راه حل بهینه جهانی استفاده کند. به عنوان مثال ، الگوریتم حریص در انیمیشن زیر قصد دارد مسیر را با بیشترین مبلغ پیدا کند.

با هدف رسیدن به بزرگترین مبلغ ، در هر مرحله ، الگوریتم حریص چیزی را انتخاب می کند که به نظر می رسد انتخاب فوری بهینه است ، بنابراین در مرحله دوم 12 به جای 3 انتخاب می کند و به بهترین راه حل نمی رسد ، که شامل 99 استبشر

برنامه نویسی پویا

برنامه نویسی پویا (DP) یک تکنیک الگوریتمی برای حل مشکلات بهینه سازی با شکستن آنها در زیرنویس های ساده تر و ذخیره هر یک از راه حل های فرعی است به طوری که می توان زیرنویس مربوطه را فقط یک بار حل کرد. برنامه نویسی پویا یک روش خوب برای مشکلات بهینه سازی است که به دنبال حداکثر یا حداقل راه حل با محدودیت ها است زیرا در تمام مشکلات زیر ممکن است جستجو می کند و هرگز نتیجه گیری را به هیچ مشکلی زیر نمی دهد.

این یک استراتژی الگوریتمی برای تجزیه یک مشکل بهینه سازی در زیرنویس های کوچکتر و اعمال این واقعیت است که بهترین راه حل برای مشکل کلی با بهترین راه حل برای مشکلات فرعی آن تعریف شده است. به عنوان مثال در مورد سری فیبوناچی که در آن هر شماره مجموع دو عدد قبلی است. فرض کنید دو شماره اول این سریال 0 ، 1 است. اگر از آن خواسته می شود تعداد نهمین سری را پیدا کنید ، می توانیم این کار را به شرح زیر انجام دهیم:

مثال برنامه نویسی پویا

در اینجا ، برای حل مشکل کلی یعنی فیبر (N) ، ما باید آن را به دو مشکل کوچکتر یعنی FIB (N-1) و FIB (N-2) تقسیم کنیم. از این رو ، ما می توانیم از برنامه نویسی پویا برای حل مسئله فوق استفاده کنیم ، که در شکل زیر با جزئیات بیشتری شرح داده شده است:

سری فیبوناچی با استفاده از برنامه نویسی پویا

الگوریتم شاخه و محدود

برای مشکلات بهینه سازی ریاضی ترکیبی ، گسسته و عمومی ، از الگوریتم های شاخه و محدود برای تعیین راه حل بهینه استفاده می شود. یک شاخه و الگوریتم محدود مجموعه ای از تمام راه حل های ممکن را قبل از توصیه بهترین مورد جستجو می کند. این الگوریتم با کاوش در تمام راه حل های ممکن ، راه حل های احتمالی نامزد را به صورت گام به گام ذکر می کند.

الگوریتم شاخه و محدود

اول از همه ما یک درخت تصمیم گیری ریشه دار می سازیم که در آن گره ریشه نمایانگر کل فضای جستجو است. هر گره کودک بخشی از مجموعه راه حل است و یک راه حل جزئی است. بر اساس راه حل بهینه ، ما قبل از ساختن درخت تصمیم گیری ریشه ، یک محدوده بالا و پایین را برای یک مشکل معین تنظیم کرده ایم و باید تصمیم بگیریم که کدام گره را در راه حل تعیین شده در هر سطح قرار دهد. پیدا کردن محدوده بالا و پایین و یافتن محدوده بالایی از هر روش بهینه سازی محلی بسیار مهم است. همچنین می توان با انتخاب هر نقطه در فضای جستجو و آرامش محدب یافت. در حالی که ، می توان از دوگانگی برای یافتن مرز پایین استفاده کرد.

الگوریتم تصادفی

الگوریتم تصادفی به الگوریتمی اشاره دارد که از اعداد تصادفی استفاده می کند تا در هر نقطه از منطق خود چه کاری انجام دهد. در یک الگوریتم استاندارد ، معمولاً برای کاهش زمان اجرا یا پیچیدگی زمان یا حافظه مورد استفاده یا پیچیدگی فضایی استفاده می شود. این الگوریتم با ایجاد یک عدد تصادفی ، R ، از مجموعه ای از اعداد و تصمیم گیری بر اساس ارزش آن کار می کند. این الگوریتم می تواند با زدن سکه یا کشیدن کارت از یک عرشه ، در تصمیم گیری در وضعیت شک و تردید کمک کند.

نماد الگوریتم تصادفی شده

هنگام استفاده از یک روش تصادفی ، دو مورد زیر را در خاطر داشته باشید:

• این منبع از اعداد تصادفی طول می کشد و در حین اجرای به همراه ورودی انتخاب تصادفی می کند.
• رفتار یک الگوریتم حتی در ورودی های ثابت نیز متفاوت است.

الگوریتم های پشتی

Backtracking بدان معنی است که اگر راه حل فعلی کار نمی کند ، باید به عقب برگردید و گزینه دیگری را امتحان کنید. این روشی برای حل و فصل مسائل با تلاش برای ساختن یک راه حل به صورت تدریجی ، یک قطعه در یک زمان است ، و هرگونه راه حل هایی را که محدودیت های مشکل را در هر مقطع زمانی برآورده نمی کند ، دور می کند. این روش برای حل مشکلات با داشتن چندین راه حل استفاده می شود. به عنوان مثال اگر می خواهیم تمام روشهای ممکن برای ترتیب 2 پسر و 1 دختر را روی 3 نیمکت با محدودیت پیدا کنیم که دختر نباید روی نیمکت میانی باشد. بنابراین 3 خواهد بود!= 6 امکان برای حل این مشکل. ما همه روشهای ممکن را به صورت بازگشتی امتحان خواهیم کرد تا راه حل مورد نیاز را بدست آوریم. این امکانات به شرح زیر است:

امکانات مثال Backtracking

نمودار زیر راه حل های ممکن برای مشکل فوق را نشان می دهد:

راه حل های پشتی