حل مسئله بهینه سازی انتخاب فعالیت — راهنمای کاربردی
«حریصانه» (Greedy) بودن، یک پارادایم الگوریتمی است که طی آن، راهکار مسئله را تکه تکه می‌سازد و هر بار تکه‌ای با مشهودترین سود حداکثری و سریع‌ترین سود، انتخاب می‌شود. الگوریتم‌های حریصانه برای مسائل «بهینه سازی» (Optimization) مورد استفاده قرار می‌گیرند. یک مسئله بهینه‌سازی را می‌توان با استفاده از یک الگوریتم حریصانه حل کرد، اگر مسئله دارای خصوصیاتی باشد که در ادامه بیان شده است.
در هر گام، بتوان انتخابی انجام داد که در آن لحظه به نظر بهترین انتخاب باشد و راهکار بهینه برای مسئله به دست آید.
اگر یک الگوریتم حریصانه بتواند یک مسئله را حل کند، عموما بهترین روش برای آن مسئله، الگوریتم حریصانه خواهد بود و در حالت کلی و موثرتر، روش‌هایی مانند «برنامه‌نویسی پویا» (Dynamic Programming | برنامه‌ریزی پویا) به کار می‌آیند. اما الگوریتم‌های حریصانه همیشه قابل اعمال نیستند. برای مثال، مسئله کوله‌پشتی بخش‌بندی شده را می‌توان با استفاده از الگوریتم حریصانه حل کرد، اما مسئله کوله‌پشتی ۰ و ۱ را نمی‌توان با روش‌های حریصانه حل کرد. در ادامه، برخی از الگوریتم‌های استاندارد حریصانه معرفی شده‌اند.
درخت پوشای کمینه کراسکال (Kruskal’s Minimum Spanning Tree | MST): در الگوریتم کراسکال، درخت پوشای کمینه با انتخاب یال‌های دارای کمترین وزن که منجر به دور در درخت نمی‌شوند، ساخته می‌شود.
درخت پوشای کمینه پریم (Prim’s Minimum Spanning Tree): در الگوریتم پریم، درخت پوشای کمینه با انتخاب دانه به دانه یال‌ها ساخته می‌شود. در این الگوریتم، دو مجموعه نگهداری می‌شوند: یک مجموعه از یال‌هایی است که در حال حاضر در درخت پوشای کمینه قرار دارند و یک مجموعه مربوط به یال‌هایی است که در آن قرار ندارند. انتخاب حریصانه برای انتخاب یال دارای کمترین وزن است که دو مجموعه را متصل می‌کند.
کوتاه‌ترین مسیر دیکسترا (Dijkstra’s Shortest Path): الگوریتم دیکسترا شباهت زیادی به الگوریتم پریم دارد. کوتاه‌ترین مسیر درخت، به صورت یال به یال، ساخته می‌شود. دو مجموعه نگهداری می‌شود. یک مجموعه از راس‌هایی که در حال حاضر در درخت قرار دارند و یک مجموعه از راس‌هایی که در آن قرار ندارند. انتخاب حریصانه، انتخاب یالی است که دو مجموعه را متصل می‌کند و در مسیری با کمترین وزن از منبع به مجموعه‌ای که هنوز حاوی هیچ راسی نیست، متصل می‌شود.
کدگذاری هافمن (Huffman Coding): کدگذاری هافمن یک روش فشرده‌سازی فاقد از دست رفتن اطلاعات است. در این روش، بیت کدهای طول متغیر به کاراکترهای مختلفی تخصیص پیدا می‌کنند. انتخاب حریصانه برای تخصیص کد طول کمترین بیت به مکررترین کاراکتر است.
الگوریتم‌های حریصانه گاهی برای به دست آوردن تخمینی برای «مسائل بهینه‌سازی سخت» مورد استفاده قرار می‌گیرند. برای مثال، «مسئله فروشنده دوره‌گرد» (Traveling Salesman Problem) یکی از مسائل ان‌پی سخت است. یک انتخاب حریصانه، انتخاب نزدیک‌ترین شهر ملاقات نشده از شهر کنونی، در هر گام است. این راهکار، همیشه راهکار بهینه را فراهم نمی‌کند اما می‌تواند یک راهکار تقریبا بهینه را ارائه کند.
اکنون، مسئله انتخاب فعالیت به عنوان اولین مثال از الگوریتم حریصانه مد نظر قرار می‌گیرد. تعریف این مسئله، در ادامه ارائه شده است. n فعالیت با زمان شروع و پایان آن‌ها داده شده است. هدف انتخاب بیشینه تعداد فعالیت‌هایی است توسط یک فرد واحد قابل انجام است؛ با در نظر داشتن این موضوع که یک فرد در هر بار فقط می‌تواند روی یک فعالیت متمرکز شود. مثال زیر برای درک بهتر این مطلب، قابل توجه است.
Consider the following 3 activities sorted by
by finish time.
start[] = {10, 12, 20};
finish[] = {20, 25, 30};
A person can perform at most two activities. The
maximum set of activities that can be executed
is {0, 2} [ These are indexes in start[] and
finish[] ]
Example 2 : Consider the following 6 activities
sorted by by finish time.
start[] = {1, 3, 0, 5, 8, 5};
finish[] = {2, 4, 6, 7, 9, 9};
A person can perform at most four activities. The
maximum set of activities that can be executed
is {0, 1, 3, 4} [ These are indexes in start[] and
finish[] ]
انتخاب حریصانه آن است که همیشه فعالیت بعدی که زمان پایان آن در میان فعالیت‌های باقیمانده کمترین باشد انتخاب شود و زمان آغاز مساوی یا بیشتر از زمان پایان فعالیت‌هایی باشد که پیش از این انتخاب شده‌اند. برای انجام انتخاب، می‌توان فعالیت‌ها را مطابق با زمان پایان آن‌ها مرتب‌سازی کرد، بنابراین همیشه فعالیت بعدی به عنوان فعالیت حداقل زمان پایان در نظر گرفته می‌شود. راهکار مورد استفاده برای این کار، در ادامه بیان شده است.
- فعالیت‌ها را مطابق با زمان پایان آن‌ها مرتب کن.
- اولین فعالیت را از آرایه مرتب شده انتخاب و آن را چاپ کن.
- اقدامات زیر را برای فعالیت‌های باقیمانده در آرایه مرتب شده انجام بده.
- اگر زمان آغاز این فعالیت بزرگ‌تر یا مساوی زمان پایان فعالیتی است که پیش از این انتخاب شده، پس فعالیت را انتخاب و آن را چاپ کن.
در پیاده‌سازی که در ادامه به زبان C ارائه شده است، فرض شده است که فعالیت‌ها در حال حاضر مطابق با زمان پایان آن‌ها مرتب‌سازی شده‌اند.
پیاده‌سازی روش اول در ++C
// C++ program for activity selection problem.
// The following implementation assumes that the activities
// are already sorted according to their finish time
#include<stdio.h>
// Prints a maximum set of activities that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start time of all activities
// f[] --> An array that contains finish time of all activities
void printMaxActivities(int s[], int f[], int n)
{
int i, j;
printf ("Following activities are selected n");
// The first activity always gets selected
i = 0;
printf("%d ", i);
// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
printf ("%d ", j);
i = j;
}
}
}
// driver program to test above function
int main()
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = sizeof(s)/sizeof(s[0]);
printMaxActivities(s, f, n);
return 0;
}
پیاده‌سازی روش اول در جاوا
// The following implementation assumes that the activities
// are already sorted according to their finish time
import java.util.*;
import java.lang.*;
import java.io.*;
class ActivitySelection
{
// Prints a maximum set of activities that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start time of all activities
// f[] --> An array that contains finish time of all activities
public static void printMaxActivities(int s[], int f[], int n)
{
int i, j;
System.out.print("Following activities are selected : n");
// The first activity always gets selected
i = 0;
System.out.print(i+" ");
// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
System.out.print(j+" ");
i = j;
}
}
}
// driver program to test above function
public static void main(String[] args)
{
int s[] = {1, 3, 0, 5, 8, 5};
int f[] = {2, 4, 6, 7, 9, 9};
int n = s.length;
printMaxActivities(s, f, n);
}
}
پیاده‌سازی روش اول در #C
// The following implementation assumes
// that the activities are already sorted
// according to their finish time
using System;
class GFG
{
// Prints a maximum set of activities
// that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start
// time of all activities
// f[] --> An array that contains finish
// time of all activities
public static void printMaxActivities(int[] s,
int[] f, int n)
{
int i, j;
Console.Write("Following activities are selected : ");
// The first activity always gets selected
i = 0;
Console.Write(i + " ");
// Consider rest of the activities
for (j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (s[j] >= f[i])
{
Console.Write(j + " ");
i = j;
}
}
}
// Driver Code
public static void Main()
{
int[] s = {1, 3, 0, 5, 8, 5};
int[] f = {2, 4, 6, 7, 9, 9};
int n = s.Length;
printMaxActivities(s, f, n);
}
}
// This code is contributed
// by ChitraNayal
پیاده‌سازی روش اول در پایتون
"""The following implementation assumes that the activities
are already sorted according to their finish time"""
"""Prints a maximum set of activities that can be done by a
single person, one at a time"""
# n --> Total number of activities
# s[]--> An array that contains start time of all activities
# f[] --> An array that contains finish time of all activities
def printMaxActivities(s , f ):
n = len(f)
print "The following activities are selected"
# The first activity is always selected
i = 0
print i,
# Consider rest of the activities
for j in xrange(n):
# If this activity has start time greater than
# or equal to the finish time of previously
# selected activity, then select it
if s[j] >= f[i]:
print j,
i = j
# Driver program to test above function
s = [1 , 3 , 0 , 5 , 8 , 5]
f = [2 , 4 , 6 , 7 , 9 , 9]
printMaxActivities(s , f)
# This code is contributed by Nikhil Kumar Singh
پیاده‌سازی روش اول در PHP
<?php
// PHP program for activity selection problem.
// The following implementation assumes that
// the activities are already sorted according
// to their finish time
// Prints a maximum set of activities
// that can be done by a single
// person, one at a time.
// n --> Total number of activities
// s[] --> An array that contains start
// time of all activities
// f[] --> An array that contains finish
// time of all activities
function printMaxActivities($s, $f, $n)
{
echo "Following activities are selected " . "\n";
// The first activity always gets selected
$i = 0;
echo $i . " ";
// Consider rest of the activities
for ($j = 1; $j < $n; $j++)
{
// If this activity has start time greater
// than or equal to the finish time of
// previously selected activity, then select it
if ($s[$j] >= $f[$i])
{
echo $j . " ";
$i = $j;
}
}
}
// Driver Code
$s = array(1, 3, 0, 5, 8, 5);
$f = array(2, 4, 6, 7, 9, 9);
$n = sizeof($s);
printMaxActivities($s, $f, $n);
// This code is contributed
// by Akanksha Rai
?>
خروجی قطعه کدهای بالا، به صورت زیر است.
Following activities are selected ۰ ۱ ۳ ۴
پرسشی که در این وهله مطرح می‌شود این است که انتخاب حریصانه چگونه برای فعالیت‌های مرتب شده بر اساس زمان پایان، کار می‌کند؟ فرض می‌شود که مجموعه فعالیت‌ها S = {1, 2, 3, ..n} است و فعالیت‌ها بر اساس زمان پایان یافتن آن‌ها مرتب شده‌اند. انتخاب حریصانه همیشه فعالیت ۱ را انتخاب می‌کند. اما فعالیت ۱ چطور همیشه یکی از راه حل‌های بهینه را فراهم می‌کند؟ این مورد را می‌توان با نشان دادن آنچه در ادامه می‌آید اثبات کرد.
اگر یک راهکار B با اولین فعالیت بعد از ۱ وجود داشته باشد، بنابراین یک راهکار A با اندازه مشابه فعالیت ۱ به عنوان اولین فعالیت وجود دارد.
فرض می‌شود که اولین فعالیت انتخاب شده توسط B، فعالیت k باشد؛ بنابراین، همیشه A = {B – {k}} U {1} وجود دارد. (شایان ذکر است که فعالیت‌های موجود در B مستقل هستند و K کمترین زمان پایان را در میان همه گزینه‌ها دارد. با توجه به اینکه k برابر با ۱ نیست، finish(k) >= finish(1)).
پرسشی که رد این وهله مطرح می‌شود این است که چگونه می‌توان هنگامی که فعالیت‌ها مرتب شده نیستند، آن را پیاده‌سازی کرد. یک ساختار/کلاس از فعالیت‌ها ساخته می‌شود. همه فعالیت‌ها بر اساس زمان پایان آن‌ها دسته‌بندی می‌شوند. هنگامی که همه فعالیت‌ها مرتب شدند، الگوریتمی مشابه با الگوریتم بالا، اعمال می‌شود. در ادامه، ارائه بصری از رویکرد بیان شده قابل مشاهده است.
پیاده‌سازی روش بیان شده، در زبان برنامه‌نویسی ++C، در ادامه ارائه شده است.
پیاده‌سازی روش دوم در ++C
// C++ program for activity selection problem
// when input activities may not be sorted.
#include <bits/stdc++.h>
using namespace std;
// A job has a start time, finish time and profit.
struct Activitiy
{
int start, finish;
};
// A utility function that is used for sorting
// activities according to finish time
bool activityCompare(Activitiy s1, Activitiy s2)
{
return (s1.finish < s2.finish);
}
// Returns count of the maximum set of activities that can
// be done by a single person, one at a time.
void printMaxActivities(Activitiy arr[], int n)
{
// Sort jobs according to finish time
sort(arr, arr+n, activityCompare);
cout << "Following activities are selected n";
// The first activity always gets selected
int i = 0;
cout << "(" << arr[i].start << ", " << arr[i].finish << "), ";
// Consider rest of the activities
for (int j = 1; j < n; j++)
{
// If this activity has start time greater than or
// equal to the finish time of previously selected
// activity, then select it
if (arr[j].start >= arr[i].finish)
{
cout << "(" << arr[j].start << ", "
<< arr[j].finish << "), ";
i = j;
}
}
}
// Driver program
int main()
{
Activitiy arr[] = {{5, 9}, {1, 2}, {3, 4}, {0, 6},
{۵, ۷}, {۸, ۹}};
int n = sizeof(arr)/sizeof(arr[0]);
printMaxActivities(arr, n);
return 0;
}
خروجی قطعه کد بالا، به صورت زیر است.
Following activities are selected (۱, ۲), (۳, ۴), (۵, ۷), (۸, ۹),
در صورتی که فعالیت‌ها مرتب شده نباشند، پیچیدگی زمانی این روش از درجه O(n log n) است. همچنین، هنگامی که فعالیت ها مرتب شده باشند، از درجه O(n) خواهند بود. با استفاده از STL در ++C، این مسئله را می‌توان به صورت زیر حل کرد.
پیاده‌سازی روش سوم در ++C
// C++ program for activity selection problem
// when input activities may not be sorted.
#include <bits/stdc++.h>
using namespace std;
void SelectActivities(vector<int>s,vector<int>f){
// Vector to store results.
vector<pair<int,int>>ans;
// Minimum Priority Queue to sort activities in ascending order of finishing time (f[i]).
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>p;
for(int i=0;i<s.size();i++){
// Pushing elements in priority queue where the key is f[i]
p.push(make_pair(f[i],s[i]));
}
auto it = p.top();
int start = it.second;
int end = it.first;
p.pop();
ans.push_back(make_pair(start,end));
while(!p.empty()){
auto itr = p.top();
p.pop();
if(itr.second >= end){
start = itr.second;
end = itr.first;
ans.push_back(make_pair(start,end));
}
}
cout << "Following Activities should be selected. " << endl << endl;
for(auto itr=ans.begin();itr!=ans.end();itr++){
cout << "Activity started at: " << (*itr).first << " and ends at " << (*itr).second << endl;
}
}
// Driver program
int main()
{
vector<int>s = {1, 3, 0, 5, 8, 5};
vector<int>f = {2, 4, 6, 7, 9, 9};
SelectActivities(s,f);
return 0;
}
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامه نویسی
- آموزش ساختمان داده‌ها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
- الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
- الگوریتم پریم — به زبان ساده
- متن کاوی (Text Mining) — به زبان ساده
منبع [+]
مجموعه: برنامه نویسی, بهینه سازی
Loading...