دانلود   پاورپوینت (شبكه هاي فعاليت) ACTIVITY NETWORKS

توضیحات محصول

دانلود پاورپوینت (شبكه هاي فعاليت) ACTIVITY NETWORKS با فرمت ppt ودر 102اسلاید قابل ویرایش

قسمتی از متن  پاورپوینت (شبكه هاي فعاليت) ACTIVITY NETWORKS

آنچه كه در اين اسلايد مي خوانيم :

(شبكه فعاليت روي راس ها)AOV 1) نمايش شبكه

(شبكه فعاليت روي يال ها)AOE2) نمايش شبكه

3) محاسبه ي زودترين زمان فعاليت

4) محاسبه ي ديرترين زمان فعاليت

AOV ) نمایش شبکه1

هر پروژه ای را می توان به چندين زيرپروژه كه فعاليت ناميده مي شود، تقسیم کرد .

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

یک دانشجوی رشته مهندسی نرم افزار برای گرفتن مدرک ناچار به موفقیت در چندین درس است.

پس هر درس به عنوان یک فعالیت در نظر گرفته می شود.

پيش نيازها روابط و اولويت موجود بين دروس را معين مي كنند .

مثال

به منظور روشن شدن روابط پيش نيازي مي توان از يك گرافجهتدار استفاده كرد، كه در آن :

– راس ها را نمایانگر دروس

– وهر یال جهتدار آن را نشان دهنده ی رابطه پیش نیازی قرار می دهیم .

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

تعاریف

شبکه فعالیت روی راس(AOV) :این شبکه در واقع یک گراف جهتدار مانند G می باشد که راس های آن نمایانگر فعالیت ها و یالهای آن نمایانگر ارتباطات بین فعالیت ها می باشد.

راس i در یک شبکه AOV از گراف G راسی قبل از راس j خواهد بود اگر وتنها اگر مسیر جهتداری از راس i به راس j وجود داشته باشد.

راسi در یک شبکه AOV بلافاصله قبل از راس j است اگر و تنها اگر(i, j) یالی در G باشد.

رابطه ي ترتيبي تعريف شده توسط پيش نيازهاي درسي يك رابطه ي متعدي

است .

معلوم نيست .AOV اما اين موضوع در شبكه ي

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

هنگامي كه هيچ تناقضي از اين نوع موجود نباشد پروژه عملي است .

ترتيب موضعي :

يك ترتيب خطي از راس هاي يك گراف است به نحوي كه به ازاي هر دو راس i و j اگر i يك راس تقدمي براي j در شبكه باشد انگاه i در اين ترتيب خطي پيش از j قرار مي گيرد .

الگوريتم ارائه شده براي آزمايش عملي بودن پروژه يك ترتيب خطي از راس ها (فعاليت ها) را به صورت V0,V1,…,Vn-2,Vn-1 توليد مي كند .

طراحي الگوريتم مرتب سازي موضعي

در ابتدا راسي كه هيچ راس ديگري در شبكه قبل از ان قرار ندارد را با تمام يال هايي كه از ان خارج مي شود از شبكه حذف مي كنيم . اين مرحله تا زماني ادامه مي يابد كه همه ي راس هاي در شبكه حذف شوند .

1 //Input the AOV network . Let n be the number of vertices .

2 For ( int i=0 ; i

3 {

4 if ( every vertex has a predecessor)

5 return ; //network has a cycle and is infeasible .

6 pick a vertex V that has no predecessors ;

7 cout

8 delete V and all edges leading out of V from the network ;

9}