مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

نسخه انگلیسی
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

video

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

sound

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

نسخه انگلیسی

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

بازدید:

424
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

دانلود:

109
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

استناد:

اطلاعات مقاله نشریه

عنوان

رویکردی جدید برای شمارش یا بهینه سازی مثلث بندی مجموعه نقاط در صفحه مبتنی بر MIS

صفحات

 صفحه شروع 249 | صفحه پایان 255

چکیده

 مثلث بندی مجموعه نقاط S در صفحه, برابر با تعبیه مسطح یک گراف مسطح مستقیم الخط بیشین (با بیشترین یال) روی مجموعه نقاط است به طوری که مجموعه رئوس گراف دقیقاً همان مجموعه نقاط داده شده باشد. دو مسئله مهم در این زمینه مورد تحقیق است. الف) به چند طریق می توان مجموعه نقاط S را مثلث بندی کرد ب) کدام مثلث بندی بر اساس ویژگی خاصی بهینه است. مسئله اول یک مسئله باز است و به جز در شرایط خاص که دارای رابطه بسته می باشد تا به حال الگوریتمی با زمان چندجمله ای برای آن در حالت کلی ارائه نشده است. مسئله دوم نیز در حالتی که هدف پیداکردن مثلث بندی که مجموع طول یال های آن کمترین باشد یک مسئله NP-HARD است (MWT), لذا تحقیقات در راستای ارائه الگوریتم های مکاشفه ای, فرامکاشفه ای یا تقریبی برای این دو حالت انجام شده است. در این مقاله روشی ارائه شده که در آن با تولید گراف تقاطع حاصل از تمامی پاره خط های حاصل از تمامی زوج نقاط S تولید می شود و سپس الگوریتم هایی برای تولید همه مجموعه های مستقل بیشین (MIS) گراف تقاطع و همچنین روشی برای شمارش تعداد این مجموعه ها ارائه می شود. این رویکرد تولید گراف تقاطع و تبدیل مسئله مثلث بندی به مسئله مجموعه مستقل بیشین نگاهی جدید به مسئله مثلث بندی در هر دو حالت الف و ب محسوب می شود و از آنجا که ارائه الگوریتم برای مسئله الف یا ب به خاطر ذات هندسی بودن آن دشوار است لذا با رویکرد مطرح شده در این مقاله, تمامی الگوریتم هایی که تا به حال برای مسئله MIS مطرح شده است را می توان برای حل مسئله مثلث بندی در هر دو حالت الف یا ب به کار برد. تکنیک تبدیل مسئله مثلث بندی به مسئله MIS رویکردی است که تا به حال روشی مبتنی بر آن برای حل مسایل شمارش تعداد طرق مثلث بندی یا مثلث بندی با کمترین وزن گزارش نشده است. علاوه بر این یک روش تخمینی مکاشفه ای برای تعیین متوسط تعداد حالات مثلث بندی ارائه خواهد شد که نتایج پیاده سازی نشان می دهد روی نمونه هایی از ورودی نزدیک به مقدار دقیق هستند.

استنادها

  • ثبت نشده است.

    • ارجاعات

  • ثبت نشده است.

    • استناددهی

    APA: کپی

    نوراله، علی، و رضایت، زهرا. (1399). رویکردی جدید برای شمارش یا بهینه سازی مثلث بندی مجموعه نقاط در صفحه مبتنی بر MIS. مهندسی برق و مهندسی کامپیوتر ایران - ب مهندسی کامپیوتر، 18(3 )، 249-255. SID. https://sid.ir/paper/405479/fa

    Vancouver: کپی

    نوراله علی، رضایت زهرا. رویکردی جدید برای شمارش یا بهینه سازی مثلث بندی مجموعه نقاط در صفحه مبتنی بر MIS. مهندسی برق و مهندسی کامپیوتر ایران - ب مهندسی کامپیوتر[Internet]. 1399؛18(3 ):249-255. Available from: https://sid.ir/paper/405479/fa

    IEEE: کپی

    علی نوراله، و زهرا رضایت، “رویکردی جدید برای شمارش یا بهینه سازی مثلث بندی مجموعه نقاط در صفحه مبتنی بر MIS،” مهندسی برق و مهندسی کامپیوتر ایران - ب مهندسی کامپیوتر، vol. 18، no. 3 ، pp. 249–255، 1399، [Online]. Available: https://sid.ir/paper/405479/fa

    مقالات مرتبط نشریه ای

    مقالات مرتبط همایشی

  • ثبت نشده است.

    • طرح های مرتبط

  • ثبت نشده است.

    • کارگاه های پیشنهادی






    بازگشت به بالا
    telegram sharing button
    whatsapp sharing button
    linkedin sharing button
    twitter sharing button
    email sharing button
    email sharing button
    email sharing button
    sharethis sharing button