الگوریتم های تقریبی چیست؟ – توضیح به زبان ساده + مثال

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

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

مفاهیم پیش نیاز الگوریتم های تقریبی

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

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

مسائل بهینه سازی چیست ؟

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

• پیدا کردن کوتاه‌ترین مسیر بین دو گره در گراف
• پیدا کردن حداقل تعداد رنگ‌های مورد نیاز برای رنگ‌آمیزی رئوس گراف

فیلم آموزش مقدماتی پیاده سازی مسائل بهینه سازی در پایتون Python در فرادرس

کلیک کنید

مسائل تصمیم گیری

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

• بررسی این که گراف تعریف شده، آیا از نوع «گراف همیلتونی» (Hamiltonian Graph) هست یا خیر؟
• بررسی این که آیا در گراف تعریف شده، حلقه وجود دارد یا خیر؟

کلاس مسائل

مسائل ریاضی و برنامه نویسی را بر اساس یک سری ویژگی‌ها، می‌توان در دو نوع کلاس دسته‌بندی کرد:

• کلاس P
• کلاس NP

در ادامه، به توضیح هر یک از انواع مسائل می‌پردازیم.

فیلم آموزش مسائل p و np در طراحی الگوریتم (رایگان) در فرادرس

کلیک کنید

کلاس P چیست ؟

مسائلی که در کلاس P گنجانده می‌شوند، جزء مسائلی محسوب می‌شوند که در «زمان چندجمله‌ای» (Polynomial Time) توسط ماشین تورینگ قابل حل شدن هستند. پیچیدگی زمانی این نوع مسائل در بدترین حالت برابر با (n^k)O است. مقدار k یک مقدار ثابت عددی در نظر گرفته می‌شود. میزان زمان یافتن پاسخ برای الگوریتم‌هایی که با زمان چندجمله‌ای قابل حل شدن هستند، به حجم داده‌های ورودی بستگی دارد.

فیلم آموزش بهینه سازی چند هدفه در متلب در فرادرس

کلیک کنید

به عنوان مثال، الگوریتمی که با n^2 مرحله قابل حل شدن است، پیچیدگی زمانی چندجمله‌ای دارد. مسائلی نظیر «ضرب زنجیره‌ای ماتریس» (Matrix Chain Multiplication)، یافتن «کوتاه‌ترین مسیر منفرد» (Single Source Shortest Path)، یافتن «تمام مسیرهای کوتاه» (All Shortest Path) و «درخت پوشای کمینه» (Minimum Spanning Tree) جزء مسائلی در نظر گرفته می‌شوند که پیچیدگی زمانی چندجمله‌ای دارند.

کلاس NP

مسائل تصمیم‌گیری را می‌توان جزء کلاس NP در نظر گرفت. در این نوع مسائل به دنبال این هستیم که صحت ادعا یا ویژگی مطرح شده برای مسئله را با کمک اطلاعات موجود بررسی کنیم. هر مسئله‌ای که از نوع کلاس NP است، پیچیدگی «زمانی نمایی» (Exponential Time) دارد.

فیلم آموزش مروری بر پیچیدگی محاسبات Computational Complexity در فرادرس

کلیک کنید

مسائلی از قبیل رنگ‌آمیزی بهینه گراف، وجود حلقه در گراف همیلتون و مسئله «فروشنده دوره گرد» (Travelling Salesperson) از نوع کلاس NP هستند.

الگوریتم های تقریبی چیست ؟

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

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

فیلم آموزش الگوریتم های بهینه سازی در یادگیری ماشین + پیاده سازی در متلب در فرادرس

کلیک کنید

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

در ادامه، به یک مثال کاربردی از روش حل الگوریتم های تقریبی برای مسائلی از نوع NP می‌پردازیم تا در درک مفهوم این نوع الگوریتم‌ها به خواننده کمک کند.

مثالی از الگوریتم های تقریبی : مسئله پوشش رأسی

در مسئله پوشش رأسی، گرافی غیرجهت‌دار وجود دارد و به دنبال یافتن کم‌ترین تعداد رأسی از این گراف هستیم که از طریق آن‌ها، تمام اتصالات یال‌های گراف برقرار شوند. سه مثال ارائه شده در تصویر زیر را در نظر بگیرید.

در مثال اول از سمت چپ، هیچ یالی بین دو گره ۰ و ۱ وجود ندارد. بنابراین مجموعه پوشش رأسی این مثال برابر با تهی است. در مثال دوم، از طریق گره ۳ می‌توان به تمام گره‌های دیگر گراف دسترسی داشت و تمام یال‌های این گراف، به گره ۳ متصل هستند. بدین ترتیب، مجموعه پوشش رأسی این گراف می‌تواند فقط شامل گره ۳ است. در مثال سوم در تصویر بالا، گره‌های ۴ و ۲ یا گره‌های ۴ و ۰ می‌توانند به عنوان رئوسی باشند که تمام اتصالات گراف با استفاده از آن‌ها برقرار می‌شوند.

