عنوان پایان‌نامه
یافتن دور همیلتن با تبدیل یال هاو راس ها
- رشته تحصیلی
- مهندسی کامپیوتر- آلگوریتم ها و محاسبات
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس یک فنی شماره ثبت: 83..;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 71365
- تاریخ دفاع
- ۰۸ بهمن ۱۳۹۳
- دانشجو
- مظاهر پورقنبر
- استاد راهنما
- اکرم حسینیان سراجه لو, امین قدوسیان
- چکیده
- در این پایان¬نامه ، سعی در بهبود حل مسئله دور همیلتون، با استفاده از الگوریتم¬ هایی که تا به حال برای آن ارائه شده است، می¬شود اما قبل از استفاده از این الگوریتم¬ها، تکنیکی برای تبدیل یال¬ها به راس¬ ها و راس ¬ها به یال¬ها ارائه می¬گردد. در این تبدیل، گراف تبدیل یافته دارای محدودیت¬هایی می¬شود که فضای مسئله را در طول روند الگوریتم کاهش ¬داده و همچنین اجازه¬ی این کار را به الگوریتم¬ها می¬دهد که هم یال-هایی را (با توجه به محدودیت¬ها) که در دور همیلتون جایی ندارد حذف کنند و هم، راس¬ ها بدون محدودیت و برای کاهش مسئله حذف گردد. همچنین اثبات می¬گردد که تبدیل گراف به گراف تبدیل یافته و عمل عکس آن در زمان چند جمله ¬ای انجام می¬شود و هزینه زمانی چند جمله ¬ای تبدیل، تأثیر چندانی بر هزینه زمانی نمایی الگوریتم¬ها ندارد. در مورد الگوریتم های به کار رفته، ما ابتدا از روش زنجیره مارکوف برای کمک گرفتن تصمیم گیری ها استفاده نمودیم و سپس از الگوریتم بهینه سازی اجتماع ذرات سعی در حل مسئله کردیم. در نتیجه مسئله در طول سه روند تبدیل گراف، کشف احتمالات آن و حل اکتشافی مورد حل و تجزیه و تحلیل قرار می¬گیرد. همچنین آزمایش های پیاده سازی شده در حل مسئله و مقایسه های انجام گرفته، نتایج برتری این الگوریتم را نسبت به دیگر الگوریتم ها بیان می¬کند.
- Abstract
- In this thesis, we try to improve the Hamiltonian problem by using algorithms that has been presented so far. A technique is provided for converting edges to vertices and vertices to edges, before using these algorithms. To convert, the transformed graph has a few limitations which the problem space will decrease during the process of algorithm besides; the algorithms allow not only the edges but also vertices to be removed to reduce the problem. This article proves that convert graph to transformed graph and reverse operation is performed in polynomial time not having a significant effect on the exponential cost of the algorithms. We're also benefiting of the Markov chain theorems and will use of the idea of the PSO algorithm. At the end, offer a meta-heuristic algorithms and compare our results.
