تحقیق در عملیات ( Operation Research)

بهینه سازی

پیچیدگی الگوریتم
نویسنده : دکتر نعمت اله تقی نژاد - ساعت ۱:٥٠ ‎ب.ظ روز سه‌شنبه ۱۸ تیر ۱۳٩٢
 


مقایسه ی بین دو الگوریتم

دو الگوریتم را که کار مشابهی انجام می دهند ، درنظر می گیریم،مقایسه آنها به چه معنا می باشد ؟ چه موقع میتوان گفت یکی بهتراست ؟ چه فاکتورهایی درکارایی الگوریتم مؤثر می باشد؟ چگونه کارایی را به دست می آوریم؟

 نظریهٔ‌ پیچیدگی محاسباتی شاخه‌ای ازعلوم کامپیوتر و ریاضی است که به بررسی دشواری حل مسائل به وسیله‌ی رایانه (به عبارت دقیق‌تر به‌ صورت الگوریتمی) می‌پردازد.
این نظریه با منابع مورد نیاز برای حل یک مسأله سروکار دارد. عمومی‌ترین منابع زمان (چقدر زمان برای حل کردن مسأله لازم است) و فضا (چقدر حافظه مورد نیاز است) می‌باشند.  
تعریف 1:میزان حافظه یا پیچیدگی فضایی یک برنامه مقدار حافظه مورد نیاز برای اجرای کامل یک برنامه است.

تعریف 2: پیچیدگی زمانی یک برنامه ، مقدار زمان کامپیوتر است که برای اجرای کامل برنامه لازم است.

 

پیچیدگی فضایی الگوریتم

 فضای مورد نیاز یک برنامه شامل موارد زیر می باشد:
1.نیازمندیهای فضای ثابت
2.نیازمندیهای فضای متغیر

اولین مورد به فضای مورد نیازیی که به تعداد و اندازه ورودی و خروجی برنامه بستگی ندارد ، اشاره می کند و شامل فضای دستورالعمل ها(فضای لازم برای ذخیره کد برنامه)،فضای لازم برای متغیرهای ساده،متغیرهای ساختاری با اندازه ثابت و....می باشد.

دومین مورد شامل فضای مورد نیاز متغیرهای ساخت یافته ای است که اندازه آنها بستگی به نمونه ای از مسأله ای که حل می شود دارد.

 

 برای مطالعه کامل مطلب و دانلود رایگان پروژه به ادامه مطلب مراجعه کنید:

 


 

پیچیدگی زمانی الگوریتم

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

زمان اجرا وابسته به تعدادی فاکتورهای متفاوت از جمله تکنیک های برنامه نویسی ، زبان برنامه نویسی ، نوع داده های ورودی ، ساختار کامپیوتر و... است.

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

 

انواع  پیچیدگی

در بحث پیچیدگی دو حالت بیشتر مورد توجه قرار می گیرد:
 1.پیچیدگی در بدترین حالت worst  case) 

