X
تبلیغات
دانشجویان کامپیوتر دانشگاه آزاد رامهرمز - جزوه طراحی الگوریتم استاد محمد صیاحی
دانشجویان کامپیوتر دانشگاه آزاد رامهرمز
Computer Engineering, University Ramhormoz

 
تاريخ : دوشنبه هشتم خرداد 1391
جزوه طراحی الگوریتم استاد محمد صیاحی

www. Mohammadsayahi.blogsky.com

-------------------

بسم الله الرحمن الرحیم

جزوهطراحی الگوریتم

مهندس محمّد صيّاحي

مدرس جهاد دانشگاهی اهواز

روش حريصانه

روش حريصانه، که روش دستاوردهاي قدم به قدم نيز ناميده مي شود، جزو حوزه ی بزرگتري به نام روش هاي بهينه سازي است. در اين روش:

1. دنباله ای از انتخاب ها وجود دارند، که بايد از بين اين دنباله، انتخاب هايي که منجر به بهينه شدن جواب نهايي گردد انتخاب کنيم.

2. در هر مرحله از مراحل اجرايي الگوريتم، بايد قسمتی از جواب، يا به عبارت دیگر، مؤلفه اي از مؤلفه هاي جواب بدست آید.

3. نتيجه نهايي يك الگوريتم حریصانه، مجموعه اي از داده كه ممكن است ترتيب آنها نيز اهميت داشته باشد. اين مجموعه ی داده ها بيشتر مواقع زيرمجموعه داده هاي ورودي است.

4. جواب نهايي بايد تابع هدف يك عبارت را بهينه کند .البته باتوجه به اينكه در روش هاي حریصانه، آينده نگري وجود ندارد و به وضعيت جاري بيشتر توجه مي شود، واضح است كه اين بهينگي ممکن است كلي نباشد و بهینگی محلي باشد. یعنی حداقل و حداکثر فعلي حاصل مي شود نه حداقل و حداکثر سراسری.

5. تصميم اتخاذ شده در مورد انتخاب يا عدم انتخابِ يكي از داده هاي ورودي به عنوان مؤلفه اي از جواب، قطعي و غيرقابل برگشت است.

6. در اين روش بايد بصورت محلی بهترين انتخاب را انجام داد و اميدوار بود که بهترين انتخاب محلی، منجر به بهترين انتخاب سراسری نيز خواهد شد. اگر بتوان اين موضوع را اثبات نمود مي توان مسئله را به اين روش حل کرد.

مسئله مهم در استفاده از روش حريصانه اثبات مورد پنجم از موارد فوق مي باشد.

اجزاي الگوريتم هاي حريصانه عبارتند از:

1. مجموعه اوليه: مجموعه ی اوليه ای كه مؤلفه هاي جواب از بين آنها انتخاب مي شود.

2. مجموعه مؤلفه هاي انتخاب شده: مجموعه ی مؤلفه هايي كه تا کنون انتخاب شده اند (به عنوان قسمتی از جواب).

3. تابع انتخاب مؤلفه بعدي: تابعي براي انتخاب مؤلفه بعدي.

4. تابعي براي تعيين اينكه با انتخاب جاري و مجموعه ی انتخاب هاي قبلي، امكان رسيدن به جواب وجود دارد يا خير.

5. تابع هدف: براي ارزش دهي به جواب مسئله، كه هدف نهايي، بهينه كردن اين تابع است.

6. يك تابع براي بررسي اينكه مشخص كند در نهايت جواب حاصل شده يا خير.

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

function Greedy(A,n)

solution := 12∅' type="#_x0000_t75">

for i:=1 to n do

x := select (A)

if feasible(x,solution) then

solution := union (solution,x)

endif

repeat

return solution

end .

مسئله كوله پشتي ساده

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

ورودي:

:n تعداد کيسه ها

:Pi سود حاصل از انتخابِ كلِ کيسه ی iام

:Wi وزن كل کيسه iام

M: ظرفیت كوله پشتی

هدف: حداکثر کردن سود حاصل از انتخاب اجناس، يعنی:

12Maxi=1nx' type="#_x0000_t75">i.pi

شرايط مسئله:

مجموع وزن همه ی کيسه ها از وزن كوله پشتي بيشتر است، زيرا اگر كمتر باشد، يعني مي توان همه را برداشت و انتخابي وجود ندارد. همچنين مجموع وزن اجسامي كه انتخاب شده اند، از وزن كل كوله پشتي نبايد بيشتر شود.

1. 12i=1nw' type="#_x0000_t75">i>M

