برای دانلود کل پاورپوینت از لینک زیر استفاده کنید:
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 6
الگوریتم فلوید برای یافتن کوتاه ترین مسیر
یک مشکل متداول در سفره های هوایی هنگامی که پرواز مستقیم وجود نداشته باشد تعیین کوتاه ترین مسیر پرواز از شهری به شهر دیگر است . حال الگوریتمی طراحی می کنیم که این مسئله و مسائل مشابه را حل کند . نخست لازم است نظریه گراف ها را مرور کنیم . شکل یک گراف جهت دار و موضون را نشان می دهد به خاطر دارید که در نمایش تصویری گراف ها دایره نشان گر راس ها و خط میان دو دایره نشان دهنده یال ها هستند . اگر هر یال دارای جهت باشد گراف را گراف جهت دار یا دیاگراف می گویند . هنگام رسم یال ها در این گونه گراف ها از پیکان برای نشان دادن جهت استفاده می کنیم در یک دیاگراف بین دو راس امکان وجود دو یال است که جهت آنها مخالف هم هست. برای مثال درشکل یک یال از v1 به v2 و یکی از v2 به v1 وجود دارد.اگر این یال ها با مقادیری همراه باشند این مقادیر را وزن و گراف حاصل را موزون می خوانند.
در این جا فرض می کنیم که این مقادیر غیر منفی است.گرچه این مقادیر را معولاً وزن می نامند در بسیاری از از کابردها نشانگر فاصله است.بنابراین مسیر را به عنوان فاصله میان راسی تا راس دیگر در نظر می گیرند.در یک گراف جهت دار مسیر مجموعه ای از راس هاست به طوری که از یک راس تا راس دیگر یک یال وجود دارد. مسیری از یک راس به خود آن راس را چرخه می گویند.
اگر مسیری هیچگاه دوبار از یک راس نگذرد مسیر ساده نامیده می شود.توجه کنید که یک مسیر ساده هرگز حاوی زیر مسیری که چرخه ای باشد نیست.طول یک مسیر در گراف موزون حاصل جمع اوزان مسیر است. در یک گراف ناموزون طول مسیر صرفاً عبارت است از تعداد رئوس موجود در آن است.
مسئله ای که کاربردهای فراوان دارد یافتن کوتاهترین مسیر از راسی به رئوس دیگر است. واضح است کوتاهترین مسیر باید مسیری ساده باشد. در شکل سه مسیر ساده از v1 به v2 وجود دارد یعنی [v1,v2,v3] [v1,v4,v3] [v1,v2,v4,v3] .چون
Length[v1,v2,v3]=1+3=4
Length[v1,v4,v3]=1+2=3
Length[v1,v2,v4,v3]=1+2+2=5
[v1,v4,v3]کوتاهترین مسیر ازv1 به v3 است.همانطور که پیش از این گفته شد یک کاربرد متداول کوتاهترین مسیر تعیین کوتاهترین مسیر میان دو شهر است.
مسئله کوتاهترین یک مسئله بهینه سازی است. برای هر نمونه از مسئله بهینه سازی ممکن است بیش از یک راه حل وجود داشته باشد.هریک از راه حل های پیشنهادی دارای مقداری مرتبط با آن است و حل نمونه آن حلی است که دارای مقدار بهینه است.مقدار بهینه حداقل است یا حد اکثر در مورد مسئله کوتاهترین مسیر یک حل پیشنهادی مسیری از یک راس به راس دیگر بود .مقدار آن طول مسیر و مقدار بهینه حداقل طول است.
چون ممکن است بیش از یک کوتاهترین مسیر از راسی به راس دیگر وجود داشته باشد مسئله ما یافتن هر یک از این کوتاهترین مسیر هاست.یک الگوریتم واضح برای این مسئله تعیین طول همه مسیرها برای هر راس از ان راس به هریک از رئوس دیگر است.اما زمان این الگوریتم بدتر از زمان نمایی است. برای مثال فرض کنید از هر راس به همه رئوس دیگر یک یال وجود دارد .در این صورت زیر مجموعه ای از همه مسیر ها عبارت است از مجموعه ای خواهد بود که از راس نخست شروع می شود و به راسی دیگر ختم می شود و از همه رئوس دیگر عبور می کنند.چون راس دوم در چنین مسیری می تواند هریک از n-2 راس باشد راس سوم در چنین مسیری می تواند هر یک از n-3 راس باشد...
و راس دومی به آخری روی چنین مسیری فقط می تواند یک راس باشد.تعداد کل مسیرها از یک راس که از همه رئوس دیگر بگذرد عبارت است از :
(n-2)(n-3)…1=(n-2)!
که بد تر از حالت نمایی است. در بسیاری از مسائل بهینه سازی با همین وضعیت مواجه هستیم . یعنی الگوریتمی که همه حالت های ممکن را در نظر بگیرد زمان آن نمایی یا بدتر است.
با استفاده از برنامه نویسی پویا یک الگوریتم زمانی درجه سوم برای مسئله کوتاهترین مسیر ایجاد می کنیم. نخست الگوریتمی طرح می کنیم که فقط طول کوتاهترین مسیرها را تعیین کند. سپس آن را طوری اصلاح می کنیم که کوتاهترین مسیر را نیز ایجاد کند .یک گراف موزون حاوی n راس را با یک آرایه w نشان می دهند که در آن
اگر یالی بین , باشد وزن یال
اگر یالی بین , نباشد w[i][j]=
اگر i=j باشد 0
چون راس vj وقتی مجاور راس vi خوانده می شود که یالی بین vj و vi باشد به این آرایه نمایش ماتریس همجواری یک گراف می گویند .اگر بتوانیم راهی برای محاسبه مقادیر d از مقادیر w بیابیم الگوریتمی برای مسئله کوتاهترین مسیر خواهیم داشت این هدف با ایجاد n+1 آرایه قابل حصول است که وداریم : =طول کوتاهترین مسیر از VI به VJ فقط با استفاده از رئوس موجود در مجموعه {V1,V2,….VK} به عنوان رئوس واسطه پیش از انکه نشان دهیم چرا به این ترتیب قادر به محاسبه D از روی W هستیم معنی عناصر این آرایه ها را توضیح می دهیم .
مثال چند مقدار از را به عنوان مثال برای گراف شکل حل می کنیم.
برای هر گراف اینها مساویند زیرا کوتاهترین مسیری که از v2 آغاز می شود نمی تواند از v2 بگذرد
برای این گراف ها اینها مساویند زیرا با گنجاندن v3 مسیر جدیدی از v2 به v5 بدست نمی آید
.
برای هر گراف اینها مساویند زیرا کوتاهترین مسیری به v5 منتهی می شود نمی تواند از v5 بگذرد.
آخرین مقدار محاسبه شده طول کوتاهترین مسیر از V2 به V5 است که مجاز به عبور از هر یک از رئوس دیگر است .یعنی طول کوتاهترین مسیر است.
بنابراین برای تعیین D از روی W فقط باید راهی برای بدست آوردن از روی بیابیم.
مراحل استفاده از برنام نویسی پویا برای رسیدن به این هدف عبارت است از :
ارائه یک ویژگی (فرایند بازگشتی که با آن بتوان را از روی محاسبه کرد.
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 25
الگوریتم
هر برنامه، می بایست دارای یک طرح و یا الگو بوده تا برنامه نویس بر اساس آن عملیات خود را دنبال نماید.از دیدگاه برنامه نویسان ، هر برنامه نیازمند یک الگوریتم است . بعبارت ساده ، الگوریتم ، بیانه ای روشمند بمنظور حل یک مسئله بخصوص است . از منظر برنامه نویسان ،الگوریتم بمنزله یک طرح کلی و یا مجموعه دستورالعمل هائی است که با دنبال نمودن آنان ، برنامه ای تولید می گردد.
الگوریتم های میکرو در مقابل ماکرو
الگوریتم ها دارای ویژگی های متفاوتی می باشند . ما می توانیم در رابطه با الگوریتم استفاده شده به منظور نوشتن یک برنامه مشخص صحبت نمائیم . از این زاویه ، ما صرفا" در رابطه با الگوریتم در سطح ماکرو(macro level) ، صحبت نموده ایم . در چنین مواردی ، الگوریتم ارائه شده ، سعی در بدست آوردن جنبه های عمومی برنامه از طریق یک مرور کلی به برنامه در مقابل درگیر شدن در جزئیات را دارد.ما می توانیم در رابطه با الگوریتم ها ، از سطح "میکرو" صحبت نمائیم . از این زاویه ، به سطوح پایین تر رفته و به عوامل اساسی ونگهدارنده ای که یک جنبه خاص از برنامه را با یکدیگر مرتبط می نماید، صحبت کرد. مثلا" در صورتیکه شما دارای داده هائی هستید که می بایست قبل از استفاده مرتب گردند ،الگوریتم های مرتب سازی متعددی در این زمینه وجود داشته و می توان یکی از آنها را بمنظور تامین اهداف مورد نظر خود انتخاب نمود. انتخاب یک الگوریتم مرتب سازی ، صرفا" باعث حل شدن یکی از جنبه های متفاوت برنامه می گردد . پس از مرتب سازی داده ها ،می بایست از یک الگوریتم میکرو دیگر بمنظور نمایش داده ها ی مرتب شده استفاده گردد .
همانگونه که احتمالا" حدس زده اید ، ما می توانیم تمام الگوریتم های میکرو را بمنظور ایجاد یک الگوریتم ماکرو ، جمع آوری نمائیم . اگر ما با الگوریتم های میکرو ، آغاز نمائیم ، و حرکت خود را بسمت نمایش ماکروی یک برنامه ، پیش ببریم ، کاری را انجام داده ایم که موسوم به طراحی " پایین به بالا" (buttom-up) ، است . اگر ما فعالیت خود را با یک الگوریتم ماکرو آعاز و حرکت خود را بسمت پائین و الگوریتم های میکرو ، ادامه دهیم ، طراحی از نوع " بالا به پایین " (top-down) را انجام داده ایم .
شاید این سوال مطرح گردد که کدام روش بهتر است ؟ اگر شما تمام مقالاتی را که تاکنون در این زمینه نوشته شده اند را دنبال نمائید ، هرگز به یک نتیجه قابل قبول دست نخواهید یافت . هر رویکرد، دارای نکات مثبت و منفی مربوط به خود است . صرفنظر از رویکرد طراحی استفاده شده ، می بایست دارای الگوئی (طرحی) مناسب برای برنامه باشیم .حداقل، نیازمند یک اعلامیه از مسئله برنامه نویسی و یک طرح ( الگو) برای برخورد با مسئله ، خواهیم بود . پس از شناخت مسئله ، می توان نحوه حل مسئله را ترسیم کرد. شناخت عمیق و مناسب نسبت به مسئله ای که قصد حل آن را داریم ، شرط اساسی و ضروری برای طراحی یک برنامه است .با توجه به اینکه این اعتقاد وجود دارد که شناخت جامع و کلی از مسئله ای که حل آن را داریم ، بخشی ضروری در اولین مرحله برنامه نویسی است ، ما در ادامه از رویکرد "بالا - پایین "، تبعیـت می نمائیم . فراموش نکنیم که رویکرد فوق ، امکان مشاهده مجازی از هر مسئله برنامه نویسی را فراهم خواهد نمود.
مراحل پنج گانه
هر برنامه را صرفنظر از میزان پیچیدگی آن ، می توان به پنج مرحله اساسی تجزیه کرد :
مقدار دهی اولیه
ورودی
پردازش
خروجی
پاکسازی
در ادامه به بررسی هریک از مراحل فوق ، خواهیم پرداخت .
مرحله مقداردهی اولیه
مرحله مقداردهی اولیه ، اولین مرحله ای است که می بایست در زمان طراحی یک برنامه در رابطه با آن فکر کرد . مرحله فوق ، شامل تمامی عملیات مورد نیازی است که برنامه می بایست قبل ازبرقراری ارتباط با کاربر ، انجام دهد . در ابتدا ممکن است این موضوع که عملیاتی را قبل از برقراری ارتباط با کاربر می بایست انجام داد ، تا اندازه ای عجیب بنظر رسد ولی احتمالا" برنامه های زیادی را مشاهده نموده اید که در این راستا عملیات مشابهی را انجام می دهند. مثلا" ، در زمان استفاده از برنامه هائی نظیر Word ، Excel و یا برنامه های مشابه دیگر ، با چنین مواردی برخورد نموده ایم . مثلا" با انتخاب گزینه منو File ، می توان لیستی از فایل هائی را که با آنها
نوع فایل: ppt _ pptx ( پاورپوینت )
( قابلیت ویرایش )
قسمتی از اسلاید :
تعداد اسلاید : 249 صفحه
درس طراحی الگوریتم ها(با شبه کد های c ++) فصل اول: کارایی ، تحلیل و مرتبه الگوریتم ها این کتاب در باره تکنیک های مربوط به حل مسائل است. تکنیک ، روش مورد استفاده در حل مسائل است. مسئله ، پرسشی است که به دنبال پاسخ آن هستیم. بکار بردن تکنیک منجر به روشی گام به گام (الگوریتم ) در حل یک مسئله می شود. منظورازسریع بودن یک الگوریتم، یعنی تحلیل آن از لحاظ زمان و حافظه.
نوشتن الگوریتم به زبان فارسی دو ایراد دارد: 1- نوشتن الگوریتم های پیچیده به این شیوه دشوار است. 2- مشخص نیست از توصیف فارسی الگوریتم چگونه می توان یک برنامه کامپیوتری ایجاد کرد. الگوریتم 1-1: جست و جوی ترتیبی Void seqsearch ( int n const keytype S[ ] keytype x, index& location) { location = 1; while (location <= n && S[location] ! = x) location++; if (location > n ) location = 0 ; الگوریتم 2-1:محاسبه مجموع عناصر آرایه number sum (int n , const number s[ ]) { index i; number result; result = 0; for (i = 1; i <= n; i++) result = result + s[i]; return result; } الگوریتم 3-1:مرتب سازی تعویضی مسئله: n کلید را به ترتیب غیر نزولی مرتب سازی کنید. void exchangesort (int n , keytype S[ ]) { index i,j; for (i = 1 ; i<= n -1; i++) for (j = i +1; j <= n ; j++) if ( S[j] < S[i]) exchange S[i] and S[j]; } الگوریتم 4-1:ضرب ماتریس ها void matrixmult (int n const number A [ ] [ ], const number B [ ] [ ], number C [ ] [ ], { index i , j, k; for ( i = 1; I <= n ; i++) for (i = 1; j <= n ; j++)} C [i] [j] = 0; for (k = 1 ; k <= n ; k++) C [i][j] = C[i] [j] + A [i][k] * B [k][j] }} 2- 1اهمیت ساخت الگوریتم های کارآمد جست و جوی دودویی معمولا بسیار سریع تر ازجست و جوی ترتیبی است. تعداد مقایسه های انجام شده توسط جست و جوی دودویی برابر با lg n + 1 است . الگوریتم 1-1: جست و جوی ترتیبی Void seqsearch ( int n const keytype S[ ] keytype x, index& location) { location = 1; while (location <= n && S[location] ! = x) location++; if (location > n ) location = 0 ; الگوریتم 5-1: جست و جوی دودویی Void binsearch (int n, const keytype S[ ], keytype x, index& location) { index low, high, mid; low = 1 ; high = n; location = 0; while (low <= high && location = = 0) { mid = Į(low + high)/2⌡; if ( x = = S [mi
متن بالا فقط قسمتی از محتوی متن پاورپوینت میباشد،شما بعد از پرداخت آنلاین ، فایل را فورا دانلود نمایید
لطفا به نکات زیر در هنگام خرید دانلود پاورپوینت: ................... توجه فرمایید !
« پرداخت آنلاین »
لینک دانلود و خرید پایین توضیحات
فرمت فایل word و قابل ویرایش و پرینت
تعداد صفحات: 28
بهینه سازی منبع با استفاده از شبیه سازی ترکیب یافته و الگوریتم ژنتیک
خلاصه
این مقاله، توسط ترکیب کردن فلوچارت ( نمودار گردش کار) براساس ابراز شبیه سازی با یک روش بهینه سازی ژنتیک قدرتمند، یک روش را برای بهینه سازی منبع نشان می دهد.روش ارائه شده، کمترین هزینه،و بیشترین بازده را ارائه میدهد، وبالاترین نسبت سودمندی را در عملکردهای ساخت و تولید فراهم می آورد. به منظور یکپارچگی بیشتر بهینه سازی منبع در طرح ریزی های ساخت،مدلهای شبیه سازی بهینه یافته (GA) الگوریتم های ژنتیکی گوناگون،عموماً با نرم افزارهای مدیریت پروژه بکار رفته شده ادغام می شوند. بنابراین، این مدلها از طریق نرم افزار زمان بندی فعال می شوند و طرح را بهینه می سازند.نتیجه، یک ساختار کاری تقلیل یافته سلسله مراتبی در رابطه با مدلهای همانندی سازی بهینه یافته GA است. آزمایشات گوناگون بهینه سازی با یک سیستم در دو مورد مطالعه، توانایی آن را برای بهینه ساختن منابع در محدوده محدودیتهای واقعی مدلهای همانند سازی آشکار کرد. این الگو برای کاربرد بسیارآسان است و می تواند در پروژه های بزرگ بکار رود. براساس این تحقیق، همانندسازی کامپیوتر وا لگوریتمهای ژنتیک ،می توانند یک ترکیب موثر برای بهبود دادن بازده و صرفه جویی در زمان وساخت و هزینه ها باشند.
مقدمه
این امر کاملاً آشکار شده است که بازده کاری پایین ،عدم آموزش، و کاهش تعداد معاملات، چالشهای بحرانی هستند که صنعت ساختمان( ساخت) با آن روبرو خواهد شد.
بهره دهی یا قدرت تولید در رابطه با مطالعه ها، برای مثال،دلالت بر زمان بیکاری (بیهودة) کاربران در ساخت(تولید) دارد که این زمان از 20 تا 45% متغیر است. این اتلاف وقت ، که از طریق منابع ناکارآمد و طرح ریزیهای غیربسنده( نامناسب) ناشی می شود، تاثیر و پیامد فوق العاده ای در هزینه های ساخت دارد. همچنین، پیماناکاران که مهارتهای مدیریتی منابع کارآمد را ندارند، این رقابت کردن در بازارهای ساخت جهانی که آنها د ر آن فرصتها بسیاری را خواهند یافت، برای آنها کاری بس دشوار خواهد بود.
با ایجاد تجهیزات و نیروی کار برای امر ساخت و تولید، این امر آشکار است که تدبیرهای کاربرد نیروی کار متناوب و کاربرد بهتر از منابع کاری موجود، به منظور بهبود دادن،بهره دهی کاری و کاهش هزینه های ساخت، مورد نیاز است. استفاده کارآمد از منابع پروژه، هزینه های ساخت را برای مالکان و مصرف کنندگان کاهش می دهد، و در عین حال سودمندیهایی را برای پیمانکاران افزایش می دهد. با این وجود،برخی فاکتورها وجود دارند که ،مدیریت منبع را امر دشواری می سازند، این فاکتورها در مراحل زیر توضیح داده شده اند:
سیاست جداسازی مدیریت منبع:در ادبیات، محققان گوناگون، تعدادی تکنیکها را برای پرداختن به جنبه های فردی مدیریت منبع، همانند تخصیص منبع، سطح بندی منبع، مدیریت نقدینگی، و تجزیه و هزینه و زمان معاملات (TCT) ، ارائه داده اند. مطالعات تالبوت و پترسون(1979) و گاولیش و پیرکون (1991)، برای مثال، به تخصیص منابع مربوط بود ، در حالیکه بررسیهای Easa (1989) و Shah et al (1993) به سطح بندی و تراز کردن منابع می پرداخت روشهای دیگر ، تنها روی تجزیه TCT متمرکز شدند. همانطوریکه این بررسیها سودمند واقع شدند، آنها به ویژگیهای مجزایی پرداختند که یکی پس از دیگری برای پروژه ها بکار برده می شدند ( نه بطور همزمان) . بوسیله پیچیدگی اساسی پروژه ها و مشکلاتی در رابطه با الگوبرداری تمام ویژگیهای ترکیب یافته، تلاش بسیار کمی برای بهینه سازی منابع ترکیب شده به عمل آمد.
ناکارآمدی الگوریتم های بهنیه سازی سنتی: در چند دهه گذشته ، بهینه سازی منبع سنتی، براساس روشهای ریاضی یا براساس تکنیکهای ذهنی(غیرمستدل) بوده است. روشهای ریاضی ، همانند برنامه ریزیهای عدد صحیح ، خطی، یا برنامه ریزیهای دینامیکی ،برای مشکلات منبع فردی پیشنهاد شده بودند.با این وجود ، روشهای ریاضی از لحاظ محاسبه ای برای هر پروژه واقعی انعطاف ناپذیر بودند که این روش فقط برای سایزهایی از پروژه مناسب می باشد. همچنین ،روشهای ریاضی پیچیده ایشان دستخوش تغییر می شوند وممکن در مطلوبترین وبهینه ترین قرار بگیرند، روشهای ذهنی (غیرمستدل) ، ازسوی دیگر، تجربیات وقوانین thumb را بکار می برند، نه فرمولهای ریاضی سخت ودقیق را. محققان برای تخصیص منبع، مدلهای ذهنی گوناگونی را پیشنهاد نموده اندن،تراز بندی منبع ها،تجزیه TCT، علی رغم سهولتشان
