روش حریصانه(Greedy Approach)

صفحه 1:


صفحه 2:
(Greedy Approach)aila > (9, رویکردی که روش حریصانه برای حل مسائل بهینه‌سازی دارد شامل تصمیم گیری‌های پشت‌سرهم است که برای هر تصمیم‌گیری تنها از اطلاعات بدست آمده تا آن مرحله استفاده م ىكند. بنایراین اصطلاحا گفته می‌شود که تصمیم‌گیری بر اساس انتخاب‌هایی صورت en a an ‏متیر ند سورت‎ در اين رويكرد حل مساله أميد واريم تابه راه حل بهينه برسيم. اما .. این زاه سل بهینه "دزیزخی موارد بدبيث تمئآيد: در این رویکرد برای هر الگوریتم پیشنهادی باید نشان داده شود که پاسخ همواره در تمامی موارد بهینه است. 

صفحه 3:
‎(Greedy Approach)aila > (9,‏ مساله: می‌خواهیم باقی پول مشتری را با تعدادی سکه (اسکناس) پرداخت کنیم (تایمانیکه سکه‌های_یشتریوجود دارد و مساله هنوز حلن_شده لست) ‎while‏ ‏{ ‏0 "6166110۲ 5//:بزررگترین سکه باقیمانده را بردار ‏۷ 2 شافه کردنسکه سیبمیشود مجموع سکه‌هایردلشته‌شده از مبلغ بدهیسیشتر شود) 1۴ ‎check‏ ‏از اون سکه صرفنظر کن ‎else‏ ‏سکه را اضافه کن 0 0 1( گر مجموع سکه‌هایردلشته شده با بسدهیبولبری‌میکد) ۱۲ ‎check‏ ‏#مساله حل ‎wads‏ ست ‎ ‎ ‎ 

صفحه 4:
‎(Greedy Approach)aila > (9,‏ در حل مسائل با شیوه حریصانه هر تکرار از سه بخش تشکیل شده است: الف) روال انتخاب ‎selection procedure)‏ ‎feasibility check) ax. (G‏ ج) بررسی راه‌حل 6۳6 ‎(solution‏ ‎ ‎ ‎ 

صفحه 5:
(Greedy Approach)aila > (9, در حل مسائل با شیوه حریصانه هر تکرار از سه بخش تشکیل شده است: ‎(selection procedure) Gail Jlg, (WI!‏ با معیاری آیتم بعدی را انتخاب می‌کند تا به مجموعه راه‌حل اضافه شود. توجه شود که معیار انتخاب مسلما بر اساس اطلاعات تا هر مرحله است ... هرچند سعی می‌شود تا بهینه باشد ولی چون .. از اطلاعات فقط تا همان مرحله استفاده می‌کند گفته می‌شود که معیار بهینگی محلی است. feasibility check) ‏ب) امكانسنجى‎ با اضافه شدن آیتم جدید به مجموعه پاسخ. کنترل می‌شود که آیا با تکمیل کردن اين مجموعه می‌توان به پاسخ رسید یا خیر ج) بررسی راه‌حل ۱ ۱ کنترل می‌شود که با بدست آمدن مجموعه ‎LI ate‏ پاسخ پیدا شده یا باید تکرار بعدی هم انجام شود. 

صفحه 6:
( 0 Minimum Spanning)auwS ‏الف) درختهاى يوشاى‎ (Trees فرض کنید که در برنامه‌ریزی احداث جاده بین شهرهاء می‌خواهیم تعدادی شهر را با جاده به هم وصل کنیم تا امکان رفتن از هر شهر به شهر دیگر با جاده‌های احداث شده ممکن باشد. چنانچه بحث محدودیت بودجه‌ای مطرح باشد. بنابراین در اين برنامه‌ریزی می‌خواهیم حداقل جاده را از نظر طولی احداث کنیم. ر ادامه بهدنبال الگوریتمی هستیم که مسائلی از این قبیل را حل اکن 

صفحه 7:
الف) درخت‌های پوشای کمینه اگر ارتباط بین شهرها را با گراف نمایش دهیم ... گراف حاصل جهت‌دار ‎Shel b Sle cons directed)‏ یک جاده بين هر دو شهر امکان رفت‌وآمد از هر دو شهر در این جاده وجود دارد. به گراف بدون جهت‌داری متصل (۲01۱۳66160) گفته می‌شود کد ... مسيرى بين هر دو جفت راس وجود داشته باشد. 

صفحه 8:
الف) درخت‌های پوشای کمینه چرخه ساده (0۷016 ‎«simple‏ در هر گراف بدون جهت. مسیری از یک راس به خودش است حداقل شامل سه راس باشد و ... هیچ راس میانی تکراری نباشد. گراف فاقدچرخه (116» ۷): گرافی غیرجهت‌دار است که ... هیچ چرخه ساده‌ای در آن وجود نداشته باشد. درخت (۲66]) گرافی است .. غیرجهت‌دار (۱۳6160 ۱1۳۱0 3 (connected) Jax. فاقد چرخه 01160 26۷) 

صفحه 9:
اگر (۷4,۷5) را حذف کنیم این ‎«pare AF‏ غیرجهت‌دار و وزن‌دار گراف همچنان متصل می‌ماند. 

صفحه 10:
الف) درخت‌های پوشای کمینه این مساله به این صورت بیان می‌شود: حذف یال‌هایی از یک گراف ... وزن‌دار غیرجهت‌دار . _ تا زیرگرافی بدست آید تا ... همچنان تمامی راس‌ها متصل به هم باقی بمانند و مجموع وزن یال‌های باقی‌مانده کمینه گردد. 

صفحه 11:
الف) درخت‌های پوشای کمینه اين مساله می‌تواند کاربردهای متعدد مانند: ساخت جاده در ايجاد شبكههاى مخابراتى در ایجاد شبکه‌های لوله گذاری و 

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

صفحه 13:
الف) درخت‌های پوشای کمینه تعریف: گراف بدون جهت 6 شامل .. مجموعه ۷ از راس‌های 63 و همچنین ... مجموعه ] شامل یالها (که به صورت دو راس نشان داده می‌شود) می‌باشد. G =(V, EF) 

صفحه 14:
الف) درخت‌های پوشای کمینه به اعضای ۷ با ,۷ اشاره می‌کنيم و همچنین ... يال بين رلا ورلا را با .. ‎Vi)‏ , بلا ) نشان مىدهيم. 

صفحه 15:
الف) درخت‌های پوشای کمینه ‎V ={v1,v2, U3, U4, U5}‏ ‎E ={ (v1, v2), (v1, vs); (v2, ¥3) , (v2, v4) » (v3, V4)‏ ‎(v3,05) , (v4, U5)}‏ 

صفحه 16:
الف) درخت‌های پوشای کمینه درخت پوشای ۲ برای 3) تعداد راس‌های یکسان ۷ همانند راس‌های 3) دارد ولی ... مجموعه یال‌های آن (۳) زیر مجموعه ] است. بنابراین درخت پوشا را می‌توانیم به صورت زیر نشان دهیم: T=(V, F) 

صفحه 17:
الف) درخت‌های پوشای کمینه الگوریتم حریصانه سطح بالا مجموعه یالها را باتهیمقار دهیکن// 6 < ۴ while (the instance is ۵۲ 50۱۷6۵(۲ select an edge according to locally optimal consideration; © روا-للنتخاب// ‎if (adding the edge to F does not create Dae)‏ لمکان‌سنجی/| ‎add it;‏ وسی‌له حل/1 ‎if (T = (V, F) is a spanning tree)‏ the instance is solved: 

