نوع فایل:power point
قابل ویرایش:56 اسلاید
قابل ویرایش:2 اسلاید انگلیسی
قسمتی از اسلایدها:
4-4 برنامه خطی تصادفی
سؤال: پس می توان نیم صفحه ها را به ترتیبی اضافه کرد که اصلا vi تغییری نکند تا زمان اجرا خطی شود. اینکه برای هر مجموعه از نیم صفحه ها یک ترتیب مناسب وجود دارد صحیح است ولی آیا یافتن این ترتیب ممکن و یا مقرون به صرفه است؟
پاسخ: چون این ترتیب باید قبل از شروع الگوریتم که هنوز هیچ از تقاطع نیم صفحه ها در دست نیست موجود باشد یافتن ترتیب مناسب ساده نیست. که در اینجا یک ترتیب تصادفی از H را برمی داریم.
درالگوریتم تصادفی از تابع RANDOM(k) استفاده می شود که در زمان ثابت یک عدد تصادفی بین 1 تا k را می دهد.
زمان اجرا وابسته به انتخاب تصادفی ساخته شده در الگوریتم میباشد
فهرست مطالب واسلایدها:
مقدمه
هندسه ی ریخته گری
تقاطع نیم صفحه ها
برنامه های خطی توسعه یافته
برنامه خطی تصادفی
برنامه خطی غیر کراندار
