Search
۱۴۰۳-۰۱-۰۹
  • :
  • :

تعبیه ی هندسی درخت درنقاط داخل یک چندضلعی با حداقل تعداد خم

تعبیه ی هندسی درخت درنقاط داخل یک چندضلعی با حداقل تعداد خم

چکیده مقاله:
چکیده N گره را روی N دراین مقاله در نظر داریم تا یک درخت با رأس تعبیه کنیم این تعبیه باید n نقطه داخل یک چند ضلعی با به گونهای باشد که تعداد خمهای درخت حاصل حداقل شود . ایدهی اصلی الگوریتم جدید مدل کردن مسئله به صورت مسئلهی تطبیقدهی گرافها واستفاده از الگوریتمهای تطبیقدهی گراف است که منجر به بررسی مسئله ی فاصله ی پیوندی و مسیر با حداقل تعداد لینک می شود، سپس با به کار بردن مفهوم تصحیح خطا ویافتن یک تابع هزینه ی مناسب و استفاده از روش تجزیهی گرافها، تطبیقدهی گراف ها ر ا با حداقل هزینه برای به حداقل رساندن تعداد خم انجام میدهیم است. O(N2n+N و الگوریتم دارای پیچیدگی محاسباتی ( ۴ کلیدواژگان: تعبیه ی هندسی، تعبیه ی درخت در مجموعه نقاط، به حداقل رساندن خم، تطبیقدهی گراف.

 

نویسندگان: اکرم سپهری ، علیرضا باقری

منبع :نشریه فناوری اطلاعات و ارتباطات ایران

لینک دریافت کامل مقاله




پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *