تاکردن متعامد خط کش در فضای d بعدی
Publish place: 9th Annual Conference of Computer Society of Iran
Publish Year: 1382
Type: Conference paper
Language: Persian
View: 1,976
This Paper With 8 Page And PDF Format Ready To Download
- Certificate
- I'm the author of the paper
Export:
Document National Code:
ACCSI09_013
Index date: 24 January 2008
تاکردن متعامد خط کش در فضای d بعدی abstract
مسئله «تاکردن خط کش» به این صورت است که می خواهیم یک دنباله به هم پیوستن از پاره خط های با طولهای دلخواه را که از محل اتصالشان قابل تا شدن هستند را طوری در فضا d بعدی تا کنیم که همه پاره خطها در راستای یک محور از محورهای مختصات باشند. همچنین یک مشخصه خاص ازکوچکترین جعبه ای که می تواند این خط کش را در خودجا دهد، نظیر مساحت یا محیط در فضای دو بعدی یا حجم در فضای سه بعدی کمینه گردد. این مسئله حتی برای d=1 جزو مسائل NP-Complete محسوب میشود. تنها الگوریتم شبه چند جمله ای که تا به حال برای حل این مسئله وجود داشت، فقط برای حالت d=1 و دارای پیچیدگی زمانی و حافظه O(n.L2) می باشد. در این مقاله الگوریتیم شبه جمله ای با استفاده از روش برنامه سازی پویا جهت حل این مسئله درحالت کلی بیان گردیده است که دارای زمان O(n.d.Ld) و حافظه مصرفی O(n.Ld) است که در آن n تعداد قطعات خط کش و L طول بزرگترین قطعه می باشد. علاوه بر این نشان میدهیم که الگوریتم ارائه شده را می توان با تغییرات اندکی در پارامترهای آن برای حل انواع دیگری از مسائل مربوط به همین موضوع استفاده کرد.
تاکردن متعامد خط کش در فضای d بعدی Keywords:
تاکردن متعامد خط کش در فضای d بعدی authors
علی نوراله
آزمایشگاه تحقیق و توسعه نرم افزار، دانشکده مهندسی کامپیوتر دانشگاه
محمدرضا رزازی
آزمایشگاه تحقیق و توسعه نرم افزار، دانشکده مهندسی کامپیوتر دانشگاه
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :