advertise laitec sharif univercity استخراج بیت کوین با کامپیوتر استخراج بیت کوین با کامپیوتر
سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

3000 تومان
دانلود پروژه معمای 8 با الگوریتم ژنتیک در سی شارپ

دانلود پروژه معمای 8 با الگوریتم ژنتیک در سی شارپ

3000 تومان
دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

3000 تومان
دانلود سورس پروژه پایانی وب سایت بنگاه املاک با php

دانلود سورس پروژه پایانی وب سایت بنگاه املاک با php

18000 تومان
دانلود پروژه کامل مهندسی نرم افزار ، شرکت نرم افزاری

دانلود پروژه کامل مهندسی نرم افزار ، شرکت نرم افزاری

3000 تومان

پایان الگوریتم GRAPHPLAN

قبلا الگوریتم GRAPHPLAN، را معرفی کرده ایم. در اینجا نشان می دهیم که GRAPHPLAN خاتمه می یابد و در صورتی که جوابی وجود نداشته باشد، خطایی را برمی گرداند.
پایان الگوریتم GRAPHPLAN

پایان الگوریتم GRAPHPLAN

قبلا الگوریتم GRAPHPLAN، را معرفی کرده ایم. در اینجا نشان می دهیم که GRAPHPLAN خاتمه می یابد و در صورتی که جوابی وجود نداشته باشد، خطایی را برمی گرداند.

اولین چیزی که باید درک شود این است که چرا نمی توان بلافاصله پس از اینکه گراف هموار شد، بسط آن را متوقف کرد. مسئله حمل بار هوایی را در نظر بگیرید که یک هواپیما و n بسته بار در فرودگاه A وجود دارند و مقصد تمام آن بارها فرودگاه B است. در این نسخه ، از مسئله، در هر زمان فقط یک بسته بار می تواند در هواپیما جاسازی شود. گراف در سطح 4 هموار می شود و این حقیقت را منعکس می سازد که برای هر بسته بار، می توانیم آن را بارگیری کنیم، با پرواز انتقال دهیم و آن را در مقصد تخلیه کنیم. اما معنایش این نیست که در سطح 4 می توان جوابی را از گراف استخراج کرد، در حقیقت جواب به 4n-1 مرحله نیاز دارد: برای هر بسته بار، آنرا بارگیری میکنیم، پرواز میکنیم و تخلیه می کنیم  و برای تمام بسته ها به جز آخری، لازم است به فرودگاه A برگردیم و بسته بعدی را بگیریم.

 

پس از اینکه گراف هموار شد، چه مدت باید گراف GRAPHPLAN را بسط دهیم؟ اگر تابع  EXTRACT-SOLUTION در یافتن جواب با شکست مواجه شود ،آنگاه حداقل یک مجموعه از اهداف باید وجود داشته باشد که قابل دسترس نباشند و به عنوان نامطلوب علامت گذاری شده باشند. بنابراین اگر امکان داشته باشد که در سطح بعدی نامطلوب های معدودی وجود داشته باشد، آنگاه باید ادامه دهیم.

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

 

خواص گراف برنامه ریزی (GRAPHPLAN) به شرح زیر می باشند:

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

 

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

 

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

 

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

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

 

 



0
نظرات

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
معرفی خواص گراف های برنامه ریزیخاتمه یافتن GRAPHPLANخاصیت های GRAPHPLAN در مسایل هوش مصنوعیچگونگی مشخص شدن پایان گراف برنامه ریزیهموارشدن گراف برنامه ریزی یعنی چه؟الگوریتم GRAPHPLAN چگونه خاتمه می یابد؟چه مدت باید گراف GRAPHPLAN را بسط دهیم؟تعیین پایان یافتن الگوریتم GRAPHPLANآشنایی با هدف های غیرقابل دسترس و نامطلوب در GRAPHPLANاهداف نامطلوب در گراف برنامه ریزی لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

کسب درآمد با کامپیوتر
تولید بیت کوین با کامپیوتر

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php