2. 12i=1nx' type="#_x0000_t75">i.wi 12≤M' type="#_x0000_t75">

خروجي:

كسري از کيسه iام كه انتخاب مي شود داخل عنصر iام آرايه قرار مي گيرد.

=Xi كسري از کيسه iام كه انتخاب مي شود. (i=1,…,n) (0 12≤' type="#_x0000_t75"> Xi 12≤1)' type="#_x0000_t75">

راه حل :

توسط مثال های نقضی مي توان نشان داد که انتخاب کيسه ها بصورت صعودی وزن، و يا نزولی سود ممکن است منجر به جواب بهينه نگردد. و لذا راه حل بهينه طوری است که بايد کيسه ها را بصورت نزولی سود بر وزنشان انتخاب کرد.

راه حل بهينه اين مي باشد كه سود حاصل از هر كيلو از اجسام را محاسبه كرده و از با ارزش ترين جسم شروع به انتخاب كنيم ماداميكه كوله پشتي فضا براي جسم جديد دارد، در غيراينصورت كسري از آن جسم را انتخاب مي كنيم. به بيان ديگر ابتدا اجسام را بصورت زیر مرتب مي کنيم و سپس به ترتيب انتخاب مي کنيم.

در الگوريتم زیر، وزن اجسام براساس بيشترين سود هر كيلوی آنها مرتب شده است. در كوله پشتي ساده 0 12≤' type="#_x0000_t75"> xi 12≤1' type="#_x0000_t75"> (xi درایه iام آرایه X می باشد). الگوريتم مورد نظر در زير بيان شده است:

procedure greedy-knapsack ( w, n, m, x )

cu := m

x :=0

for i:=1 to n do

if w(i) > cu then

exit

endif

x(i) :=1

cu := cu- w(i)

repeat

x(i) := cu/w(i)

end

اگر شرط موجود در منطقه هاشور خورده ی فوق، برقرار نشود، جسم iام انتخاب مي شود. Feasibility

اما اگر شرط برقرار بشود، كسري از جسم iام را انتخاب کرده تا بيشترين سود را حاصل شود و نيز کوله پشتی، کاملا پر شود.

روش تقسیم و حل

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

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

procdure d&c (p,q)

if small (p,q) then

return g(p,q)

else

m:= divide (p,q)

return combine (d&c(p,m) , d&c(m+1,q))

endif

end.

برای ارائه الگوريتم در اين روش بايد جزئيات توابع small،divide ،g و combine را مشخص کرد. small تصميم گيری در مورد کوچک بودن اندازه مسئله را انجام مي دهد. به اين معنی که در اين تابع مشخص مي شود که اگر اندازه مسئله به حد کافی کوچک است، ديگر احتیاجی به احضار بازگشتی الگوريتم نباشد، عمل تقسيم مسئله به زير مسائل خاتمه مي یابد. تابع g مسئله با اندازه کوچک را حل مي کند. تابع divide وظيفه تقسيم مسئله به زير مسائل کوچکتر را به عهده دارد و تابع combine هم ترکيب جواب زير مسائل را انجام مي دهد.

محاسبه عنصر حداقل و حداکثر يک آرايه

توسط یک روش تقسیم و حل، می توان عنصر حداقل و حداکثر یک آرايه را محاسبه کرد .کد اين الگوريتم بصورت زیر است:

procedure minmax(a, l, u, min, max)

if l=u then

min:= a(l)

max:= a(l)

elsif l+1=u then

if a(l)

min:= a(l)

max:= a(u)

else

min:= a(u)

max:= a(l)

endif

else

mid:= (l+u)/2

call minmax(a, l, mid, min1, max1)

call minmax(a, l, mid+1, min2, max2)

if min1

min:= min1

else

min:= min2

endif

if max1>max2 then

max:= max1

else

max:= max2

endif

endif

end.

روش برنامه سازی پويا

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

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

برای ارائه الگوريتم به روش برنامه سازی پويا، ۴ مرحله را بايد طراحی کرد:

1. تعريف تابعی، که حل تابع، منجر به حل مسئله شود.

2. بيان شرايط مرزی

3. بيان جواب مسئله بر حسب تابع

4. تعريف بازگشتی تابع

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

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

مسئله كوله پشتي 0/1

مسئله کوله پشتی صفر يا يک، که به صورت 0/1 نوشته می شود، مدلی از مسئله کوله پشتی است که در آن اشياء، يا بطور کامل انتخاب مي شوند، و يا انتخاب نمي شوند و نمي توان فقط کسری از اشياء را انتخاب کرد.

ورودي:

:n تعداد کيسه ها

:Pi سود حاصل از انتخاب كل جسم iام

:Wi وزن كل جسم iام

:M ظرفیت كوله پشتی

هدف: حداکثر سازی سود حاصل از انتخاب اجناس يعنی:

12Maxi=1nx' type="#_x0000_t75"> i.pi

شرايط مسئله:

وزن همه کيسه ها روي هم، از وزن كوله پشتي بيشتر است. زيرا اگر كمتر باشد، يعني مي توان همه را برداشت، در نتیجه انتخابي وجود ندارد. همچنين مجموع وزن اجسامي كه انتخاب شده اند، از وزن كل كوله پشتي نبايد بيشتر شود.

1. 12i=1nw' type="#_x0000_t75">i>M

2. 12i=1nx' type="#_x0000_t75">i.wi 12≤M' type="#_x0000_t75">

خروجي:

كسري از کيسه iام كه انتخاب مي شود، داخل عنصر iام آرايه قرار مي گيرد.

= Xiكسري از کيسه iام كه انتخاب مي شود. (i=1,…,n) ( Xi =0 or 1)

راه حل :

توسط مثال های نقضی، مي توان نشان داد که انتخاب کيسه ها بر اساس معيار مطرح شده در مسئله کوله پشتی کسری، ممکن است به جواب بهينه منجر نشود. توسط مثال نقضی مي توان اين موضوع را نشان داد.

الگوريتم:

1. gi(y): بيشترين سود حاصل از حل مسئله براي جسم i+1ام تا nام به شرطي كه ظرفیت كوله پشتی، y باشد.

2. g0(M): بيشترين سود حاصل از حل مسئله براي کل اجسام به شرطي كه ظرفیت كوله پشتی M باشد.

3. شرايط مرزي:

gn(y)= 0،) از جسمn+1 به بعد، جسمي وجود ندارد كه سودي داشته باشد)