صفحه 18:
الف) درخت‌های پوشای کمینه- الگوریتم ۱۲۱۳06 الگوریتم پرایم (0۲]06) با مجموعه تهی از ۴ کار را شروع می‌کند. مجوعه ۷ در این الگوریتم شامل راس‌هایی خواهد بود که به درخت پوشای کمینه اضافه شده‌اند و در ابتدا ۷ با راس دلخواهی مثلا (:۷] مقداردهی اولیه می‌شود. نزد بكتر بن راس به ل راسی است که (۱) عضو ۷-۷ است و همچنین ... (۲) به راسی که عضو ۷ است متصل است و (۳) این اتصال با راسی است که حداقل وزن را دارد. 

صفحه 19:
الف) درخت‌های پوشای کمینه- الگوریتم ۱۲۱۳06 در گراف شکل بالاء ۷ نزدیک‌ترین راس به ۷ زمانیکه < ۲ ‎{v,}‏ می‌باشد. نزدیکترین راس به ۷ و یال مربوطه به ۴ اضافه می‌شود. بنابراين در اين حالت. دلا به 54 ‎Fa (Vi, V2)‏ افزوده می‌شود. اين فرايند افزودن نزديكتر راس تا زمانيكه ... ‎Y==V‏ شود ادلمه می‌پابد ‎ ‎ ‎ 

صفحه 20:
الف) درخت‌های پوشای کمینه- الگوریتم ۳۲۱۳6 

صفحه 21:
۳۲۱6 ‏در خت‌های یوشای کمینه- الگور بتم‎ (WI weight on edge if there is an edge between v; and v, ۱۷ ][ ‏[تا‎ 2 ۰ 0 if there is no edge between v; and v; ifi=j 

صفحه 22:
الف) درخت‌های پوشای کمینه- الگوریتم ۳۲۱۲6۵ دو بردار ۵۵۲65 و 01501166 را برای حل این مساله به صورت زیر تعریف می‌کنیم: (۱6۵۲65۲)1. لندیس‌رلسودر ۷ لستکه به ۷ ن زدیکتسر لست 44 Vi ou SLargllonjs bie distance(i) atl. nearest(i) 

صفحه 23:
~ for k=1:n- | 0000 WT(nearest(vnear),vnear)=minv: ۶ WT r))=minvalue; added(vnear)=true; distance(vnear)=Inf; %nearest and distance should be updated. for i=2:n if ~added(i) if WG(i,vnear)<distance(i) distance(i)=WG(i,vnear); nearest(i)=vnear; end end end end end (function WT=prim(WG) n=max(size(WG)); Inf=1000; f*ones(n,n); 2:n nearest‘*)=1; distance(i)=W _,-,., end added false(n,1); added(1)=true; distance(1)=Inf; 

صفحه 24:
الف) درخت‌های پوشای کمینه- الگوریتم ۳۲۱۳6 الگوریتم پرایم مسلما درخت پوشا ایجاد می‌کند. ولی ‎LT‏ لزوما درخت ایجاد شده کمینه است؟ به دلیل اينکه در هر گام نزدیکترین راس به ۷ انتخاب می‌شوده به نظر می‌رسد که درخت ایجاد شده باید کمینه باشد. در این الگوریتم‌ها نیاز است درستی کارکرد الگوریتم اثبات شود. هرچند الگوریتم حریصانه در مقايسه با ديكر الكوريتمها سادهتر است ولى اثبات بهينكى آنها معمولا كار دشوارى است. 

صفحه 25:
الف) درخت‌های پوشای کمینه- الگوریتم ۱۲۷5۱۵ در اين روش به ازای هر ۷ عضو ۷ یک زیرمجموعه مجزا ایجاد می‌شود که تنها شامل یک راس است. سپس یال‌ها که از قبل به ترتیب صعودی مرتب شده‌اند به ترتیب وارسی می‌شوند. چنانچه یالی دو راس در دو مجموعه جدا از هم را به هم متصل کند ... یال مربوطه به ۴ اضافه شده و دو مجموعه که دو راس آن توسط یال به هم متصل شده بودند با هم ادغام می‌شوند. این فرایند تازمانیکه تمامی زیرمجموعه‌ها در یک مجموعه ادغام شوند ادامه می‌يابد. 

صفحه 26:
۱۲۷5۱۵۱ ‏درخت‌های پوشای کمینه- الگوریتم‎ (I Determine a minimum 1. Edges are sorted by weight ——_2. Disjoint sot are created. spanning tree. oe ©) ©) ۷۷2 ۷۷93 ow O © ۷۸۷۵ 5 G) (vous) 6 

صفحه 27:
۱۲۱51۵۱ ‏الف) در خت‌های پوشای کمینه- الگوربتم‎ ۱ 1. Edges are sorted by weight (qe) 1 3. 6099 ‏ها (و۷,,۷)‎ 4, Edge (vs,¥g) is selected. (V5.5) 2 (Wav) 3 (avg) 4 ۷۵ 5 © OQ OQ © = 

صفحه 28:
الف) در خت‌های پوشای کمینه- الگوریتم ۱۲۷5۱۵۱ 1. Edges are sorted by weight ‏و‎ ‎۷2 ‎6. Edge (v.14) s solocted 7. Edge (¥s,va is selected (ve) 3 ‏وی‎ 4 ۳۵ (vou) 6 

صفحه 29:
ب) الگور بتم 61۲3[ برای کهتاه‌ترین مسیر تک مبدا این الگوریتم هم از همان رویکرد الگوریتم پرایم برای مساله درخت پوشای کمینه استفاده می کند. مجموعه ۷ با راسی که کوتاه‌ترین مسیرها تا آن قرار است محاسبه شود مقداردهی اولیه می‌شود. در ادامه این راس ۷ درنظر گرفته می‌شود. مجموعه ۳ را برابر با مجموعه یال‌های موجود در کوتاه‌ترین مسیر از ۷ به بقیه رئوس درنظر می‌گیریم که .. در شروع با تهی مقداردهی اولیه می‌شود. سيبس راس ۷ که نزدیکترین راس به ۷ است را انتخاب می‌کنیم ... راس ۷ را به ۷و یال <۷ ,۷ > به ] اضافه می‌کنيم. یال لا و9 * مستلما گوفاه‌ترین مسیر از ولا با اشسخ. 

صفحه 30:
ب) الگوریتم 91517 برای کهتاه ترین مسیر تک مبدا سپس مسیرهای از ۷ به راس‌های عضو ۷-۷ چک می‌شود که تنها از راس‌های عضو ۷ به عنوان راس میانی استفاده می‌کنند. مسیری,کهباااین رویکزفا بة است میآینه:گوتاه‌تزین, مسیر انست(کة لتق بايد اثبات شود) راسی که در انتهای چنین مسیری قرار دارد به ۷ و ... يالى كه آن راس را در انتهای مسیر قرار می‌دهد به ۴ اضافه می‌شود. این فرایند مادامیکه ... يلير ل شود ادلمه ميهايد پس در انتهاء ۳ شامل ... یال‌های موجود در کوتاه‌ترین مسیر از ۷ به بقيه رتوس خواهد بود. 

صفحه 31:
ب) الگوریتم 91517 برای کهتاه ترین مسیر تک مبدا ‎selected because 2.Vertex vis selected because it‏ موز وم ‎itis nearest to v;. has the shortest path from v, using‏ وو وسو اه ‎‘Compu‏ only vertices in {v5} a8 intermediates. © Xe 

