gharli

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



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

babak_1234

سلام دوست من

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

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

موفق باشید

gharli

ممنونم.این مسله رو باید با یکی از الگوریتم های تکاملی حلش کنیم.خیلی ممنونم میشم توی این زمینه هم کمکم کنید.

mahdiii

اگه آشنایی با الگوریتم ژنتیک دارین
در این الگوریتم گام اول کد کردن و ساختن جمعیت اولیه هست
خوب برای کد کردن به این صورت میتونین عمل کنین که مثلا در شکل بالا که چهار تکه دارین برای تاکردن خط کش به این صورت عمل می کنین که باید جهت اونها تعیین بشه. مثلا اول بخش 7 هست. بسته به دقت بازه 0 تا 360 درجه رو به بازه هایی گسسته می کنین مثلا 8 بازه 45 درجه ای که به سه بیت نیازه داره. خوب بعدش برای تکه بعدی یعنی سه دوباره برای تعیین زاویه اش به سه بیت نیازه و برای بعدیام به همین صورت.
پس کلا به 4*3==12 بیت نیاز هست که میشه برای افزایش دقت تقسیم بازه 0 تا 360 بیشتر بشه و خوب تعداد بیتهایی که اونهارو کد میکنه هم بیشتر میشه. خوب جمعیت اولیه ساخته میشه مثلا 100 تا کد 12 بیتی صفر و یک. بر اساس جمعیت تصادفی از صفر و یکها و برای هر کدوم . بعدش برای هر کدوم مقدار طول اونها به دست میاد (تابع ارزیاب) و بر اساس بهتر بودن هر کدوم (در اینجا کمترین بهترین است)با احتمال بیشتری برای تولید فرزندان و نسل بعدی اون کروموزوم انتخاب میشه. سپس عمل جهش و تقاطع برای ساختن جمعیت بعدی و نسل بعدی اعمال میشه و این اعمال تکرار میشه.
اگه وقت داشتم کدشو میزدمموفق باشین