الگوریتم‌های تقریبی به جای یافتن راه‌حل دقیق و بهینه، راه‌حل‌هایی تقریبی ارائه می‌دهند که به طور معمول بهترین راه‌حل ممکن نیستند، اما با سرعت بالا و با استفاده از منابع کمتر قابل محاسبه‌اند. این الگوریتم‌ها به صورت تقریبی بهینه بودن راه‌حل را تضمین می‌کنند، به این معنی که میزان فاصله راه‌حل ارائه‌شده توسط الگوریتم از راه‌حل بهینه معیاری را از دست نمی‌دهد. یکی از مثال‌های رایج الگوریتم‌های تقریبی، الگوریتم گریدی است که برای حل مسئله پوشش تعدادی نقطه از یک فضا با استفاده از کمترین تعداد دایره‌ها طراحی شده است. الگوریتم گریدی با سرعت بالا و استفاده کمتر از منابع یک مجموعه دایره‌ها را ارائه می‌دهد که نقاط مورد نظر را به طور تقریبی پوشش می‌دهد.
مفاهیم پیش‌نیاز الگوریتم‌های تقریبی
برای درک بهتر الگوریتم‌های تقریبی باید با یکسری مفاهیم پیش‌نیاز آشنا باشیم. اولین مورد مسئله بهینه‌سازی است. مسئله‌ای که هدف آن یافتن بهترین راه‌حل ممکن با استفاده از یک معیار بهینه‌سازی است. به عنوان مثال، می‌توانیم به مسئله کمینه‌سازی یک تابع هدف یا مسئله بیشینه‌سازی یک تابع هدف اشاره کنیم. مورد بعدی NP-hard است که اشاره به مسائلی دارد که به دلیل پیچیدگی محاسباتی‌شان، نیاز به الگوریتم‌های با زمان اجرای نمایی دارند. این مسائل در دسته NP قرار دارند که الگوریتم‌های دقیق و بهینه‌سازی برای آنها وجود ندارد. الگوریتم‌های تقریبی معمولاً برای حل این مسائل استفاده می‌شوند.
ضریب تقریب بیان‌گر عددی است که نشان می‌دهد چقدر راه‌حل ارائه‌شده توسط یک الگوریتم تقریبی از راه‌حل بهینه مسئله دور است. برای مثال، اگر ضریب تقریب ۲ باشد، به این معنی است که راه‌حل ارائه‌شده حداکثر دو برابر راه‌حل بهینه است. مورد بعدی تراکم مسئله است که بیان‌گر معیاری است که نشان می‌دهد مسئله چقدر پیچیده است و چقدر اطلاعات درباره ساختار مسئله در اختیار داریم. تراکم مسئله می‌تواند تاثیر زیادی در طراحی الگوریتم‌های تقریبی داشته باشد. حداکثر نسبت تقریبی (Approximation Ratio) ضریب تقریب برای یک الگوریتم تقریبی است. به عنوان مثال، اگر حداکثر نسبت تقریب ۳ باشد، به این معنی است که ضریب تقریب الگوریتم حداکثر ۳ است و راه‌حل ارائه‌شده توسط الگوریتم حداکثر سه برابر راه‌حل بهینه است. آشنایی با پیش‌نیاز‌های یاد شده کمک می‌کنند تا بفهمید چگونه الگوریتم‌های تقریبی برای حل مسائل بهینه‌سازی استفاده می‌شوند.
مسائل بهینه‌سازی چیست؟
مسائل بهینه‌سازی مجموعه‌ای از مسائل ریاضی هستند که هدف آنها یافتن بهترین راه‌حل ممکن برای یک معیار بهینه‌سازی است. در اینگونه مسائل، باید یک تابع هدف تعریف شود که بر اساس آن، باید مقدار بهینه‌ای را بیابیم. مسائل بهینه‌سازی در زمینه‌ها و صنایع مختلف مورد استفاده قرار می‌گیرند. به عنوان مثال، در مهندسی صنایع، مسائل بهینه‌سازی می‌توانند در بهینه‌سازی فرآیندهای تولید، مدیریت زنجیره تأمین، برنامه‌ریزی منابع و برنامه‌ریزی تولید مورد استفاده قرار بگیرند. در علوم کامپیوتر، مسائل بهینه‌سازی در طراحی الگوریتم‌های بهینه، بهینه‌سازی پایگاه داده، مسائل برنامه‌ریزی خطی و غیرخطی، مسائل برنامه‌ریزی عدد صحیح و غیره مورد استفاده قرار می‌گیرند.
به طور معمول، مسائل بهینه‌سازی دارای یک مجموعه متغیرهای تصمیم‌گیری هستند که باید به صورتی تعیین شوند که مقدار بهینه تابع هدف را بیشینه یا کمینه کنند. این متغیرها می‌توانند محدودیت‌ها و قیدهایی را نیز داشته باشند که باید در راه‌حل بهینه رعایت شوند.
مسائل تصمیم‌گیری
مسائل تصمیم‌گیری، مسائلی هستند که در آنها باید در مورد انتخاب بهترین گزینه بین گزینه‌های مختلف تصمیم‌گیری کنیم. در اینگونه مسائل، هدف ما تعیین بهترین تصمیم است که بر اساس آن، معیار مشخصی را بهبود دهیم. در مسائل تصمیم‌گیری، معمولا مشکلات و چالش‌های مختلفی وجود دارد که باید در نظر گرفته شوند. این مشکلات می‌توانند شامل محدودیت‌ها، قیدها، متغیرهای تصمیم‌گیری، تغییرات زمانی و ساختارهای پیچیده‌ای باشند که باید با آنها مواجه شویم. مثال‌های رایجی در این زمینه وجود دارند. اولین مورد مسئله برنامه‌ریزی خطی است. در این مسئله، باید برنامه‌ریزی خطی را به صورتی انجام دهیم که هدفی مشخص (مانند سود بیشینه یا هزینه کمینه) را بهبود دهیم و در عین حال محدودیت‌های موجود (مانند منابع محدود، قیدها و محدودیت‌های فنی) را رعایت کنیم.
مورد بعدی مسئله برنامه‌ریزی غیرخطی است. در این مسئله، تابع هدف یا قیدها به صورت غیرخطی هستند. به خاطر پیچیدگی ریاضی آنها، حل این مسائل معمولا دشوار است و الگوریتم‌های تصمیم‌گیری خاصی برای آنها طراحی می‌شوند. مسئله بسته‌بندی یکی دیگر از مثال‌ها در این زمینه است. در این مسئله، باید اجسامی را در بسته‌های محدود قرار دهیم به صورتی که معیاری مشخص (مانند حجم کمینه یا هزینه کمینه) را بهبود دهیم و شرایطی مانند محدودیت‌های فضایی و وزنی را رعایت کنیم.
مسئله تخصیص منابع یکی دیگر از موضوعات جالب توجه در این زمینه است. در این مسئله، باید منابع را بین فعالیت‌ها یا پروژه‌های مختلف تخصیص دهیم به صورتی که معیاری مشخص (مانند بهره‌وری بیشینه یا زمان کمینه) را بهبود دهیم و محدودیت‌ها (مانند منابع محدود، ظرفیت و ترتیب اجرا) را درنظر بگیریم.
کلاس مسائل
مسائل تصمیم‌گیری را می‌توان در دسته‌بندی‌های مختلفی قرار داد. یکی از روش‌های رایج برای دسته‌بندی مسائل تصمیم‌گیری، طبقه‌بندی آنها بر اساس ویژگی‌های مشترک آنها است. برخی از کلاس‌های رایج مسائل تصمیم‌گیری به شرح زیر هستند:
- مسائل خطی و غیرخطی: مسائل تصمیم‌گیری می‌توانند بر اساس خطی یا غیرخطی بودن توابع هدف و محدودیت‌ها دسته‌بندی شوند. در مسائل خطی، توابع هدف و محدودیت‌ها به صورت خطی هستند، در حالی که در مسائل غیرخطی، حداقل یکی از توابع هدف یا محدودیت‌ها به صورت غیرخطی است.
- مسائل گسسته و پیوسته: مسائل تصمیم‌گیری می‌توانند بر اساس طبیعت متغیرهای تصمیم‌گیری دسته‌بندی شوند. در مسائل گسسته، مقادیر متغیرهای تصمیم‌گیری محدود به مجموعه‌ای گسسته هستند، مانند تصمیم‌گیری در مورد انتخاب محصولات برای تولید. در مقابل، در مسائل پیوسته، مقادیر متغیرهای تصمیم‌گیری می‌توانند به صورت پیوسته و در بازه‌های مختلف قرار بگیرند، مانند تصمیم‌گیری درباره تخصیص منابع در یک پروژه.
- مسائل دسته‌بندی و رده‌بندی: در این کلاس از مسائل، هدف ما تقسیم بندی داده‌ها به دسته‌ها و رده‌های مختلف است. مثال‌هایی از این دسته از مسائل شامل دسته‌بندی ایمیل‌ها به عنوان "هرزنامه" یا "نامه مهم"، تشخیص بیماری بر اساس علائم بالینی، و تشخیص تصاویر به عنوان "گربه" یا "سگ" می‌شوند.
- مسائل مسیریابی: در این کلاس از مسائل، هدف ما تعیین بهترین مسیر بین نقاط مختلف است. برخی مثال‌های این دسته شامل مسئله یافتن کوتاه‌ترین مسیر در شبکه، برنامه‌ریزی ترافیکی و غیره است.
- مسائل تصمیم‌گیری چندمعیاره: در این کلاس از مسائل، هدف ما تصمیم‌گیری بر اساس چندین معیار واگرا است. به عبارت دیگر، برای انتخاب بهترین گزینه بین گزینه‌های مختلف، باید چند معیار را در نظر بگیریم که ممکن است با یکدیگر در تناقض باشند.
کلاس P چیست ؟
در محاسبات پیچیده، کلاس P یک کلاس از مسائل محاسباتی است که توسط ماشین‌های تورینگ با زمان چندجمله‌ای قابل حل هستند. به عبارت دیگر، مسئله‌ای در کلاس P قابل حل است اگر و تنها اگر وجود داشته باشد روشی با زمان اجرای چندجمله‌ای برای حل آن. زمان اجرای چندجمله‌ای به معنای این است که زمان اجرای الگوریتم بر حسب تابع چندجمله‌ایی بر مبنای اندازه ورودی محاسبه می‌شود. به عنوان مثال، اگر یک الگوریتم در زمان O(n^2) اجرا شود، به این معنی است که زمان اجرای الگوریتم به طور خطی با مربع اندازه ورودی (n) افزایش می‌یابد. مسائلی که در کلاس P قرار می‌گیرند، معمولا در زمان عادی قابل حل هستند. لازم به توضیح است که کلاس P توسط کلاس‌های دیگری از مسائل محاسباتی مانند کلاس NP و کلاس NP-hard توسعه پیدا کرده است. این کلاس‌ها بیشتر به مسائلی اشاره دارند که زمان اجرای الگوریتم‌های دقیق برای آنها بسیار زمان‌بر است.
کلاس NP
کلاس NP سرنام (Non-deterministic Polynomial time) یک کلاس مهم در محاسبات پیچیده است. مسائلی که در این کلاس قرار می‌گیرند، معمولا مسائل تصمیم‌گیری هستند که الگوریتم‌های غیرقطعی (non-deterministic) می‌توانند در زمان چندجمله‌ای به طور تضمینی پاسخ درست را به آنها بدهند.
برای توضیح بهتر، لازم است ابتدا الگوریتم‌های غیرقطعی را مورد بررسی قرار دهیم. در الگوریتم‌های غیرقطعی، به جای دنبال کردن یک مسیر مشخص در تصمیم‌گیری، همه مسیرهای ممکن همزمان مورد بررسی قرار می‌گیرند. به عبارت دیگر، الگوریتم‌های غیرقطعی می‌توانند در هر مرحله از اجرا، بین چندین گزینه بهترین انتخاب را انجام دهند. کلاس NP شامل مسائلی است که با استفاده از الگوریتم‌های غیرقطعی نشان می‌دهد که پاسخ در کوتاه‌ترین زمان به دست آمده است.
به عنوان مثال، فرض کنید یک مسئله دسته‌بندی داده‌ها داریم. الگوریتم غیرقطعی می‌تواند یک تقسیم‌بندی اولیه از داده‌ها را انتخاب کند و سپس در زمان چندجمله‌ای بررسی کند که آیا این تقسیم‌بندی درست است یا خیر.
بد نیست بدایند که کلاس NP شامل مسائل مهم و پیچیده ای در دنیای محاسبات می شود. مسائل NP-سخت (NP-hard) که دسته‌ای از مسائل هستند که به‌اندازه مسائل NP نیاز به منابع پردازشی دارند، در حالی که مسائل NP-سخت کامل (NP-complete) هم در کلاس NP و هم NP-سخت هستند. اگر بتوان برای یک مسئله NP-سخت یک الگوریتم بازگشتی چندجمله‌ای یافت، آن مسئله NP-سخت کامل نیز خواهد بود. کلاس NP اهمیت بسیاری در تئوری محاسبات دارد و به عنوان بستری برای مطالعه الگوریتم‌های تقریبی و مسائل بهینه‌سازی استفاده می‌شود. علاوه بر این، مسئله P vs NP که یکی از مهمترین مسائل بینایی در علوم کامپیوتر است، به بررسی رابطه بین کلاس P و کلاس NP می‌پردازد
مثالی از الگوریتم‌های تقریبی : مسئله پوشش راسی
مسئله پوشش راسی (Vertex Cover) یکی از مسائل معروف در تئوری گراف است. در این مسئله، هدف پیدا کردن یک مجموعه کوچکتر از رئوس گراف است که تمام یال‌های گراف را پوشش دهد. به عبارت دیگر، باید یک زیرمجموعه از رئوس گراف را انتخاب کنیم، به طوری که هر یال حداقل یکی از رئوس انتخاب شده را در بر گیرد.
مسئله پوشش راسی یک مسئله NP-سخت است، به این معنی که تا کنون هیچ الگوریتمی با زمان اجرای چندجمله‌ای برای حل دقیق آن پیدا نشده است. اما می‌توان از الگوریتم‌های تقریبی برای حل تقریبی این مسئله استفاده کرد. یک الگوریتم تقریبی ساده و معروف برای مسئله پوشش راسی الگوریتم ۲-تقریبی است. این الگوریتم به صورت زیر عمل می‌کند:
- شروع با مجموعه خالی رأس‌ها که پوشش راسی را شامل می‌شود.
- بررسی یک یال به طور تصادفی و اضافه کردن دو راس آن به مجموعه پوشش راسی.
- حذف تمام یال‌هایی که حداقل یکی از رئوس آنها در مجموعه پوشش راسی قرار دارد.
- ادامه مراحل ۲ و ۳ تا زمانی که هیچ یال باقی نمانده باشد.
با اجرای این الگوریتم، می‌توان یک مجموعه تقریبی از رئوس گراف را به عنوان پاسخ به مسئله پوشش راسیی به دست آورد. البته، این مجموعه تقریبی ممکن است بزرگتر از مجموعه بهینه واقعی باشد، اما با توجه به نسبت تقریبی ۲، حداکثر دو برابر اندازه مجموعه بهینه خواهد بود.
الگوریتم ۲-تقریبی یک نمونه از الگوریتم‌های تقریبی است که برای حل مسئله پوشش راسی استفاده می‌شود. این الگوریتم‌ها معمولا با زمان اجرای چندجمله‌ای قابل اجرا هستند و به دلیل سرعت و کارایی خود، کاربرد گسترده‌ای در مسائل دارند.
اکنون اجازه دهید نحوه کدنویسی الگوریتم ۲-تقریبی برای مسئله پوشش راسیی را به زبان پایتون پیاده‌سازی کنیم.
def vertex_cover_approximation(graph):
vertex_cover = set()
edges = graph.edges()
while edges:
# انتخاب یک یال به طور تصادفی
edge = edges.pop()
u, v = edge
# اضافه کردن دو رأس یال به مجموعه پوشش راسیی
vertex_cover.add(u)
vertex_cover.add(v)
# حذف یال‌هایی که حداقل یکی از رئوس آنها در مجموعه پوشش راسیی قرار دارد
edges = [e for e in edges if u not in e and v not in e]
return vertex_cover
در این کد، ورودی graph یک گراف است که با استفاده از ساختار داده‌های مناسب (مانند لیست مجاورت یا ماتریس مجاورت) نمایش داده شده است. الگوریتم به صورت تصادفی یک یال را انتخاب می‌کند و دو راس آن را به مجموعه پوشش راسی اضافه می‌کند. سپس، تمام یال‌هایی که حداقل یکی از رئوس آنها در مجموعه پوشش راسی قرار دارد، از لیست یال‌ها حذف می‌شوند. این فرآیند تا زمانی که هیچ یالی باقی نمانده ادامه می‌یابد. در نهایت، مجموعه پوشش راسی به عنوان خروجی برگردانده می‌شود.
مقدار بازگشتی vertex_cover مجموعه رئوسی است که به عنوان پوشش راسی تقریبی به دست آمده است. البته، به دلیل استفاده از الگوریتم تقریبی، این مجموعه ممکن است بزرگتر از مجموعه بهینه واقعی باشد، اما با نسبت تقریبی ۲، حداکثر دو برابر اندازه مجموعه بهینه خواهد بود.
ماهنامه شبکه را از کجا تهیه کنیم؟
ماهنامه شبکه را می‌توانید از کتابخانه‌های عمومی سراسر کشور و نیز از دکه‌های روزنامه‌فروشی تهیه نمائید.
ثبت اشتراک نسخه کاغذی ماهنامه شبکه
ثبت اشتراک نسخه آنلاین
کتاب الکترونیک +Network راهنمای شبکه‌ها
- برای دانلود تنها کتاب کامل ترجمه فارسی +Network اینجا کلیک کنید.
کتاب الکترونیک دوره مقدماتی آموزش پایتون
- اگر قصد یادگیری برنامه‌نویسی را دارید ولی هیچ پیش‌زمینه‌ای ندارید اینجا کلیک کنید.
نظر شما چیست؟