• فهرست مقالات


      • دسترسی آزاد مقاله

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