صفحه 32:
ب) الگوریتم 91517 برای کهتاه ترین مسیر تک مبدا 111 4.The shortest path trom vs ۵ ‏فأ‎ ‎has the shortest path from ¥ UM ‏ب وا‎ ting only verioes in (v4, 4) as intermediates 

صفحه 33:
ب) الگوریتم 91517 برای کهتاه ترین مسیر تک مبدا براى نوشتن الكوريتم اين مساله هم نياز به تعريف تعدادى متغير است: ‎length[i] =‏ طول كوتادترين مسير محاسبه شده فعلى (تا هر تكرار در الكوريتم خريصانه) از ‎sa Vj ag Vi‏ فقط از راس‌های عضو ۷ به عنوان راس میانی استفاده می‌کند. ‎touch[i] =‏ انديس راس ۷ در ۷ که ... یال <۷ ,۷ > آخرین یال در کوتاه‌ترین مسیر جاری از :۷ به ,۷ باشد که ... تنها از راس‌های عضو ۷ به عنوان راس میانی استفاده کرده است. ‎ ‎ ‎ 

صفحه 34:
for k=1:n [minvalue, vnear]=min(length); Y(vnear)=true; S(vnear)=minvalue; %length(vn ٠ for i=l. if ~added(i) ‏اميه أ سيدا عد‎ +W(vne& jy ‏سحت‎ ‎JONG ccncm anes +W/(vnear,i); touch(i)=vnear; end end end length(vnear)=Inf; end end function S=dijkstra(W,s) n=max(size(W)) Inf=1000; S=Inf*ones(1,n);] for i=1:r touch( length(i)=W(s,i); end Y=false(n,1); Y(s)=true; length(s)=Inf; 

صفحه 35:
ج) زمان‌بندی (56۳06001109) درنظر خدمات ید که در یک آرایشگاه تعدادی مشتری در انتظار دریافت مختلفی مانند اصلاح ساده. اصلاح با شستشو رنگ مو و ... باشند. هر خدمتى در آرايشكاه زمان يكسانى با بقيه خدمات ندارد و آرايشكر می‌داند که هر خدمتی چه مقدار به طول خواهد انجامید. در این جا هدف آن است تا مشتریان به ترتیبی سرویس بگیرند که مجموع کل زمان‌های صرف شده برای انتظار و سرویس گرفتن کمینه گردد. زمان‌بندی که هدف بالا را تامین کند. زمان‌بندی بهینه نامیده می‌شود. 

صفحه 36:
ج) زمان‌بندی اگر زمان سپری شده برای انتظار و سرویس گرفتن هر مشتری را زمان ‎(time in the system) pi.‏ بنامیم ... مساله در اینجا کمینه کردن تمامی زمان‌های سیستم (01۳06 ‎Total‏ ‎bein the system‏ این مساله کاربردهای گسترده‌ای مانند ... زمان‌بندی دسترسی کاربران به دیسک به‌گونه‌ایکه کل زمان سپری شده برای انتظار و سرویس گرفتن کمینه گردد. 

صفحه 37:
ج) زمان‌بندی نوع دیگری از مساله زمان‌بندی وجود دارد که در آن ... هر کار (سرویس امشتری) زمان یکسانی را برای انجام شدن نیاز دارند ولی ... هر کار مهلت (063011۳06) ای برای شروع شدن دارد که ... درصورتیکه شروع شود. منفعت (0۲083) مرتبط با آن حاصل می‌شود. در اين مساله زمان‌بندی هدف آن است تا ... کارها به گونه‌ای زمان‌بندی شوند که بیشترین منفعت (101۵1 11 بدست آید. بنابراین در ادامه ابتدا مساله زمان‌بندی بدون مهلت و سپس زمان‌بندی با مهلت ارائه خواهد گردید. 

صفحه 38:
ج) زمان‌بندی -کمینه‌سازی زمان کل فرض کنید سه کار و زمان پاسخ‌دهی به آنها به صورت زیر وجود دارد: ‎and tz = 4.‏ ,10 = وا ,5= 1 اكر اين سه كار به ترتیب ۱ و ۲ و ۴ زمان‌بندی شوند, زمان سیستم هر کدام به صورت زیر می‌باشد: ‎Job Time in the System ‎1 5 (service time) 2 5 (wait for job 1) + 10 (service time) 3 5 (wait for job 1) + 10 (wait for job 2) + 4 ‎ ‎ ‎ ‎(service time) ‏بنابراین تمامی زمان‌های سیستم به صورت زیر می‌باشد:‎ ‎5 ۲ 5) + (5+10) + (5+10+4) —39 ‎Time for Time for ‘Time for ‎© ‏«وز‎ 1 job 2 job 3 ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 39:
ج) زمان‌بندی -کمینه‌سازی زمان کل ۰ < وا ‎and‏ ,10 < وا چنانچه تمامی زمان‌بندی‌های ممکن برای سه کار را ایجاد کنیم و برای هر 7 تمامی زمان‌های سیستم را محاسبه کنیم. جدول زیر به دست خواهد آ Schedu Total Time in the System le , 2, 3[ | 5+)5+10(+)5+10+4( 2 9 3,2) [5+(5+4)+(5+4410) = 33 , 1, 3[ | 10+)10+5(+)10+5+4( - 4 [2, 3, 1] | 10+(10+4)+(10+4+5) = 43 1, 2) [44+(4+5)+(4+5410) = 32 2,1) [4+(4+10)+(44+10+5) = 37 که زمان‌بندی [۱,۲, ۲ با تمامی زمان سیستم ۲۲ بهینه خواهد بود. 

صفحه 40:
ج) زمان‌بندی -کمینه‌سازی زمان کل واضح است الگوریتمی که به صورت ۴0۲66 0۲۷06 تمامی زمان‌بندی‌های ممکن را درنظر بگیرد دارای پیچیدگی محاسباتی ... فاکتوریل خواهد بود. همانگونه که مشخص است در مثال قبلی زمان‌بندی بهینه زمان حاصل شد که ... کار با کمترین زمان سرویس ابتدا انجام شد و پس از آن .-. کار با زمان سرویس کمتر و -. چنین به نظر می‌رسد که چنین زمان‌بندی‌ای بهینه خواهد بود. 

صفحه 41:
ج) زمان‌بندی-کمینه‌سازی زمان کل ابتدا کارها را به ترتیب صعودی مرتب می‌کنیم و ‎while ( the instance is not solved)‏ 1 schedule the next job;// selection procedure and // feasibility check if (there are no more jobs) // solution check the instance is solved; } W (n) € O(nign). 

صفحه 42:
ج) زمان‌بندی -کمینه ن‌بندی - کمین ‎j‏ ‏ینه‌سازی زمان زمان کل قضبه: تنها زمان‌بندی که ۵ ۳ ب می‌شود کل زمان 5 زمان سیسیم ۵ زمان‌بند زمان‌بندی است است که کا ارها به ترتیب صعود. Ss سرویس داده شون ه شوند. 

صفحه 43:
ج) زمان‌بندی-کمینه‌سازی زمان کل اثبات: برای ۱ < .1 - 2 ك / را زمان سرویس برای آامین کار درنظر که در یک زمان‌بندی بهینه قرار دارد. می‌بایست نشان دهیم که در اين زمان‌بندی ... کارها بر اساس زمان سرویسشان به ترتیب صعودی قرار گرفته‌اند. اثبات را با برهان خلف انجام می‌دهیم. 