y<0، ظرفیت كوله پشتی منفي مي باشد. يعني بيشتر از حد كوله پشتی جسم وجود دارد. در اين حالت gi(y)حالت ضرر است.

(gi(y)) = - 12âˆ‍' type="#_x0000_t75">

4. gi(y)= Max{(gi+1 (y), pi+1+ gi+1 (y- wi+1)}

مثال: مسئله زير را به به کمک الگوريتم فوق حل كنيد؟

30

10

20

P

13

10

12

W

M= 30

g0(30)= Max{g1(30), 20+ g1(18)}= 50

g1(30)= Max{g2(30), 10+ g2(20)}= 40

g1(18)= Max{g2(18), 10+ g2(8)}= 30

g2(30)= Max{g3(30), 30+ g3(17)}= 30

g2(20)= Max{g3(20), 30+ g3(7)}= 30

g2(18)= Max{g3(18), 30+ g3(5)}= 30

g2(8)= Max{g3(8), 30+ g3(-5)}= 0

M

M-1

Y

2

1

0

-

G

جواب

12-âˆ‍' type="#_x0000_t75">

0

12-âˆ‍' type="#_x0000_t75">

l

12-âˆ‍' type="#_x0000_t75">

gi(y)

12-âˆ‍' type="#_x0000_t75">

i

12-âˆ‍' type="#_x0000_t75">

12-âˆ‍' type="#_x0000_t75">

n-1

0

0

0

0

0

0

0

0

12-âˆ‍' type="#_x0000_t75">

n

نکته اساسی در روش محاسبه ماتريس جواب در اين است که به کدام يک از روش های زير مي توان ماتريس را پر کرد. با کمی دقت در رابطه بازگشتی مي توان به جواب رسيد.

function DP_knapsack(W,P,n,M)

for i¬0 to M do g[n,i]:= 0 repeat

for i¬0 to n do g[-,i]:= -∞ repeat

for i=n-1 to 0

for j=0 to m

g[i,j] =max{g[i+1,y],pi+1+g[i+1,y-Wi+1] }

repeat

repeat

return g[0,M]

end.

مرتبه زماني اين الگوريتم O(M.n)مي باشد.

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

روش عقبگرد

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

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

مثال: اعداد ۴ بيتی را پيدا کنيد که تعداد يک های آنها دقيقًا ۲ تا باشد.

برای اين مسئله فضای حالت را رسم مي کنيم:

در فضای حالت، وقتیکه اطمینان وجود دارد که اين مسير به جواب صحیح منجر نخواهد شد، عمل عقبگرد صورت مي گيرد که در شکل با علامت 12أ—' type="#_x0000_t75"> مشخص شده است .توسط کد زير، مي توان فضای حالت رسم شده در بالا را تشکيل داد و به جواب رسيد:

procedure BT(A, i, n)

f1:= sum(A,n)

if i>n then

if f1= 2 then write(A) endif

else

if f1>2 or 2-f1>n-i then return endif (*)

A[i] :=1

BT(A,i+1,n)

A[i] := 0

BT(A,i+1,n)

endif

end.

احضار اوليه رويه فوق، بايد بصورت BT(A,1,4)صورت گيرد. تابع sum در این کد، تعداد يک های رشته A را تا مرحله فعلی(i-1ام) محاسبه مي کند.

شرط مشخص شده در(*)، بررسی مي کند که درصورتیکه مسير فعلی منجر به جواب صحیح نخواهد شد، عمل عقبگرد را انجام مي دهد. شرط اول آن نشاندهنده بيش از حد مجاز بودن تعداد يک هاست و شرط دوم آن نشان دهنده کمتر از حد مجاز بودن تعداد بيت های مشخص نشده تا بحال مي باشد که هر دو شرط دليل غلط بودن مسير فعلی مي باشد.

مرتبه زمانی این کد، O(2n) مي باشد.

هرچه تعداد شروط دستور (*) بيشتر باشد، داخل درخت فضای حالت، زودتر عقبگرد صورت می گیرد و اين منجر به تقلیل زمان واقعی الگوريتم خواهد شد.

حال به ارائه مثالی ديگر در اين رابطه مي پردازيم.

روش انشعاب و تحديد

روش انشعاب و تحديد، روش يك روش غيرهدفمند ولي هوشمند است .در اين روش برخلاف روش عقبگرد، تمامي حالات در فضای حالت بررسی نمي شود و براساس شرطي كه در مسئله قرار داده مي شود، برخي از حالت ها بررسي نمي شوند. اين شروط وابسته به نوع مسئله متفاوت است.

سه تفاوت عمده، بين روش عقبگرد و روش انشعاب و تحديد وجود دارد:

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

2. در روش انشعاب و تحدید يک تابع محدود کننده وجو د دارد که مانع توسعه ی بيش از حد و نابجای شاخه های درختِ حل مسئله، می شود و در موقع لزوم شاخه ها را قطع کرده و مسير فعلی را ادامه نمی دهد. درحاليکه در روش عقبگرد چنين معياری وجود ندارد.

3. روش انشعاب و تحدید در مقايسه با روش عقبگرد هوشمندانه تر عمل مي کند و در هنگا م انتخاب شاخه جهت توسعه درخت حل مسئله، شاخه ای که احتمال بيشتری برای توليد جواب دارد، انتخاب مي شود.

حال به ارائه الگوريتم هايي مبتنی بر اين روش مي پردازيم.

7-1- فروشنده دوره گرد

در یک گراف جهت دار تعداد دورهای هامیلتونی (n-1)! است و در یک گراف جهت دار تعداد دورهای هامیلتونی 12(n-1)! 2' type="#_x0000_t75"> می باشد.

مثال: پيدا كردن كوتاهترين دور هاميلتوني در يك گراف با ٥ رأس

تابع محدود کننده:

f(G)= 1212' type="#_x0000_t75"> 12v ∈V{cu,v+cv,w:u,v,v,ware two least cost edges adjacent to vertex v}' type="#_x0000_t75">

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

درخت فضای حالات برای گرافی با ٥ رأس در حالت كلي به شكل زير مي باشد:

توضيح:

در يك گراف براي هر رأس ٢ يال با كمترين هزينه را انتخاب مي كنيم. مجموع هزينه ها را محاسبه كرده، سپس بر دو تقسيم مي كنيم تا كمترين هزينه اي كه ممكن است حاصل شود.

راس

اولین مینیمم

دومین مینیمم

A

2

3

B

3

3

C

4

4

D

2

5

E

3

6

35/2=17.5

طريقه محاسبه ارزش هر گره:

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

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

الگوريتم هاي انشعاب و تحدید، از لحاظ مرتبه زمانی تفاوتي با الگوريتم هاي عقبگرد ندارند، ولی از زمان واقعی کمتری برخوردارند.

در درخت حل مسئله فوق، فقط ۴ دور مختلف محاسبه شدند، درحالی که در روش عقبگرد بايد تمام ۱۲ دور مختلف را توليد کرد.

پیچیدگی محاسبات

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

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

مسائلی که خروجی آنها دارای دو حالت باشد، مسائل تصمیم گیری نامیده می شوند. بطور مثال، گراف وزن داری مفروض است، تشخيص اينکه آيا هزينه دور هاميلتونی حداقل اين گراف از مقدارk کمتر است يا خير، يک مسئله تصميم گيری محسوب مي شود. مسائل نوع بهینه سازی، خروجیشان، جواب بهینه است. در مورد هر مسئلۀ بهینه سازی متناظراً یک مسئلۀ تصمیم گیری نیز وجود دارد نمونه هایی از آن عبارتند از:

1. فروشنده دوره گرد

2. کوله پشتی 1/0

3. رنگ آمیزی گراف

كلاس P

مجموعه ی مسائل تصميم گيری كه براي آنها يك الگوريتم قطعي با زمان کثیرالجمله اي وجود داشته باشد، بطور مثال، مسائلی نظیر موارد زیر، همگی جزو کلاس P هستند:

1. تشخيص مرتب بودن يک آرايه

2. تشخيص اينکه يک رشته مفروض، شامل زير رشته خاصی هست يا خير؟

3. تشخيص همبند بودن يک گراف

به عبارت کامل تر، کلاس P، مجموعه ای از مسائل تصمیم گیری است که می توانند بوسیله الگوریتم هایی با پیچیدگی زمانی کثیرالجمله ای حل شوند. در واقع P، کلاسی از مسائل تصمیم گیری است که اگر بتوانند بوسیله الگوریتم هایی که پیچیدگی آنها از مرتبه یک کثیرالجمله است، حل شوند. یعنی مسائل، در بدترین حالت خود از لحاظ پیچیدگی زمانی، بوسیله کثیرالجمله ای قابل محدودسازی هستند. همچنین می توان گفت که یک مسئله از کلاس P است، فقط اگر قابل حل بوسیله الگوریتم های معین یا قطعی با پیچیدگی زمانی کثیرالجمله باشد. پس مطمئناً تمام مسائلی که برای آنها الگوریتم های با پیچیدگی زمانی کثیرالجمله ای حاصل شده است، جزء کلاس P می باشند. به عنوان مثال مسئلۀ تعیین اینکه عنصری در داخل (مرتب شده) و یا نامرتب، وجود دارد یا نه؟ و همینطور همۀ مسائل تصمیم گیری متناظر با مسائل بهینه سازی، همگی در این کلاس قرار دارند. حال سؤال اینستکه آیا مسائل تصمیم گیری که هنوز نتوانسته ایم برای آنها یک الگوریتم با پیچیدگی زمانی کثیرالجمله ای پیدا کنیم، می توانند در کلاس P باشند یا نه؟ با اینکه هنوز کسی نتوانسته برای حل این مسئله یک الگوریتم با پیچیدگی زمانی کثیرالجمله ای بدست آورد، اما هیچکس نیز نتوانسته ثابت کند که این کار غیرممکن است. پس ممکن است این مسئله نیز در P باشد ولی هنوز معلوم نیست. برای اینکه بدانیم یک مسئلۀ تصمیم گیری در P نمی باشد، باید بتوانیم اثبات کنیم که بدست آوردن الگوریتم با پیچیدگی زمانی کثیرالجمله ای برای حل آن مسئله، امکان پذیر نیست؛ که این کار هنوز برای مسئلۀ تصمیم گیری فروشندۀ دوره گرد صورت نگرفته است. همین مورد دربارۀ مسائل کوله پشتی 1/0 و رنگ آمیزی گراف نیز مصداق دارد.

حال سؤال اینستکه چه مسائل تصمیم گیری در P نیستند؟ بطوریکه بیان شد مسائل فروشندۀ دوره گرد، کوله پشتی 1/0 و رنگ آمیزی گراف ممکن است در P باشند (یعنی در آینده بتوان برای حل آنها الگوریتم های با پیچیدگی زمانی کثیرالجمله ای بدست آورد) و یا در P نباشند (یعنی در آتیه بتوان اثبات کرد که یافتن الگوریتم های با پیچیدگی زمانی چند جمله ای برای حل آنها امکان پذیر نیست)؛ بنابراین هنوز وضعیت اینگونه مسائل تصمیم گیری کاملاً مشخص نیست. در حال حاضر، هزاران مسائل تصمیم گیری از این گروه وجود دارند که مشخص نیست آیا در P قرار دارند یا نه؟ یعنی نمی دانیم که آنها در P هستند یا نه؟ اما مسائل تصمیم گیری که می شناسیم و می دانیم در P نیستند، نسبتاً کم و اندک می باشند. اینها، مسائل تصمیم گیری هستند که اثبات شده که به دست آوردن الگوریتم های با پیچیدگی زمانی کثیرالجمله ای برای آنها امکان پذیر نیست. نمونه ای از اینگونه مسائل، به دست آوردن همۀ مسیرها یا مدارهای همیلتون در یک گراف است.

كلاس NP

مجموعه ی مسائل تصميم گيری كه براي آنها يك الگوريتم غيرقطعي با زمان کثیرالجمله اي وجود داشته باشد، مسائل کلاس NP را تشکیل می دهد. کلاس P، مجموعه ای از تمام مسائل تصمیم گیری است که با الگوریتم های معین یا قطعی که در بدترین حالت الگوریتم های با پیچیدگی زمانی کثیرالجمله ای می باشند، قابل حل هستند. NP، مجموعه ای از تمام مسائل تصمیم گیری است که با الگوریتم های غیرقطعی، یعنی الگوریتم هایی هستند که در آنها خروجی یا نتیجۀ عملیات، به مجموعه ای از احتمالات مشخص، بستگی دارد.

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

اما چیزی که ما نمی دانیم؛ و یا چیزی که شاید یکی از مسائل معروف حل نشده در دانش کامپیوتر باشد آنستکه نمی دانیم که آیا P=NP و یا P≠NP است. بطور مثال، مسائلی نظیر موارد زیر، همگی جزو کلاس NP هستند:

1. تشخيص مرتب بودن يک آرايه

2. تشخيص اينکه يک رشته مفروض شامل زير رشته خاصی هست يا خير؟

3. تشخيص همبند بودن يک گراف

4. تشخيص اينکه آيا بيشترين سود حاصل در مسئله کوله پشتی صفر و يک از مقدار خاصی بيشتر است.

5. مسئله افراز: تشخيص اينکه يک مجموعه ی مفروض را مي توان طوری به دو قسمت، افراز کرد، که مجموع دو قسمت مساوی باشد.

6. مسئلهSum of Subset : تشخيص اينکه مي توان در يک مجموعه ی مفروض، يک زير مجموعه یافت، که مجموع عناصر آن معادل با عدد داده شده M باشد.

هر مسئلهP متعلق به NP نيز مي باشد. چون اگر برای مسئله ای، الگوريتم قطعی کثیرالجمله ای وجود داشته باشد. مي توان همان الگوريتم را غيرقطعی هم در نظر گرفت. در نتیجه هر مسئله قطعي، حالت غيرقطعي آن نيز وجود دارد.

مسائل Intractable

مسائلي كه ثابت شده است که متعلق به کلاس NP نيستند. بطور مثال، مسئله تشخيص اول بودن يک عددn بيتی، نمونه ای از چنین مسائلی است. به بیان دیگر خواهیم داشت:

مسئله ای که برای آن یک الگوریتم امکان پذیر نباشد، Intractable نامیده می شود. Intractable در لغت یعنی: مشکل، برای حل کردن.

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

یک الگوریتم با پیچیدگی زمانی کثیرالجمله ای، الگوریتمی است که پیچیدگی زمانی آن در بدترین حالت، با یک تابع کثیرالجمله ای برحسب بزرگی ورودی آن، محدود شده باشد. یعنی اگر n، بزرگی ورودی آن باشد، کثیرالجمله ای نظیر p(n) وجود دارد بطوریکه:

tw(n) 12∈' type="#_x0000_t75"> O(p(n))

بطور مثال، الگوریتم هایی که پیچیدگی زمانی آنها در بدترین حالت به صورت زیر می باشد؛ همگی الگوریتمی با پیچیدگی زمانی کثیرالجمله ای می باشند:

· 2n

· 3n3+4n

· 5n+n10

· n log n

الگوریتم هایی که پیچیدگی زمانی آنها در بدترین حالت به صورت زیر باشند، الگوریتمی با پیچیدگی زمانی کثیرالجمله ای هستند:

· 2n

· 20.01n

· 2 12âˆڑ' type="#_x0000_t75"> n

· n!

توجه داشته باشید که n log n یک کثیرالجمله برحسب n نمی باشد؛ اما به هر حال به لحاظ اینکه n log n2 باشد. بنابراین به وسیلۀ یک کثیرالجمله، محدود است؛ پس این الگوریتم قانون محدود بودن به وسیلۀ یک کثیرالجملۀ را دارا می باشد.

بطور کلی می توان گفت که یک الگوریتم دارای پیچیدگی زمانی کثیرالجمله ای است اگر و فقط اگر، پیچیدگی زمانی آن O(nd) باشد که در آن، d، یک عدد صحیح است.

از دیدگاه علم کامپیوتر یک مسئله، در صورتی Intractable نامیده می شود که حل آن با یک الگوریتم با پیچیدگی زمانی کثیرالجمله ای، غیر ممکن باشد. البته باید توجه کنیم که Intractability جزء خاصیت یک الگوریتم نیست، بلکه جزء خاصیت یک مسئله است.

برای اینکه یک مسئله، Intractable باشد، باید هیچ الگوریتمی با پیچیدگی از درجۀ کثیرالجمله ای که آن را حل کند وجود نداشته باشد (یعنی امکان پذیر نباشد). بدست آوردن یک الگوریتم با پیچیدگی زمانی غیر کثیرالجمله ای برای یک مسئله، آن را Intractable نمی سازد.

مسائل را از دیدگاه Intractability می توان به سه گروه کلی و عمومی زیر دسته بندی کرد:

1. مسائلی که برای آنها الگوریتم های با پیچیدگی زمانی کثیرالجمله ای پیدا شده است.

2. مسائلی که اثبات شده است که Intractable می باشند.

3. مسائلی که اثبات نشده است که Intractable باشند، ولی برای آنها هنوز الگوریتم های با پیچیدگی زمانی کثیرالجمله ای پیدا نشده است.

به نظر می رسد که در علم کامپیوتر اغلب مسائل جزء گروه اول و یا سوم می باشند.

تبديل یا کاهش

گوييم مسئله A در زمان کثیر الجمله ای، به B تبديل مي شود (A 12âˆ‌' type="#_x0000_t75"> p B)، اگر يک الگوريتم برای B را بتوان در زمان کثیرالجمله ای به الگوريتمی برای A تبديل کرد. یعنی، يک جواب برای يک نمونه مسئله از B در زمان کثیرالجمله ای منجر به يک جواب برای يک نمونه مسئله از A شود. مسائل زیر نمونه ای از چنین مسائلی هستند:

• Sorting 12âˆ‌' type="#_x0000_t75">p Convex Hull

• Partition 12âˆ‌' type="#_x0000_t75">p Sum of Subset

مرتب کردن n عدد توسط الگوريتم پوسته محدب: اعداد ورودی را مختصه x برای n نقطه در نظر مي گيريم و به عنوان مختصه y مقدار x2 را در نظر مي گيريم .حال پوسته محدب n نقطه را مي سازيم .قابل اثبات است که ترتيب x نقاط روی پوسته محدب مرتب شده اعداد اوليه هستند. مثال:

4

1

2

3

5

16

1

4

9

25

از قابل تبديل بودن مسئله مرتب سازی به پوسته محدب مي توان اثبات کرد که بهترين الگوريتم برای توليد پوسته محدب دارای زمان O(n. log n) مي باشد. چون اگر بتوان پوسته محدب را در زمان کمتر از O(n. log n) توليد کرد پس مرتب سازی هم در کمتر از O(n. log n) امکان پذير است که اين غير ممکن است چون مرتب سازی n عدد توسط الگوريتم های مقايسه ای در بدترين حالت 12Ω' type="#_x0000_t75">(n. log n) است.

مسئله:NP-Complete

خیلی از مسائل در دنیا، وجود دارند که برای آنها، الگوریتم کارآیی وجود ندارد و سختی ذاتی چنین مسائلی را نیز هنوز کسی نتوانسته اثبات کند. مسائل زیر همگی نمونه ای از مسائل NP-Complete هستند:

1. مسئله كوله پشتي 1/0

2. مسئله فروشنده دوره گرد

3. مسئله افراز

4. مسئله وجود و يا عدم وجود دور هاميلتونی در گراف

5. مسئله Sum of Subset

6. مسئله رنگ آميزی گراف

7. مسئله تا کردن خط کش(Ruler Folding)

8. مسئله یافتن مسيری به طول k در يک گراف وزن دار

مثلاً برای مسئلۀ فروشندۀ دوره گرد، هنوز الگوریتمی که پیچیدگی آن در بدترین حالت بهتر از نمایی باشد، حاصل نشده است. یعنی هنوز کسی نتوانسته پیچیدگی ذاتی این مسئله را اثبات کند. مسئلۀ فروشندۀ دوره گرد و هزاران مسئلۀ دیگر مشابه آن از لحاظ بدست آوردن الگوریتم کارآ، جزو گروه مسائل مشکل(Hard) می باشند و اگر بتوان برای یکی از آنها الگوریتم کارآیی طراحی کرد، می توانیم برای تمامی آنها چنین الگوریتم کارآیی بدست آورد. اما چنین الگوریتمی هنوز پیدا نشده است و عدم امکان وجود آن نیز هرگز اثبات نشده است. اینگونه مسائل را NP-complete نامند.

مسئلۀ فروشندۀ دوره گرد

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

مسئلۀ تصمیم گیری فروشندۀ دوره گرد آنستکه تعیین کنیم که آیا برای یک عدد مفروض مثبت d می توان یک تور بدست آورد که مجموع وزن آن (یعنی مجموع طول یال های طی شده) بزرگتر از d نباشد؟ این مسئله نیز پارامترهایی مشابه مسئله بهینه سازی فروشندۀ دوره گرد را دارد که پارامتر d نیز به آن اضافه شده است.

مسئلۀ كوله پشتي 1/0

مسئلۀ بهینه سازی كوله پشتي 1/0 عبارت از آنستکه حداکثر سود حاصل از قرار دادن اجناسی هر کدام با وزن و سود معلوم، در کیسه ای که وزن قابل تحمل آن W می باشد، بدست آوریم.

حال می توان گفت که مسئلۀ بهینه سازی كوله پشتي 1/0 آنستکه تعیین کنیم که آیا برای یک سود مفروض P، این امکان وجود دارد که اجناس را طوری انتخاب کنیم و در کیسه قرار دهیم که وزن مجموع آنها بیشتر از W نباشد و سود حاصل نیز حداقل برابر P گردد. این مسئله نیز دارای همان پارامترهای مسئلۀ بهینه سازی كوله پشتي 1/0 است، که پارامترهای P نیز به آن اضافه شده است.

مسئلۀ رنگ آمیزی گراف

مسئلۀ بهینه سازی رنگ آمیزی گراف آنستکه با حداقل تعداد رنگ، یک گراف را طوری رنگ آمیزی کنیم که هیچ دو رأس یا دو گره مجاور آن، همرنگ نباشند. این عدد حاصل نیز Chromatic Number گراف نامیده می شود.

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

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

d≥120

بله و در غیر این صورت (یعنی برای سایر مقادیر d) خیر خواهد بود. بطریق مشابه اگر سود بهینه برای یک نمونه از مسئلۀ بهینه سازی كوله پشتي 1/0 برابر 230$ باشد، جواب موردنظر برای مسئلۀ تصمیم گیری متناظر از آن برای:

P≤$230

بله و در غیر اینصورت (یعنی برای سایر مقادیر P) خیر خواهد بود.

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

مسئله تاکردن خط کش

یک پاره خط، که تعدادی مفصل بر روی آن مشخص شده اند، داریم كه هر پاره خط مي تواند حول مفاصل دو طرفش عمل دوران را تا ٣٦٠ درجه انجام بدهد. هدف كوتاهترين طول حاصل از تاکردن اين پاره خط ها بر روی خط افقی است. مثال:

مسئله افراز

در اين مسئله مجموعه اي از اعداد داده شده است و هدف افراز مجموعه به دو قسمت بطوری است که مجموع عناصر دو مجموعه، مساوی باشد.

مثال: با ورودي مجموعه زير مسئله افراز به نحوه اي كه داراي طول هاي يكساني باشند.(هزينه هاي يكسان)

مثال: ثابت کنيد مسئله افراز يک مجموعه قابل تبديل به مسئله یافتن مسيری به طول k در گراف است .برای اين کار گرافی مي سازيم که دارای n+1 راس است. بين راس i-1ام و iام دو يال جهتدار برقرار مي کنيم .يال اول دارای هزينه عنصرi ام از مجموعه اعداد داده شده و يال دوم دارای مقدار قرينه يال اول مي باشد .اکنون یافتن مسيری به طول صفر در اين گراف منجر به افراز مجموعه اوليه به دو قسمت با مجموع يکسان خواهد شد. انتخاب عناصر متناظر با يال های اول از هر راس به راس بعدی در مسير مورد نظر منجر به افراز مورد نظر خواهد شد.

فرض کنيد هدف افراز مجموعه {3,1,7,9} مي باشد .گرافی بصورت زير ساخته و در آن مسيري از A به B به طول صفر را بررسی مي کنيم:

دو مسير با هزينه صفر وجود دارد که يکی از آنها در زير نشان داده شده است:

مي توان نتيجه گرفت مجموعه قابل افراز به {3,7} و {1,9} مي باشد.



ارسال توسط ram.1988

VPN setup

قالب وبلاگ

دانلود رایگان