محبوبترین نویسندگان :
نویسندگان مقالات پربازدید :
نوزدهمین کنفرانس ملی سالانه انجمن کامپیوتر ایران
جزئیات رویداد
همایش ، رویداد ، ژورنال
اینستاگرام تی پی بین
حوزه های تحت پوشش رویداد

  • ارائه یک الگوریتم حریصانه جهت تجزیه یکنواخت چندضلعی های ساده و حفره دار

    نویسندگان :
    کلمات کلیدی :
    جزئیات بیشتر مقاله
    • تاریخ ارائه: 1392/07/24
    • تاریخ انتشار در تی پی بین: 1392/07/24
    • تعداد بازدید: 1162
    • تعداد پرسش و پاسخ ها: 0
    • شماره تماس دبیرخانه رویداد: -
     در این مقاله به ارائه یک الگوریتم جهت تجزیه یکنواخت چندضلعی های ساده و حفره دار می پردازیم. این الگوریتم بدون استفاده از نقاط کمکی، یک چندضلعی را به صورت یکنواخت تجزیه می کند. هدف از ارائه این الگوریتم، دستیابی به تجزیه ای تقریبا کمینه در یک زمان قابل قبول است. تجزیه کمینه یکنواخت یک چندضلعی حفره دار، در حالتی که استفاده از نقاط کمکی مجاز نیست، یک مسئله –np سخت است. استفاده از الگوریتم هایی که منجر به تجزیه تقریبا کمینه می شوند، یکی از راهکارهای عملی است  در طراحی این الگوریتم، دو مقوله کمینگی تجزیه و زمان اجرا مورد توجه قرار گرفته است. این الگوریتم به صورت حریصانه تلاش می کند عمل تجزیه را به صورت کمینه انجام دهد. با وجود این که تضمینی در مورد بدست آمدن جواب کمینه وجود ندارد، اما نتایج پیاده سازی این الگوریتم و مقایسه عملی آن با برخی از الگوریتم های موجود، موثر بودن این راهکار را نشان می دهد. بخشی از زمان اجرای این الگوریتم با استفاده از پارامتری به نام « حداکثر عمق جستجو » کنترل می شود. با تنظیم مقدار این پارامتر و با توجه به کاربرد مسئله، می توان بین زمان اجرا و کمینه بودن تجزیه یکی را ترجیح داد و یا این که تعادلی بین آنها بوجود آورد.

سوال خود را در مورد این مقاله مطرح نمایید :

با انتخاب دکمه ثبت پرسش، موافقت خود را با قوانین انتشار محتوا در وبسایت تی پی بین اعلام می کنم
مقالات جدیدترین رویدادها
مقالات جدیدترین ژورنال ها