صفحه 44:
ج) زمان‌بندی -کمینه‌سازی زمان کل چنانچه کارها کارهای به ترتیب صعودی مرتب نباشند آنگه .. برای حداقل یک 1 - 0 ك / ك 1 . خواهيم داشت .. ۰ < با 

صفحه 45:
ج) زمان‌بندی-کمینه‌سازی زمان کل می‌توان ترتیب اولیه از کارها را با جابجا كردن كار أام و 1+1 ام تغيير ‎a dle‏ © 

صفحه 46:
ج) زمان‌بندی-کمینه‌سازی زمان کل ‎wn‏ اگر آ برابر با کل زمان سیستم در زمان‌بندی اولیه باشد و برابر با کل زمان‌بندی سیستم در ترتیب جدید باشد آنگاه خواهیم داشت ... ‎T=T+tyi—t‏ ‏و چون 7+1 < با eT: که فرض بهینه بودن زمان‌بندی اولیه را نقض می‌کند. 

صفحه 47:
ج) زمان‌بندی با مهلت معین در این زمابندی هر کاری یک واحد زمان نیاز خواهد داشت تا به اتمام برسد. همچنین هر کاری یک مهلت و یک منفعت دارد. اگر کار قبل از مهلت و با در زمان مهلتش آغاز شود در اين صورت ... منفعتش برای سیستم حاصل خواهد شد. هدف این است تا کارهای به گونه‌ای زمان‌بندی شوند که بیشترین منفعت حاصل شود. در اين زمان‌بندی الزامی وجود ندارد که تمامی کارها در زمان‌بندی وجود داشته باشند. همچنین نبایست زمان‌بندی ایجاد کنیم که در آن کاری بعد از مهلتش زمان‌بندی شود. ۱ ۱ چنین زمان‌بندی را غیرممکن (۱۳۳۱0055/016) می‌نامیم. 

صفحه 48:
ج) زمان‌بندی با مهلت معین فرض کنید جدول زیر از کارهاء مهلت و منفعتشان را داریم: Job | Deadlin | Profit e 1 2 30 2 1 35 3 2 25 4 1 40 وقتی گفته می‌شود که کار ۱ دارای مهلت ۲ است یعنی ... این کار می‌تواند در زمان ۱ یا ۲ شروع شود. در این جا زمان صفر وجود ندارد. در اين جدول مثلا کار ۲ به دلیل اینکه دارای مهلت ۱ است فقط می‌تواند در زمان ۱ شروع شود. 

صفحه 49:
ج) زمان‌بندی با مهلت معین Profit 30 35 25 40 Total Profit Deadlin e PiNfely Job بان نت | جح زمان‌بندی‌های ممکن و کل منعت بدست آمده از آن در ادامه آمده است ... ‎Schedule‏ 11, 3] 

صفحه 50:
| [Job | Deadlin | Profit e 1 2 30 ‏ج) زمان‌بندی با مهلت معین‎ 2 1 35 3 2 25 4 1 40 ترتيبى از کارها ممکن (560۱666 6851016) گفته می‌شود اگر تمامى كارها در آن ترتيب بر اساس مهلتشان شروع شوند. منقاة تويب ‎adil See peed LPN]‏ [05 ]ارتب «ممكلخ تمن باذ مجموعه‌ای از کارها مجموعه ممکن (566 ۲625016) نامیده می‌شود اگر ... حداقل یک ترتیب ممکن از کارها بتوان از آن مجموعه استخراج کرد. مجموعه (۰]۲,۴ مجموعه‌ای ... ممکن نیست چرا که هیچ ترتیب ممکنی نمی‌توان از آن استخراج کرد. 

صفحه 51:
ج) زمان‌بندی با مهلت معین هدف ما در این مساله یافتن ترتیبی ممکن است که ... بیشترین:مجموغ متفعت زا ذارازباشقو مجموعه کارهای آن را ... مجموعه بهینه از کارها می‌نامیم. 

صفحه 52:
ج) زمان‌بندی با مهلت معین الگوریتم حریصانه سطح بالا کارها را بر اساس منفعتشان به صورت نزولی مرتب می‌کنیم 5 - 6 while (the instance is not solved) { select next job; // selection procedure if (S is feasible with this job added) // feasibility check add this job to S; if (there are no more jobs) // solution check the instance is solved; 1 

صفحه 53:
ج) زمان‌بندی با مهلت معین .کارها پر اساس منفعت مرتب‌شده هستند ۰ ۵ 56 وا 5 Sis set to {1} because the sequence [1] is feasible. Sis set to {1,2} because the sequence [2,1] is feasible. {1,2, 3} is rejected because there is no feasible sequence for this set. Sis set to {1,2,4} because the sequence [2,1,4] is feasible. {1,2,4,5}is rejected because there is no feasible sequence for this set. {1,2,4,6}is rejected because there is no feasible sequence for this set. {1,2,4,7}is rejected because there is no feasible SaqueNS ۳۸۴۴ ‏دراین تال 5 در نع‎ Profit 40 55 30 25 20 15 10 Deadli ne بات | نت رم زیت ازیو Job sJoalulalwinfe 

صفحه 54:
ج) زمان‌بندی با مهلت معین به گوه‌ای اضافه می‌کند که در دنباله یه دست آمده کارها بر اساس مهلتشان مرتب باشند function K=addJ,i,deadline) n=length(j); for r=1:n if deadline(j(r))<=deadline(i) ‏)ل )كا‎ else K(r) =i; K(r+1:n+1)=J(r:n); break; end pee function J=schedule(deadline) n=length(deadline); JQ)=1; for i=2:n K=add(),i,deadline); if feasible(K, deadline) J=K; end end end function r=feasible(K,deadline) =length(K); :n if deadline(K(i))> i r=0; break; end end end 

صفحه 55:
ج) زمان‌بندی با مهلت معین پیچیدگی محاسباتی مرتب کردن کارها بر اساس منافعشان ‎wb. © (nN Ign)‏ در هر تکرار از حلقه تابع 6الا560 .. برای اینکه امین کار را به ‏ اضافه کنیم. حداکثر به أ مقایسه نیاز است. همچنین حداکثر أ مقایسه نیاز است تا ممکن بودن > را بررسی کنیم. بنابراین در بدترین حالت پیچیدگی محاسباتی این الگوریتم برابر است با : n Slt) + iJ€ O(n?) i=2 

صفحه 56:
مسئله وله پشتی صفر و یک 0 ‎w; = weight of item;‏ ‎Pi = profit of item;‏ ‎W = maximum weight the knapsack can hold‏ که ,۷۷ و ,0 و ۷۷ همگی اعداد مثبتی هستند. می‌خواهیم زیر مجموعه ۸ از 5 را به گونه‌ای مشخص کنیم که ... 2 Pi is maximized subject to ۳13 ‏:نا‎ > ۷ و ۰4 

صفحه 57:
۰) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک اگر بخواهیم رویکرد ‎brute-force‏ را درنظر بكيريم ... باید تمامی زیرمجموعه‌های 5 را درنظر بگیریم و .. از اونهایی که مجموع وزنشون از ۷۷ بیشتر است صرفنظر کنیم و ... از زیرمجموعه‌های باقیمانده اونی که بیشترین مجموع منفعت دارد را به عنوان پاسخ انتخاب کنیم. پیچیدگی محاسباتی این روش بادرنظر گرفتن 0 آیتم ... asl ‏مين‎ 7 

