نقل قول:
نوشته اصلي بوسيله 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
موفق باشید