روش حریصانه(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. بنابراین هیچ فضایی هدر نمی‌رود. پس همواره حل بهینه را خواهیم داشت.