تجزیه و تحلیل فضای برازندگی جواب های مسئله طولانی ترین مسیر ساده در گرافها
- سال انتشار: 1394
- محل انتشار: دوازدهمین کنفرانس بین المللی مهندسی صنایع
- کد COI اختصاصی: IIEC12_241
- زبان مقاله: فارسی
- تعداد مشاهده: 521
نویسندگان
استادیار مهندسی صنایع، دانشگاه تربیت مدرس، تهران
دانشجوی کارشناسی ارشد مهندسی صنایع ، دانشگاه تربیت مدرس، تهران
دانشجوی کارشناسی ارشد مهندسی صنایع ، دانشگاه تربیت مدرس، تهران
چکیده
مسئل طولانیترین مسیر روی گراف ها یکی از مهمترین مسائل در تئوری گراف بوده و عبارت است از یافتن مسیری ساده با بیشترین تعداد رئوس بین دو راس معین یا ماکزیمم مجموع طو ل های یال ها بین بین دو راس معین در گراف. این مسئله کاربردهای مختلفی در حوزه ای گوناگون دارد، که از مهمترین آنها می توان به یافتن مسیر بحرانی در سیستم VLSI و بدست آوردن طولانیترین مسیر در شبکه صف اشاره کرد. از آنجایی که تعداد بسیار معدودی الگوریتم حل در زمان چند جمله ای برای کلاس ها (انواع) خاصی از گراف ها برای این مسئله توسعه داده شده است، در مقاله حاضربرای نخستین بار، تجزیه و تحلیل فضای برازندگی جواب های مسئله بر اساس شاخصهای آماری مستخرج از اجرای ١٠٠٠ مرتبه جستجوی محلی ساده انجام شده که در نتیجه آن تخمین زده شد بهینه های محلی این مسئله در چندین نقطه فضا تجمع یافته اند و لذا روشهای حل مبتنی بر جمعیت به جواب های بهتری برای مسئله مذکور در گرافهای مختلف دست خواهند یافت. این فرضیه با حل چند مسئله طولانیترین مسیر توسط الگوریتم های فراابتکاری مبتنی بر تک جواب (شبیه سازی تبرید) و مبتنی بر چند جواب (الگوریتم ژنتیک) مورد آزمون قرار گرفت، و با توجه به برتری جواب هایتولیدی الگوریتم ژنتیک، مورد پذیرش قرار گرفت. نتایج این تحلیل نشان میدهد که میانگین اختلاف نتایج الگوریتم ژنتیک پیشنهادی برای یک مسئله بهینه، ٠٫٠٢۴٣۶٣ است.کلمات کلیدی:مسئله طولانیترین مسیر؛کلیدواژه ها
مسئله طولانی ترین مسیر؛ مسیر همیلتونی؛ الگوریتم فراابتکاری؛ تجزیه و تحلیل فضای برازندگی جوابمقالات مرتبط جدید
- پیشرفت های کلیدی در مهندسی مکانیک: شبیه سازی تولید، فناوری های نوین و آینده پژوهی
- نقش مدیریت تقاضا و یادگیری ماشین در بهینه سازی سیستم سلامت
- The Impact of Safety Training Programs on Reducing Accidents and Improving Working Conditions in Industrial Environments
- Study and Necessity of Using Intelligent Transportation Systems (ITS) and Their Impact on Transportation Management in Tehran
- بررسی تاثیر مدیریت فراموشی سازمانی بر مدیریت دانش در سازمان های دولتی
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.