الگوریتمستان
برنامهنویسی، طراحی الگوریتم و حل مسئلههای الگوریتمی
الگوریتم جستجوی اول عمق (Depth First Search - DFS) الگوریتمی مشابه الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف است. این دو الگوریتم خواص و کاربردهای مشترک بسیاری دارند و تفاوت اصلی در این است که در هر تکرار الگوریتم DFS تنها یکی از گرههای مجاور گره پردازش شده برای مرحلهی بعد انتخاب میشود. به این ترتیب، الگوریتم DFS به جای صف از یک پشته برای مشخص کردن مسیر پیمایش استفاده میکند.
الگوریتم فلوید-وارشال (Floyd-Warshall) یک الگوریتم مبتنی بر روش برنامهنویسی پویا برای محاسبهی کوتاهترین مسیر بین هر دو جفت گره گرافهای وزندار است. دو الگوریتم رایج دایکسترا و بلمن-فورد روشهای محاسبهی کوتاهترین مسیر از مبدأ ثابت هستند که در صورت تکرار آنها به ازای هر گره عملکردی همانند الگوریتم فلوید-وارشال دارند. اما این الگوریتم ویژگیهایی دارد که آن را برجسته میکند:
الگوریتم پیمایش اول سطح یا جستجوی اول سطح (Breadth First Search - BFS) از جمله الگوریتمهای مشهور پیمایش و جستجوی گراف است که در حل مسائل الگوریتمی و هوش مصنوعی کاربرد دارد. این الگوریتم برای پیمایش و جستجوی گراف از یک صف برای نگهداری ترتیب جستجو استفاده میکند.
الگوریتم BFS با وارد کردن گره مبدأ به صف پردازش شروع شده و تا خالی نشدن این صف مراحل زیر را تکرار میشود:
1- عنصر جلوی صف را به عنوان گره جاری انتخاب و از صف حذف کن.
2- گره جاری را پردازش کن.
الگوریتم دایکسترا (دیکسترا، دایجسترا - Dijkstra) یک راهکار حریصانه برای یافتن کوتاهترین مسیر از مقصد ثابت (تک منبع) به سایر گرههای گراف وزندار است. این گراف میتواند معرف مسیرهای یک شهر و تقاطعهای آن باشد که انبار شرکت در یک گره آن قرار داشته و هدف یافتن کوتاهترین مسیر به هر محل دیگر از این انبار است. طبیعتا این الگوریتم در یافتن کوتاهترین مسیر بین دو گره مشخص نیز کاربرد دارد. تنها شرط لازم برای استفاده از این الگوریتم نامنفی بودن وزن یالهای گراف است.