Artificial Intelligence - هوش مصنوعی - -مسئله تاکردن خط کش (ruler folding problem)

Artificial Intelligence - هوش مصنوعی (http://artificial.ir/intelligence/)

- الگوریتم و پردازش تکاملی (http://artificial.ir/intelligence/forum12.html)

- - -مسئله تاکردن خط کش (ruler folding problem) (http://artificial.ir/intelligence/thread12000.html)

-مسئله تاکردن خط کش (ruler folding problem)

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

http://upload7.ir/images/00112223580315702962.jpg

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

نقل قول:

نوشته اصلي بوسيله gharli (پست 30072)

سلام دوست من

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

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

موفق باشید

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

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