صفحه 58:
۰) الگوربتم حریصانه در مسئله کوله پشتی صفر و یک اولین راه حل حریصانه که شاید برای این مساله به ذهن برسد آن است که.. تمامی آیتم‌ها را بر اساس منفعتشان به صورت نزولی مرتب کنیم و ... به ترتیب آیتم‌ها را از مجموعه مرتب‌شده برداریم مادامیکه ... مجموع وزنشان از ۷۷ بیشتر نشود. این استراتژی زمانیکه آیتم‌های با منفعت بالا وزن بیشتری در مقایسه با منفعتشون دارند مناسب نمی‌باشد. 

صفحه 59:
ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک احتمالا استراتزی بعدی اين می‌تواند باشد که آیتم‌های سبک‌تر را ابتدا برداریم ~ این استراتژزی هم زمانی که آیتم‌های سبک منفعت کمی داشته باشند به شکست می‌انجامد. 

صفحه 60:
۰) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک راه حل حریصانه مناسب این است که ... آیتم‌ها را بر اساین منفعت واحد وزنشان به صورت نزولی مرثب کنیم 3 1 بت را تا زمانیکه مجموع وزنشان از ۷۷ بیشتر نشود برداریم. 

صفحه 61:
ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک بو فد و و 5 :۶ 810 < item, : 5 30 Ib $140 Max. ‘$60 Le] a Item 1 ttem 2 ttem 3 Knapsack Greedy Optimal solution solution 

صفحه 62:
۰) الگوریتم حریصانه در مسئله کوله پشتی کسری ‎(Fractional)‏ در مساله کوله پشتی کسری چنانچه برداشتن کل آیتم میسر نیست. می‌توان بخشی از آن را نیز برداشت. مثلا در مثال قبل ... ۰ $50 + $140 + 10 ($60) = $220. بنابراین هیچ فضایی هدر نمی‌رود. پس همواره حل بهینه را خواهیم داشت. 

