دنیای زبانهای کدنویسی و توسعه نرمافزار
دو مسئله کلاسیک برنامهنویسی پویای دیگر، تطبیقپذیری این تکنیک را فراتر از بهینهسازی عددی نشان میدهند: یافتن طولانیترین زیردنباله مشترک بین دو رشته، سنگبنای ابزارهای diff و بیوانفورماتیک، و ساخت یک درخت جستجوی دودویی که هزینه جستجوی مورد انتظار را با فرکانسهای دسترسی شناختهشده کمینه میکند. این راهنمای جامع هر دو الگوریتم را با جزئیات کامل، شامل استخراج رابطه بازگشتی، ساخت جدول، و بازسازی راهحل، مرور میکند.
الگوریتمهای حریصانه یک راهحل را قطعهبهقطعه میسازند، و همیشه گزینهای که در لحظه فعلی بهترین بهنظر میرسد را انتخاب میکنند، بدون هرگز بازبینی آن انتخاب بعداً، با این حال برای مسائل خاصی این استراتژی ساده بهطور اثباتپذیر یک نتیجه بهینه سراسری تولید میکند. این راهنمای جامع مسئله انتخاب فعالیت را بهعنوان یک مثال انگیزاننده پوشش میدهد، اصول کلی که تعیین میکنند چه زمانی الگوریتمهای حریصانه کار میکنند را استخراج میکند، و کدگذاری هافمن، یک الگوریتم حریصانه بهطور گسترده استفادهشده برای فشردهسازی بهینه داده، را توضیح میدهد.
برخی عملیاتهای ساختار داده گاهی زمان طولانی میگیرند، اما میانگینگیریشده در سراسر یک توالی کامل از عملیاتها، هزینه بهازای هر عملیات واقعاً بسیار پایین است. تحلیل مستهلک ابزارهای دقیقی برای اثبات این کارایی میانگین بدون تکیه بر احتمال یا فرضیات غیرواقعبینانه ورودی فراهم میکند. این راهنمای جامع سه تکنیک استاندارد تحلیل مستهلک را از طریق مثالهای کلاسیک آرایه پویا و شمارنده باینری پوشش میدهد.
وقتی داده بهاندازهای بزرگ است که در حافظه جا نمیشود و باید روی دیسک ذخیره شود، کمینهکردن تعداد دسترسیهای دیسک بسیار مهمتر از کمینهکردن مقایسهها میشود. این راهنمای جامع درختهای B را توضیح میدهد، یک ساختار درخت جستجوی متوازن که بهطور خاص برای کمینهکردن ورودی/خروجی دیسک با نگهداشتن کلیدهای زیاد بهازای هر گره طراحی شده، و ویژگیهای تعریفکننده، رویه جستجو، و تکنیک درج مبتنی بر تقسیم که توازن را حفظ میکند را پوشش میدهد.
بسیاری الگوریتمها نیاز دارند یک مجموعه پویا از مجموعههای مجزا را ردیابی کنند، و بهطور مکرر مجموعهها را ادغام کرده و پرسوجو کنند کدام مجموعه یک عنصر متعلق به آن است. این راهنمای جامع نمایش جنگل مجموعهمجزا، دو بهینهسازی حیاتی union by rank و path compression، و زمان اجرای مستهلک تقریباً-ثابتی که این بهینهسازیها با هم دست مییابند، نتیجهای مرکزی برای الگوریتمهایی مانند درخت پوشای کمینه کروسکال، را پوشش میدهد.
گرافها روابط بین اشیا را مدلسازی میکنند، و تقریباً هر الگوریتم گراف روی دو استراتژی پیمایش بنیادین ساخته میشود. این راهنمای جامع دو نمایش استاندارد گراف، لیستهای مجاورت و ماتریسهای مجاورت، را پوشش میدهد، سپس جستجوی سطحاول برای یافتن کوتاهترین مسیرها در گرافهای بدونوزن و جستجوی عمقاول برای کاوش ساختار و تشخیص چرخهها را توضیح میدهد، شامل ویژگیهای زمانبندیشان که در الگوریتمهای گراف بعدی استفاده میشوند.
ویژگیهای زمانبندی جستجوی عمقاول دو الگوریتم گراف قدرتمند با کاربرد عملی گسترده را باز میکنند: مرتبکردن وظایفی که وابستگی دارند، و شناسایی خوشههای بهشدت متصل درون یک گراف جهتدار. این راهنمای جامع مرتبسازی توپولوژیک برای زمانبندی وظایف وابسته را توضیح میدهد، سپس الگوریتم DFS دوعبوری ظریف برای یافتن مؤلفههای قویاًمتصل را مرور میکند.
اتصال مجموعهای از مکانها با کمترین هزینه کل اتصالات یک مسئله بهینهسازی کلاسیک با راهحلهای حریصانه ظریف است. این راهنمای جامع مسئله درخت پوشای کمینه را توضیح میدهد، قضیه عمومی مبتنی بر برش که رویکردهای حریصانه برای آن را توجیه میکند اثبات میکند، و هم الگوریتم کروسکال، ساختهشده روی ساختار مجموعهمجزا، و هم الگوریتم پریم، ساختهشده روی یک صف اولویت، را مرور میکند.
یافتن کوتاهترین مسیرها در یک گراف وزندار پیچیدهتر از حالت بدونوزن حلشده توسط جستجوی سطحاول است، بهویژه وقتی وزنهای یال منفی ممکن باشند. این راهنمای جامع تکنیک relaxation زیربنای همه الگوریتمهای کوتاهترینمسیر، الگوریتم بلمن-فورد که وزنهای منفی را مدیریت میکند و چرخههای منفی را تشخیص میدهد، و الگوریتم کارآمدتر دیجکسترا برای گرافهای بدون وزنهای منفی را پوشش میدهد.
گاهی یک اپلیکیشن به کوتاهترین فاصله بین هر جفت رأس ممکن نیاز دارد، نه فقط از یک منبع واحد. این راهنمای جامع مسئله کوتاهترین مسیرهای همهجفت را توضیح میدهد، رابطه بازگشتی برنامهنویسی پویای ظریف پشت الگوریتم فلوید-وارشال را استخراج میکند، و کارایی آن را در برابر اجرای مکرر الگوریتمهای منبع-واحد مقایسه میکند.
مسائل جریان بیشینه بیشترین توان عملیاتی ممکن از میان یک شبکه با اتصالات محدود-به-ظرفیت را مدلسازی میکنند، از لولههای آب تا شبکههای داده. این راهنمای جامع شبکههای جریان را معرفی میکند، روش فورد-فالکرسون برای یافتن جریان بیشینه با استفاده از مسیرهای تقویتی را مرور میکند، و قضیه ظریف برش-کمینه/جریان-بیشینه که دو مسئله بهظاهر متفاوت را به یکی متصل میکند را توضیح میدهد.
برخی مسائل برای دههها در برابر هر تلاشی برای یک الگوریتم کارآمد مقاومت کردهاند، با این حال هیچکس اثبات نکرده یک راهحل کارآمد غیرممکن است. این راهنمای جامع کلاسهای P و NP، مفهوم تقلیلهای زمان-چندجملهای مورد استفاده برای مقایسه سختی مسئله، و چگونگی اینکه اثبات NP-complete بودن یک مسئله شواهد قوی، هرچند نه اثبات، فراهم میکند که هیچ الگوریتم کارآمدی وجود ندارد را توضیح میدهد.