فیلم آموزش بهینه سازی با پایتون – بررسی و حل مسائل تحقیق در عملیات در فرادرس

کلیک کنید

برای یافتن پاسخ مسئله پوشش رأسی می‌توان از رویکرد ساده‌ای استفاده کرد. فرض کنید گرافی دارید که دارای سه رأس ۰، ۱ و ۲ است. برای یافتن پاسخ مسئله پوشش رأسی، می‌توان مجموعه‌ای از ترکیب رئوس را به این صورت تعریف کنیم:

{0,1,2,{0,1},{0,2},{1,2},{0,1,2}}

سپس، به ازای هر یک از اعضای این مجموعه بررسی می‌کنیم که کدام یک از آن‌ها، تمامی یال‌های گراف را پوشش می‌دهند. بدین ترتیب، با استفاده از این روش، به پاسخ بهینه مسئله دست میابیم.

حال بیایید با استفاده از الگوریتم های تقریبی مسئله پوشش رأسی را حل کنیم. گراف زیر را در نظر بگیرید.

مراحل حل این مسئله را می‌توان با استفاده از الگوریتم های تقریبی به صورت زیر پیش برد:

1. مجموعه‌ای تهی برای راه‌حل نهایی مسئله با نام Result تعریف کنید‌: {}: Result
2. تمامی یال‌های گراف را در مجموعه‌ای با نام E تعریف کنید:
   {(a, b), (b, a), (b, c), (c, b), (c, f), (f, c), (c, e), (e, c), (d, e), (e, d), (b, d), (d, b)}: E
3. مراحل زیر را تا زمانی که مجموعه E تهی شود، تکرار کنید:
   1. یالی را به طور تصادفی از مجموعه E انتخاب کنید (u, v) و u و v را به مجموعه Result اضافه کنید.
   2. تمامی یال‌هایی را از مجموعه E حذف کنید که یکی از رئوس آن‌ها u یا v را شامل می‌شوند.
4. مجموعه Result را به عنوان پاسخ نهایی الگوریتم تقریبی در خروجی برگردانید.

فیلم آموزش مبانی محاسبات تکاملی و بهینه سازی هوشمند در فرادرس

کلیک کنید

در تصویر زیر، روال حل مسئله پوشش رأسی را با استفاده از الگوریتم تقریبی ملاحظه می‌کنید.

بدین ترتیب، ملاحظه می‌کنید که با استفاده از روش‌های تقریبی می‌توان در کوتاه‌ترین زمان به پاسخ مناسبی از مسئله رسید. در ادامه، قطعه کدی از زبان برنامه نویسی پایتون را ملاحظه می‌کنید که برای حل مسئله پوشش رأسی با استفاده از الگوریتم تقریبی ارائه شده است.

1# Python3 program to print Vertex Cover
2# of a given undirected graph
3from collections import defaultdict
4
5# This class represents a directed graph
6# using adjacency list representation
7class Graph:
8
9	def __init__(self, vertices):
10		
11		# No. of vertices
12		self.V = vertices
13		
14		# Default dictionary to store graph
15		self.graph = defaultdict(list)
16
17	# Function to add an edge to graph
18	def addEdge(self, u, v):
19		self.graph[u].append(v)
20
21	# The function to print vertex cover
22	def printVertexCover(self):
23		
24		# Initialize all vertices as not visited.
25		visited = [False] * (self.V)
26		
27		# Consider all edges one by one
28		for u in range(self.V):
29			
30			# An edge is only picked when
31			# both visited[u] and visited[v]
32			# are false
33			if not visited[u]:
34				
35				# Go through all adjacents of u and
36				# pick the first not yet visited
37				# vertex (We are basically picking
38				# an edge (u, v) from remaining edges.
39				for v in self.graph[u]:
40					if not visited[v]:
41						
42						# Add the vertices (u, v) to the
43						# result set. We make the vertex
44						# u and v visited so that all
45						# edges from/to them would
46						# be ignored
47						visited[v] = True
48						visited[u] = True
49						break
50
51		# Print the vertex cover
52		for j in range(self.V):
53			if visited[j]:
54				print(j, end = ' ')
55				
56		print()
57
58# Driver code
59
60# Create a graph given in
61# the above diagram
62g = Graph(7)
63g.addEdge(0, 1)
64g.addEdge(0, 2)
65g.addEdge(1, 3)
66g.addEdge(3, 4)
67g.addEdge(4, 5)
68g.addEdge(5, 6)
69
70g.printVertexCover()
71
72# This code is contributed by Prateek Gupta

ویژگی الگوریتم های تقریبی

الگوریتم های تقریبی ویژگی‌های مهمی دارند که باعث می‌شوند از آن‌ها در حل مسائل مختلفی استفاده کرد. در ادامه به برخی از مهم‌ترین این ویژگی‌ها اشاره شده است:

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

فیلم آموزش بهینه سازی مقید در متلب در فرادرس

کلیک کنید

جمع‌بندی

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