2.پیچیدگی در حالت میانگین  (avarage case)

 ابتدا با یک مثال این بحث را توضیح می دهیم، فرض کنیم آرایه ای به طول N داریم ، و به دنبال عدد خاصی در این دنباله می گردیم . پس باید از ابتدا تا انتهای آرایه را بگردیم  تا عدد مورد نظررا بیابیم. بدترین حالت وقتی است که عدد مورد نظر درانتهای آرایه قرار گرفته باشد . در این جا پیچیدگی به صورت ( O(N است. حالت میانگین زمانی  است که عدد مورد نظر در وسط  آرایه قرارگرفته باشد که در این حالت پیچیدگی ( O(N/2 است.
 
تعریف 5)  پیچیدگی در بدترین حالت : پیچیدگی الگوریتم است هنگامی که ورودی بدترین حالت ممکن نسبت به پیچیدگی را دارد.یعنی حداکثر تعداد مراحلی است که می تواند برای پارامترهای داده شده اجرا شود.

پیچیدگی درحالت میانگین : مقدار انتظار یا امید ریاضی تابع پیچیدگی می باشد.

 

انواع کلاسهای پیچیدگی

پیچیدگی درحالت میانگین بسیار مشکل ترازبدترین حالت می باشد زیرا فرض می کند که داده ها از یک توزیع احتمال خاص پیروی می کنند.این توزیع عمل در وضعیت های حقیقی ممکن نمی باشد. بنابراین بیشتر پیچیدگی در بدترین حالت را مد نظر قرار می دهیم. 

برای سادگی کار مسأله‌ها به کلاس‌هایی تقسیم می‌شوند به طوری که مسأله‌های یک کلاس از حیث زمان مورد نیاز با هم مشابهت دارند. این کلاس‌ها در اصطلاح کلاس پیچیدگی خوانده می‌شوند.

 معروف ‌ترین کلاس‌های پیچیدگی، P و NP هستند . به طور شهودی می‌توان گفت P کلاس مسأله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اما NP شامل آن دسته از مسأله‌هاست که اگرچه ممکن است پیدا کردن جواب ‌برای آن‌ها نیاز به زمان زیادی داشته باشد اما چک کردن درستی جواب به وسیله‌ٔ یک الگوریتم سریع ممکن است.

 

معرفی NP-Complete  

  NP-Completeها مسائلی هستند که اثبات شده به سرعت قابل حل نیستند. در تئوری پیچیدگی NP-Completeها دشوارترین مسائل کلاس NP هستند و جزء مسائلی می‌باشند که احتمال حضورشان در کلاس P خیلی کم است. علت این امر این می‌باشد که اگر یک راه‌حل پیدا شود که بتواندیک مسأله NP-Complete را حل کند، می‌توان از آن الگوریتم برای حل کردن سریع همه مسائل NP-Complete‌ استفاده کرد. به خاطر این مسأله و نیز بخاطر اینکه تحقیقات زیادی برای پیدا کردن الگوریتم کارآمدی برای حل کردن اینگونه مسائل با شکست مواجه شده‌اند، وقتی که مسأله‌ای به عنوان NP-Complete‌ معرفی شد، معمولاً اینطور قلمداد می‌شود که این مسأله در زمان Polynomial قابل حل شدن نمی‌باشد، یا به بیانی دیگر هیچ الگوریتمی وجود ندارد که این مسأله را در زمان Polynomial حل نماید.

کلاس EXPTIME مسائلی که زمان مورد نیاز برای حل آنها به صورت نمایی می‌باشد. مسائل این کلاس شامل همه مسائل دو کلاس قبلی نیز می‌باشد. نکته جالب و قابل توجه این است که حتی این کلاس نیز جامع نمی‌باشد. یعنی مسائلی وجود دارند که بهترین و کارامدترین الگوریتم‌ها برای آنها زمان بیش‌تری نسبت به زمان نمایی می‌گیرند.

مثال:یک مسیر ساده در یک گراف به مسیری اطلاق می‌شود که هیچ رأس یا یال تکراری در آن وجود ‌نداشته ‌باشد. با داشتن گراف G، رئوس s و t و عدد k آیا یک مسیر ساده از s به t با حداقل k یال وجود دارد؟.چرا این مسأله NP می‌باشد؟ چون اگر مسیری به شما داده شود، به راحتی می‌توان طول مسیر را مشخص نمود و آن را با k مقایسه کرد. همه این کار‌ها در زمان خطی و صد البته در زمان Polynomial قابل انجام می‌باشد.

 در حقیقت این مسأله در کلاس NP-Completeها می‌باشد، الگوریتم‌هایی وجود دارند که این مسأله را حل می‌کنند، به عنوان مثال همه مسیر‌های موجود و ممکن را بررسی نموده و نتایج مقایسه شوند که آیا این مسیر مسأله را حل می‌کند یا نه. اما تا آنجایی که می‌دانیم، الگوریتمی با زمان Polynomial برای حل این مسأله وجود ندارد.

حال به سراغ بحث برنامه ریزی خطی برمی گردیم و روش سیمپلکس را در نظر می گیریم.سوالی که مطرح این است که چه مقدار کار برای اجرای الگوریتم لازم می باشد؟
بنابراین باید بدانیم که الگوریتم در چند تکرار انجام می شود وهر تکراری چه مقدار کار نیاز دارد.مسلماَ کار مورد نیاز برای مسأله با افزایش سایز مسأله بیشترمی شود.
برای یک برنامه ریزی خطی سایز مسأله تعداد سطرها و ستون ها در جدول اولیه می باشد.
در هر تکرار الگوریتم سیمپلکس ، با n متغیر وm قید ، نیاز به (m+1)(n+1) ضرب(یا تقسیم) و mn جمع (تفریق )داریم.  

در برنامه ای با m قید ، سیمپلکس قادر به حل مسأله از m تا 3m تکرار
می باشد.از زمان پیدایش الگوریتم تا حدود بیست سال این فرضیه درست بود وپیچیدگی آنرا به صورت چند جمله ای در نظر می گرفتند.

  ولی در سال 1972 ، Klee و Minty مثالی ارائه دادند که شامل m  قید نامساوی با m متغیر بود و نیاز به  m2m-1 تکرار داشت و در هر تکرار از هر یک از نقاط شدنی تا رسیدن به جواب بهینه عبور می کرد.  

 

بررسی پیچیدگی الگوریتم سیمپلکس

سوالی که مطرح می شود این است که این اتفاق از خصوصیت های خود الگوریتم است یا از خاصیت های برنامه ریزی خطی ؟ یعنی اینکه هر الگوریتمی برای برنامه ریزی خطی نیاز به زمان نمایی دارد؟

آیا الگوریتمی وجود دارد که سرعت رشد پیچیدگی زمانی آن کمتر از نمایی باشد؟
آیا مسأله برنامه ریزی خطی در کلاس NP-C قرار دارد ؟
 
در سال  1979 دانشمند روسی به نام  Khachiyan ، روشی به نام بیضوی را ارا ئه کرد که دارای پیچیدگی چندجمله ای بود و چنین انتظار می رفت که دستورالعمل آن بسیار سریع ترازسیمپلکس عمل نماید ، درنتیجه جایگزین سیمپلکس گردد.ولیکن تجربیات محاسباتی چنین چیزی را ثابت نکرد واین روش دارای ارزش عملی نیست مگر آنکه موانع زیادی که باعث کندی این الگوریتم می شوند برداشته شوند.     

 

بررسی پیچیدگی الگوریتم کارمارکار

  در سال 1984، کارمارکار(karmarkar) یک الگوریتم جدید را ارائه داد که دارای پیچیدگی چندجمله ای زمانی بود.او ادعا کرد که روش جدیدش می تواند بین 10 الی 50 برابر سرعت سیمپلکس عمل نماید.
البته این مطلب در مورد مسائل با بعد بالا صحت دارد و در مسائل با بعد پایین سرعت الگوریتم سیمپلکس بیشتراست.علت چیست؟

 روش کارمارکار درهر تکرارش نیاز به محاسبات قابل توجهی نسبت به  سیمپلکس دارد.بنابرابن زمان هر تکرارآن بیشترازسیمپلکس است.برای یک مسأله کوچک ، مثلاََ با 10 قید ، تقریباَ هردوالگوریتم نیاز به 20تکرار دارد.بنابراین زمان کلی  کارمارکار بیشتر از سیمپلکس است.

 

مقایسه الگوریتم سیمپلکس و کارمارکار

حال در یک مسأله بزرگ ،مثلاَ با 10،000 قید ،روش کارمارکار نیاز به کمتر از 100 تکرار دارد و حتی با در نظر گرفتن یک زمان قابل توجه برای هر تکرار ،در یک زمان کلی خوب به جواب می رسیم.چون تعداد کم مراحل مشکل را مهار می کند.در حالی که روش سیمپلکس ممکن است به 20،000 تکرار نیاز داشته باشد.

علت این اختلاف بزرگ در تعداد مراحل به علت مسیری است که دنبال می شود.سیمپلکس از یک جواب شدنی  گوشه ای(CPF)  شروع می کند و به نقطه CPF مجاورش می رود.

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

 

دریافت رایگان پروژه    


 
 
 



backgroundcolor= class=#2f57a2width:230px; padding-top: 5px;td width=logo