نمايش پست تنها
قديمي ۰۶-۱۶-۱۳۹۲, ۰۲:۱۲ بعد از ظهر   #2 (لینک دائم)
babak_1234 Male
Moderator
 
آواتار babak_1234
 
تاريخ عضويت: شهريور ۱۳۸۸
محل سكونت: تهران
پست ها: 252
تشكرها: 1
140 تشكر در 108 پست
My Mood: Khonsard
پيش فرض

نقل قول:
نوشته اصلي بوسيله gharli نمايش پست
سلام کسی میتونه به من کمک کنه یا یک شبه کد از این مسله رو برای من بفرسته؟
مسئله «تاکردن خط کش» به این صورت است که می خواهیم یک دنباله به هم پیوسته از پاره خط هايی با طولهای دلخواه را که از محل اتصالشان قابل تا شدن هستند را طوری در فضا d بعدی تا کنیم که همه پاره خطها در راستای یک محور از محورهای مختصات باشند. همچنین یک مشخصه خاص ازکوچکترین جعبه ای که می تواند این خط کش را در خود جادهد، نظیر مساحت یا محیط در فضای دو بعدی یا حجم در فضای سه بعدی کمینه گردد. این مسئله حتی برای d=1 جزو مسائل NP-Complete محسوب میشود.



در اينجا یک پاره خط، که تعدادی مفصل بر روی آن مشخص شده اند، داریم كه هر پاره خط ميتواند حول مفاصل دو طرفش عمل دوران را تا ٣٦٠ درجه انجام بدهد. هدف كوتاهترين طول حاصل از تاکردن اين پاره خط ها بر روی خط افقی است.



سلام دوست من

مساله خیلی جالبی بود
توی این مقالات مساله همراه با الگوریتم برای حل ارائه شده.

http://citeseerx.ist.psu.edu/viewdoc...=rep1&type=pdf
http://www.jucs.org/jucs_14_4/a_line..._nourollah.pdf

موفق باشید
babak_1234 آفلاين است   پاسخ با نقل قول