تکنیکهای طراحی الگوریتم - روش سیری ناپذیر

[Y@SiN]

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

لازم به ذکر است که:

روش سیری ناپذیر همیشه به یک جواب بهینه (مناسبترین جواب) نمی‌رسد و گاهی فقط تقریبی از جواب را بدست می‌آورد.
حتی برای مسائلی که دقیقا" با این روش قابل حل هستند، ممکن است تعیین درستی این روش امری دشوار باشد.
در این روش روال الگوریتم به این صورت است که از بین کاندیداهای ورودی (C)، تک به تک بهترین کاندیدا را انتخاب کرده (Select) و در صورتی که اضافه کردن کاندیدای انتخاب شده به مجموعه کاندیداهای از پیش انتخاب شده (S) بتواند مجموعه جواب محتملی ایجاد کند (Feasible)، آن را به مجموعه اضافه می‌کنیم. عمل انتخاب کاندیداها را وقتی متوقف می‌کنیم که یا دیگر کاندیدایی وجود نداشته نباشد یا اینکه مجموعه جواب محتمل بتواند به عنوان مجمومه جواب مسئله (Solution) قبول شود.

همانگونه که در ابتدا گفته شد٬ تابع Select با استفاده از یک روال عینی (Objective Function) بهترین کاندیدا را انتخاب می‌کند.



function Select(C: set of condidates) return cadidate
function Feasible(S: set of candidates) return boolean
function Solution(S: set of candidates) return boolean

function Gready(C: set of condidates) return set of condidates
var
S: set of condidates;
x: candidate;
begin
S := {} /* S is the set in which we construct solutions */
while not Solution(S) and (C <> {}) loop
X := Select(C)
C := C - {x}
if Feasible(S union {x}) then
S := S union {X}
end if
end loop
if Solution(S) then
return S
else
return {}
end if
end Gready
مثال:

می خواهیم بقیه پول مشتری را با کمترین تعداد پول خرد بپردازیم.

در این مثال مجموعه جواب احتمالی (Feasible) آن مجموعه از پول خردهاست که جمع آنها کمتر یا برابر با مقدار پولی باشد که قرار است به مشتری برگردانده شود. و مجموعه جواب مسئله (Solution) مجموعه‌ای از پول خردهاست که جمع آنها دقیقا" برابر با مقدار پول برگشتی مشتری است.

بدیهی است برای داشتن کمترین تعداد پول خرد، بهترین انتخاب٬ انتخاب بزرگترین پول خرد است. این همان چیزی است که به آن روال عینی (Objective Function) گفتیم و تابع Select براساس آن پیاده سازی می‌شود.




function FindCoinChanges(C: coin_set; /* واحدهای پول خرد */
K: integer) /* پولی که قرار است به مشتری برگردانده شود */
return coin_set; /* پول خردهای جواب */
var
S: coin_set; /* پول خردهایی که تا کنون انتخاب شده‌اند */
Sum: iteger; /* مجموع پول خردهایی که تا کنون انتخاب شده‌اند */
X: integer;
begin
S := {};
Sum := 0;
while not (Sum = K) /* SOLUTION */ and (C <> {}) loop
X := select the largest coin in C /* SELECT */
C := C - {X};
if (Sum + X <= K) /* FEASIBLE */ then
S := S + {X}
Sum := Sum + X
end if
end loop
if (Sum = K) /* SOLUTION */ then
return S
else
return {}
end if
end FindCoinChanges;
با فرض داشتن پول خردهای 1 و 5 و 10 ریالی، الگوریتم هواره بهترین جواب را بر می‌گرداند. اما اگر پول خرد 12 ریالی را به این مجموعه اضافه کنیم، الگوریتم الزاما"بهترین جواب را پیدا نخواهد کرد.

به عنوان مثال:


کد:

15 = 12 + 1 + 1 + 1
در صورتیکه بهترین جواب عبارت است از:

کد:

15 = 10 + 5
در حالتی حتی ممکن است الگوریتم علارقم وجود جواب، قادر به پیدا کردن جواب نباشد. فرض کنید پول خوردهایی که داریم 2 و 3 و 5 ریالی باشند:

کد:

6 = 5 + ?
در صورتیکه جوابی به صورت زیر موجود است:

کد:

6 = 3 + 3