روش حریصانه()Greedy Approach رویک ردی ک ه روش حریص انه ب رای ح ل مس ائل بهینه‌س ازی دارد ش امل تصمیم‌گیری‌های پشت‌سرهم است ک ه ب رای ه ر تص میم‌گیری تنه ا از اطالع ات بدست آمده تا آن مرحله استفاده می‌کند. بنابراین اصطالحا گفته می‌شود ک ه تص میم‌گیری ب ر اس اس انتخاب‌ه ایی ص ورت می‌پذیرد که به صورت محلی بهینه هستند. در این رویکرد حل مساله امیدواریم تا به راه حل بهینه برسیم .اما ... این راه حل بهینه دربرخی موارد بدست نمی‌آید. در این رویکرد برای هر الگوریتم پیشنهادی باید نشان داده شود که پاس خ هم واره در تمامی موارد بهینه است. 2 روش حریصانه()Greedy Approach مساله :می‌خواهیم باقی پول مشتری را با تعدادی سکه (اسکناس) پرداخت کنیم )تازمانیکه سکه‌های بیشتری وجود دارد و مساله هنوز حل نشده است ( while { 1 ;//selection procedureبزرگترین سکه باقیمانده را بردار )//feasibilityاضافه کردن سکه سبب می‌شود مجموع سکه‌های برداشته‌شده از مبلغ بدهی بیشتر شود( I f 2 ‏check ;از اون سکه صرفنظر کن ‏else ;سکه را اضافه کن 3 )//solution checkاگر مجموع سکه‌های برداشته شده با بدهی برابری می‌کند( I f ;مساله حل شده است } 3 روش حریصانه()Greedy Approach در حل مسائل با شیوه حریصانه هر تکرار از سه بخش تشکیل شده است: الف) روال انتخاب ()selection procedure ب) امکان‌سنجی ( )feasibility check ج) بررسی راه‌حل ( )solution check 4 روش حریصانه()Greedy Approach در حل مسائل با شیوه حریصانه هر تکرار از سه بخش تشکیل شده است: الف) روال انتخاب ()selection procedure با معیاری آیتم بعدی را انتخاب می‌کند تا به مجموعه راه‌حل اضافه شود. توجه شود که معیار انتخاب مسلما بر اساس اطالعات تا هر مرحله است ... هرچند سعی می‌شود تا بهینه باشد ولی چون ... از اطالعات فقط تا همان مرحله استفاده می‌کند گفته می‌شود که معیار بهینگی محلی است. ب) امکان‌سنجی ( )feasibility check با اضافه شدن آیتم جدید به مجموعه پاسخ ،کنترل می‌شود که آیا با تکمیل کردن این مجموعه می‌توان به پاسخ رسید یا خیر ج) بررسی راه‌حل کنترل می‌شود که با بدست آمدن مجموعه جدید آیا پاسخ پیدا شده یا باید تکرار بعدی هم انجام شود. 5 الف) درخت‌های پوشای کمینه(Minimum Spanning )Trees فرض کنید که در برنامه‌ریزی احداث جاده بین شهرها ،می‌خواهیم تعدادی شهر را با جاده به هم وصل کنیم تا امکان رفتن از هر شهر به شهر دیگر با جاده‌های احداث شده ممکن باشد. چنانچه بحث محدودیت بودجه‌ای مطرح باشد ،بنابراین در این برنامه‌ریزی می‌خواهیم حداقل جاده را از نظر طولی احداث کنیم. در ادامه به دنبال الگوریتمی هستیم که مسائلی از این قبیل را حل کند. 6 الف) درخت‌های پوشای کمینه اگر ارتباط بین شهرها را با گراف نمایش دهیم ... گراف حاصل جهت‌دار ( )directedنیست .چراکه با احداث یک جاده بین هر دو شهر امکان رفت‌وآمد از هر دو شهر در این جاده وجود دارد. به گراف بدون جهت‌داری متصل ( )connectedگفته می‌شود که ... مسیری بین هر دو جفت راس وجود داشته باشد. 7 الف) درخت‌های پوشای کمینه چرخه ساده (... :)simple cycle در هر گراف بدون جهت ،مسیری از یک راس به خودش است چنانچه ... حداقل شامل سه راس باشد و ... هیچ راس میانی تکراری نباشد. گراف فاقدچرخه ( :)Acyclicگرافی غیرجهت‌دار است که ... هیچ چرخه ساده‌ای در آن وجود نداشته باشد. درخت ( )Treeگرافی است ... غیرجهت‌دار (،)undirected متصل ( )connectedو فاقد چرخه ()acyclic 8 اگر ( )v4,v5را حذف کنیم این گراف همچنان متصل می‌ماند. درخت پوشای کمینه گراف متصل، غیرجهت‌دار و وزن‌دار درختی پوشا برای گراف باال 9 الف) درخت‌های پوشای کمینه این مساله به این صورت بیان می‌شود: حذف یال‌هایی از یک گراِف ... متصِل وزن‌داِر غیرجهت‌دار تا زیرگرافی بدست آید تا ... همچنان تمامی راس‌ها متصل به هم باقی بمانند و مجموع وزن یال‌های باقی‌مانده کمینه گردد. 10 الف) درخت‌های پوشای کمینه این مساله می‌تواند کاربردهای متعدد مانند: ساخت جاده در ایجاد شبکه‌های مخابراتی در ایجاد شبکه‌های لوله‌گذاری و ... 11 الف) درخت‌های پوشای کمینه برای اینکه زیرگرافی شرایط گفته‌شده را داشته باشد حتما بایستی ... درخت باشد .چراکه ... اگر زیرگرافی این شرایط را داشته باشد و درخت نباشد، بنابراین در آن حداقل یک چرخه ساده وجود خواهد داشت که ... می‌توانیم یکی از یال‌های چرخه را حذف کنیم و گراف حاصل همچنان ... متصل با مجموع وزن یال‌های کمتر باقی بماند 12 الف) درخت‌های پوشای کمینه تعریف: گراف بدون جهِت Gشامل ... مجموعه Vاز راس‌های Gو همچنین ... مجموعه Eشامل یالها (که به صورت دو راس نشان داده می‌شود) می‌باشد. 13 الف) درخت‌های پوشای کمینه به اعضای Vبا viاشاره می‌کنیم و همچنین ... یال بین viو vjرا با ... ( ) vi , vjنشان می‌دهیم. 14 الف) درخت‌های پوشای کمینه 15 الف) درخت‌های پوشای کمینه درخت پوشای Tبرای Gتعداد راس‌های یکسان Vهمانند راس‌های Gدارد ولی ... مجموعه یال‌های آن ( ،)Fزیر مجموعه Eاست. بنابراین درخت پوشا را می‌توانیم به صورت زیر نشان دهیم: )T=(V, F 16 الف) درخت‌های پوشای کمینه F=Ø الگوریتم حریصانه سطح باال // مجموعه یالها را با تهی مقدار دهی کن while (the instance is not solved){ select an edge according to locally optimal consideration; // روال انتخاب 1 if (adding the edge to F does not create a cycle) 2 add it; // امکان‌سنجی if (T = (V, F ) is a spanning tree) // بررسی راه حل the instance is solved; } 17 3 الف) درخت‌های پوشای کمینه -الگوریتم Prime الگوریتم پرایم ( )Primeبا مجموعه تهی از Fکار را شروع می‌کند. مجوعه Yدر این الگوریتم شامل راس‌هایی خواهد بود که به درخت پوشای کمینه اضافه شده‌اند و در ابتدا Yبا راس دلخواهی مثال { }v1مقداردهی اولیه می‌شود. نزدیکترین راس به Yراسی است که ( )1عضو V-Yاست و همچنین ... ( )2به راسی که عضو Yاست متصل است و ( )3این اتصال با راسی است که ... حداقل وزن را دارد. 18 الف) درخت‌های پوشای کمینه -الگوریتم Prime در گراف شکل باال v2 ،نزدیک‌ترین راس به ،Yزمانیکه = Y } {v1می‌باشد. نزدیکترین راس به Yو یال مربوطه به Fاضافه می‌شود. بنابراین در این حالت v2 ،به Yو ( )v1, v2به Fافزوده می‌شود. این فرایند افزودن نزدیکتر راس تا زمانیکه ... Y==Vشود ادامه می‌یابد. 19 الف) درخت‌های پوشای کمینه -الگوریتم Prime 20 الف) درخت‌های پوشای کمینه -الگوریتم Prime 21 الف) درخت‌های پوشای کمینه -الگوریتم Prime دو بردار nearestو distanceرا برای حل این مساله به صورت زیر تعریف می‌کنیم: ) ،nearest(iاندیس راسی در Yاست که به viنزدیک‌تر است. ) ،distance(iمقدار وزن یال متصل‌کننده viبه )nearest(i می‌باشد. 22 function WT=prim(WG) n=max(size(WG)); Inf=1000; WT=Inf*ones(n,n); for i=2:n nearest(i)=1; for k=1:n-1 3 [minvalue,vnear ]=min(distance); 2 1 WT(nearest(vnear),vnear)=minvalue; WT(vnear,nearest(vnear))=minvalue; added(vnear)=true; distance(vnear)=Inf; %nearest and distance should be updated. distance(i)=WG(1,i); for i=2:n if ~added(i) end if WG(i,vnear)<distance(i) added=false(n,1); distance(i)=WG(i,vnear); nearest(i)=vnear; added(1)=true; distance(1)=Inf; end end end end 23 end الف) درخت‌های پوشای کمینه -الگوریتم Prime الگوریتم پرایم مسلما درخت پوشا ایجاد می‌کند. ولی آیا لزوما درخت ایجاد شده کمینه است؟ به دلیل اینکه در هر گام نزدیکترین راس به Yانتخاب می‌شود ،به نظر می‌رسد که درخت ایجاد شده باید کمینه باشد. در این الگوریتم‌ها نیاز است درستی کارکرد الگوریتم اثبات شود. هرچند الگوریتم حریصانه در مقایسه با دیگر الگوریتم‌ها ساده‌تر است ولی اثبات بهینگی آنها معموال کار دشواری است. 24 الف) درخت‌های پوشای کمینه -الگوریتم Kruskal در این روش به ازای هر viعضو Vیک زیرمجموعه مجزا ایجاد می‌شود که تنها شامل یک راس است. سپس یال‌ها که از قبل به ترتیب صعودی مرتب شده‌اند به ترتیب وارسی می‌شوند. چنانچه یالی دو راس در دو مجموعه جدا از هم را به هم متصل کند ... یال مربوطه به Fاضافه شده و دو مجموعه که دو راس آن توسط یال به هم متصل شده بودند با هم ادغام می‌شوند. این فرایند تازمانیکه تمامی زیرمجموعه‌ها در یک مجموعه ادغام شوند ادامه می‌یابد. 25 الف) درخت‌های پوشای کمینه -الگوریتم Kruskal 26 الف) درخت‌های پوشای کمینه -الگوریتم Kruskal 27 الف) درخت‌های پوشای کمینه -الگوریتم Kruskal 28 ب) الگوریتم Dijkstraبرای کوتاه‌ترین مسیر تک مبدا این الگوریتم هم از همان رویکرد الگوریتم پرایم برای مساله درخت پوشای کمینه استفاده می‌کند. مجموعه Yبا راسی که کوتاه‌ترین مسیرها تا آن قرار است محاسبه شود مقداردهی اولیه می‌شود. در ادامه این راس v1درنظر گرفته می‌شود. مجموعه Fرا برابر با مجموعه یال‌های موجود در کوتاه‌ترین مسیر از v1به بقیه رئوس درنظر می‌گیریم که ... در شروع با تهی مقداردهی اولیه می‌شود. سپس راس vکه نزدیکترین راس به v1است را انتخاب می‌کنیم ... راس vرا به Yو یال < >v1, vبه Fاضافه می‌کنیم. یال < >v1, vمسلما کوتاه‌ترین مسیر از v1به vاست. 29 ب) الگوریتم Dijkstraبرای کوتاه‌ترین مسیر تک مبدا سپس مسیرهای از v1به راس‌های عضو V-Yچک می‌شود که تنها از راس‌های عضو Yبه عنوان راس میانی استفاده می‌کنند. مسیری که با این رویکرد به دست می‌آید ،کوتاه‌ترین مسیر است (که البته باید اثبات شود) راسی که در انتهای چنین مسیری قرار دارد به Yو ... یالی که آن راس را در انتهای مسیر قرار می‌دهد به Fاضافه می‌شود. این فرایند مادامیکه .... Yبرابر Vشود ادامه می‌یابد. پس در انتها F ،شامل ... یال‌های موجود در کوتاه‌ترین مسیر از v1به بقیه رئوس خواهد بود. 30 ب) الگوریتم Dijkstraبرای کوتاه‌ترین مسیر تک مبدا 31 ب) الگوریتم Dijkstraبرای کوتاه‌ترین مسیر تک مبدا 32 ب) الگوریتم Dijkstraبرای کوتاه‌ترین مسیر تک مبدا برای نوشتن الگوریتم این مساله هم نیاز به تعریف تعدادی متغیر است: = ]length[i طول کوتاه‌ترین مسیر محاسبه شده فعلی (تا هر تکرار در الگوریتم حریصانه) از v1 به viکه ... فقط از راس‌های عضو Yبه عنوان راس میانی استفاده می‌کند. = ]touch[i اندیس راس vدر Yکه ... یال < >v, viآخرین یال در کوتاه‌ترین مسیر جاری از v1به viباشد که ... تنها از راس‌های عضو Yبه عنوان راس میانی استفاده کرده است. 33 function S=dijkstra(W,s) n=max(size(W)); Inf=1000; S=I nf*ones(1,n); for i=1:n touch(i)=s; length(i)=W(s,i); end Y=false(n,1); Y(s)=true; length(s)=I nf; 34 for k=1:n [minvalue,vnear]=min(length); Y(vnear)=true; S(vnear)=minvalue; %length(vnear) for i=1:n if ~added(i) if length(vnear) +W(vnear,i)<length(i) length(i)=length(vnear) +W(vnear,i); touch(i)=vnear; end end end length(vnear)=Inf; end end ج) زمان‌بندی ()Scheduling درنظر بگیرید که در یک آرایشگاه تعدادی مشتری در انتظار دریافت خدمات مختلفی مانند اصالح ساده ،اصالح با شستشو ،رنگ مو و ... باشند. هر خدمتی در آرایشگاه زمان یکسانی با بقیه خدمات ندارد و آرایشگر می‌داند که هر خدمتی چه مقدار به طول خواهد انجامید. در این جا هدف آن است تا مشتریان به ترتیبی سرویس بگیرند که مجموع کل زمان‌های صرف شده برای انتظار و سرویس گرفتن کمینه گردد. زمان‌بندی که هدف باال را تامین کند ،زمان‌بندی بهینه نامیده می‌شود. 35 ج) زمان‌بندی اگر زمان سپری شده برای انتظار و سرویس‌گرفتن هر مشتری را زمان سیستم ( )time in the systemبنامیم ... مساله در اینجا کمینه کردن تمامی زمان‌های سیستم ( total )time in the systemمی‌باشد. این مساله کاربردهای گسترده‌ای مانند ... زمان‌بندی دسترسی کاربران به دیسک به‌گونه‌ایکه کل زمان سپری شده برای انتظار و سرویس‌گرفتن کمینه گردد. 36 ج) زمان‌بندی نوع دیگری از مساله زمان‌بندی وجود دارد که در آن ... هر کار (سرویس/مشتری) زمان یکسانی را برای انجام شدن نیاز دارند ولی ... هر کار مهلت ( )deadlineای برای شروع شدن دارد که ... درصورتیکه شروع شود ،منفعت ( )profitمرتبط با آن حاصل می‌شود. در این مساله زمان‌بندی هدف آن است تا ... کارها به گونه‌ای زمان‌بندی شوند که بیشترین منفعت ( total )profitبدست آید. بنابراین در ادامه ابتدا مساله زمان‌بندی بدون مهلت و سپس زمان‌بندی با مهلت ارائه خواهد گردید. 37 ج) زمان‌بندی-کمینه‌سازی زمان کل فرض کنید سه کار و زمان پاسخ‌دهی به آنها به صورت زیر وجود دارد: اگر این سه کار به ترتیب 1و 2و 3زمان‌بندی شوند ،زمان سیستم هر کدام به صورت زیر می‌باشد: ‏Time in the System ‏J ob )5 (service time 1 )5 (wait for job 1) + 10 (service time 2 5 (wait for job 1) + 10 (wait for job 2) + 4 )(service time بنابراین تمامی زمان‌های سیستم به صورت زیر می‌باشد: 3 38 ج) زمان‌بندی-کمینه‌سازی زمان کل چنانچه تمامی زمان‌بندی‌های ممکن برای سه کار را ایجاد کنیم و برای هر ترتیب تمامی زمان‌های سیستم را محاسبه کنیم ،جدول زیر به دست خواهد آمد: ‏Total Time in the System ‏Schedu ‏le 5+(5+10)+(5+10+4) = 39 ][1, 2, 3 5+(5+4)+(5+4+10) = 33 ][1, 3, 2 10+(10+5)+(10+5+4) = 44 ][2, 1, 3 10+(10+4)+(10+4+5) = 43 ][2, 3, 1 4+(4+5)+(4+5+10) = 32 ][3, 1, 2 4+(4+10)+(4+10+5) = 37 ][3, 2, 1 که زمان‌بندی [ ]2 ,1 ,3با تمامی زمان سیستم 32بهینه خواهد بود. 39 ج) زمان‌بندی-کمینه‌سازی زمان کل واضح است الگوریتمی که به صورت brute forceتمامی زمان‌بندی‌های ممکن را درنظر بگیرد دارای پیچیدگی محاسباتی ... فاکتوریل خواهد بود. همانگونه که مشخص است در مثال قبلی زمان‌بندی بهینه زمان حاصل شد که ... کار با کمترین زمان سرویس ابتدا انجام شد و پس از آن .... کار با زمان سرویس کمتر و ... چنین به نظر می‌رسد که چنین زمان‌بندی‌ای بهینه خواهد بود. 40 کمینه‌سازی زمان کل-ج) زمان‌بندی ابتدا کارها را به ترتیب صعودی مرتب می‌کنیم و while ( the instance is not solved) { schedule the next job;// selection procedure and // feasibility check if ( there are no more jobs) // solution check the instance is solved; } 41 ج) زمان‌بندی-کمینه‌سازی زمان کل قضیه: تنها زمان‌بندی که سبب می‌شود کل زمان سیستم کمینه شود ... زمان‌بندی است که کارها به ترتیب صعودی سرویس داده شوند. 42 ج) زمان‌بندی-کمینه‌سازی زمان کل اثبات: برای i ≤ n − 1، ti ≤ 1را زمان سرویس برای iامین کار درنظر بگیرید که ... که در یک زمان‌بندی بهینه قرار دارد. می‌بایست نشان دهیم که در این زمان‌بندی ... کارها بر اساس زمان سرویسشان به ترتیب صعودی قرار گرفته‌اند. اثبات را با برهان خلف انجام می‌دهیم. 43 ج) زمان‌بندی-کمینه‌سازی زمان کل چنانچه کارها کارهای به ترتیب صعودی مرتب نباشند آنگاه ... برای حداقل یک i، 1 ≤ i ≤ n − 1خواهیم داشت ... 44 ج) زمان‌بندی-کمینه‌سازی زمان کل می‌توان ترتیب اولیه از کارها را با جابجا کردن کار iام و i+1ام تغییر داد ... 45 ج) زمان‌بندی-کمینه‌سازی زمان کل بنابراین اگر Tبرابر با کل زمان سیستم در زمان‌بندی اولیه باشد و ... ’T برابر با کل زمان‌بندی سیستم در ترتیب جدید باشد آنگاه خواهیم داشت ... و چون ti > ti+1 پس که فرض بهینه بودن زمان‌بندی اولیه را نقض می‌کند. 46 ج) زمان‌بندی با مهلت معین در این زما‌بندی هر کاری یک واحد زمان نیاز خواهد داشت تا به اتمام برسد. همچنین هر کاری یک مهلت و یک منفعت دارد. اگر کار قبل از مهلت و یا در زمان مهلتش آغاز شود در این صورت ... منفعتش برای سیستم حاصل خواهد شد. هدف این است تا کارهای به گونه‌ای زمان‌بندی شوند که بیشترین منفعت حاصل شود. در این زمان‌بندی الزامی وجود ندارد که تمامی کارها در زمان‌بندی وجود داشته باشند. همچنین نبایست زمان‌بندی ایجاد کنیم که در آن کاری بعد از مهلتش زمان‌بندی شود. چنین زمان‌بندی را غیرممکن ( )impossibleمی‌نامیم. 47 ج) زمان‌بندی با مهلت معین فرض کنید جدول زیر از کارها ،مهلت و منفعتشان را داریم: ‏Profit ‏Deadlin ‏e ‏Job 30 2 1 35 1 2 25 2 3 40 1 4 وقتی گفته می‌شود که کار 1دارای مهلت 2است یعنی ... این کار می‌تواند در زمان 1یا 2شروع شود. در این جا زمان صفر وجود ندارد. در این جدول مثال کار 2به دلیل اینکه دارای مهلت 1است فقط می‌تواند در زمان 1شروع شود. 48 ج) زمان‌بندی با مهلت معین ‏Profit ‏Deadlin ‏e ‏Job 30 2 1 35 1 2 25 2 3 40 1 4 زمان‌بندی‌های ممکن و کل منعت بدست آمده از آن در ادامه آمده است ... 49 ج) زمان‌بندی با مهلت معین ‏Profit ‏Deadlin ‏e ‏Job 30 2 1 35 1 2 25 2 3 40 1 4 ترتیبی از کارها ممکن ( )feasible sequenceگفته می‌شود اگر .. تمامی کارها در آن ترتیب بر اساس مهلتشان شروع شوند. مثال ترتیب [ ،]4,1ترتیبی ممکن و ترتیب [ ]1,4ترتیبی ممکن نمی‌باشد. مجموعه‌ای از کارها مجموعه ممکن ( )feasible setنامیده می‌شود اگر ... حداقل یک ترتیب ممکن از کارها بتوان از آن مجموعه استخراج کرد. مجموعه { ،}2,4مجموعه‌ای .... ممکن نیست چرا که هیچ ترتیب ممکنی نمی‌توان از آن استخراج کرد. 50 ج) زمان‌بندی با مهلت معین هدف ما در این مساله ،یافتن ترتیبی ممکن است که ... بیشترین مجموع منفعت را دارا باشدو چنین ترتیبی ترتیب بهینه و ... مجموعه کارهای آن را ... مجموعه بهینه از کارها می‌نامیم. 51 ج) زمان‌بندی با مهلت معین الگوریتم حریصانه سطح باال کارها را بر اساس منفعتشان به صورت نزولی مرتب می‌کنیم S=Ø while (the instance is not solved){ select next job; // selection procedure if (S is feasible with this job added) // feasibility check add this job to S; if (there are no more jobs) // solution check the instance is solved; } 52 Job Deadli Profit ne 1 3 40 2 1 35 3 1 30 4 3 25 5 1 20 6 3 15 7 2 10 ج) زمان‌بندی با مهلت معین کارها بر اساس منفعت مرتب‌شده هستند. S is set to Ø. S is set to {1} because the sequence [1] is feasible. S is set to {1,2} because the sequence [2,1] is feasible. {1,2, 3} is rejected because there is no feasible sequence for this set. S is set to {1,2,4} because the sequence [2,1,4] is feasible. {1,2,4,5}is rejected because there is no feasible sequence for this set. {1,2,4,6}is rejected because there is no feasible sequence for this set. {1,2,4,7}is rejected because there is no feasible sequence for this set. .} برابر خواهد شد1,2,4{ در نهایت باS در این مثال 53 function J =schedule(deadline) n=length(deadline); J (1)=1; for i=2:n K=add(J ,i,deadline); if feasible(K,deadline) J =K; end end end 54 function r=feasible(K,deadline) n=length(K); r=1; for i=1:n if deadline(K(i))> i r=0; break; end end end ج) زمان‌بندی با مهلت معین به گونه‌ای اضافه می‌کند که در دنباله به دست آمده کارها بر اساس مهلتشان مرتب باشند function K=add(J ,i,deadline) n=length(J ); for r=1:n if deadline(J (r))<=deadline(i ) K(r)=J (r); else K(r)=i; K(r+1:n+1)=J (r:n); break; ج) زمان‌بندی با مهلت معین پیچیدگی محاسباتی مرتب کردن کارها بر اساس منافعشان ... ) Θ (n lgnمی‌باشد. در هر تکرار از حلقه تابع ... ،schedule برای اینکه iامین کار را به Kاضافه کنیم ،حداکثر به iمقایسه نیاز است. همچنین حداکثر iمقایسه نیاز است تا ممکن بودن Kرا بررسی کنیم. بنابراین در بدترین حالت پیچیدگی محاسباتی این الگوریتم برابر است با : 55 مسئله کوله‌پشتی صفر و یک که w iو piو Wهمگی اعداد مثبتی هستند .می‌خواهیم زیر مجموعه Aاز Sرا به گونه‌ای مشخص کنیم که ... 56 ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک اگر بخواهیم رویکرد brute-forceرا درنظر بگیریم ... باید تمامی زیرمجموعه‌های Sرا درنظر بگیریم و ... از اونهایی که مجموع وزنشون از Wبیشتر است صرفنظر کنیم و ... از زیرمجموعه‌های باقیمانده اونی که بیشترین مجموع منفعت دارد را به عنوان پاسخ انتخاب کنیم. پیچیدگی محاسباتی این روش بادرنظر گرفتن nآیتم .... 2nمی‌باشد 57 ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک اولین راه حل حریصانه که شاید برای این مساله به ذهن برسد آن است که ... تمامی آیتم‌ها را بر اساس منفعتشان به صورت نزولی مرتب کنیم و ... به ترتیب آیتم‌ها را از مجموعه مرتب‌شده برداریم مادامیکه ... مجموع وزنشان از Wبیشتر نشود. این استراتژی زمانیکه آیتم‌های با منفعت باال وزن بیشتری در مقایسه با منفعتشون دارند مناسب نمی‌باشد. 58 ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک احتماال استراتژی بعدی این می‌تواند باشد که آیتم‌های سبک‌تر را ابتدا برداریم ... این استراتژی هم زمانی که آیتم‌های سبک منفعت کمی داشته باشند به شکست می‌انجامد. 59 ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک راه حل حریصانه مناسب این است که ... آیتم‌ها را بر اساس منفعت واحد وزنشان به صورت نزولی مرتب کنیم و ... آیتم‌ها را تا زمانیکه مجموع وزنشان از Wبیشتر نشود برداریم. 60 ه) الگوریتم حریصانه در مسئله کوله پشتی صفر و یک 61 ه) الگوریتم حریصانه در مسئله کوله پشتی کسری ()Fractional در مساله کوله‌پشتی کسری چنانچه برداشتن کل آیتم میسر نیست، می‌توان بخشی از آن را نیز برداشت. مثال در مثال قبل ... بنابراین هیچ فضایی هدر نمی‌رود. پس همواره حل بهینه را خواهیم داشت. 62