مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

video

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

sound

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

نسخه انگلیسی

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

بازدید:

272
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

دانلود:

65
مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

استناد:

اطلاعات مقاله همایش

عنوان

تا کردن متعامد خط کش در فضای d بعدی

صفحات

 صفحه شروع | صفحه پایان

چکیده

 مساله «تاکردن خط کش» به این صورت است که می خواهیم یک دنباله به هم پیوستن از پاره خط های با طولهای دلخواه را که از محل اتصالشان قابل تا شدن هستند را طوری در فضا d بعدی تا کنیم که همه پاره خطها در راستای یک محور از محورهای مختصات باشند. همچنین یک مشخصه خاص از کوچکترین جعبه ای که می تواند این خط کش را در خود جا دهد, نظیر مساحت یا محیط در فضای دو بعدی یا حجم در فضای سه بعدی کمینه گردد. این مساله حتی برای d=1 جزو مسائل NP-Complete محسوب می شود. تنها الگوریتم شبه چند جمله ای که تا به حال برای حل این مساله وجود داشت, فقط برای حالت d=1 و دارای پیچیدگی زمانی و حافظه O(n.L2) می باشد. در این مقاله الگوریتیم شبه جمله ای با استفاده از روش برنامه سازی پویا جهت حل این مساله در حالت کلی بیان گردیده است که دارای زمان O(n.d.Ld) و حافظه مصرفی O(n.Ld) است که در آن n تعداد قطعات خط کش و L طول بزرگترین قطعه می باشد. علاوه بر این نشان میدهیم که الگوریتم ارائه شده را می توان با تغییرات اندکی در پارامترهای آن برای حل انواع دیگری از مسائل مربوط به همین موضوع استفاده کرد.

استنادها

  • ثبت نشده است.

    • ارجاعات

  • ثبت نشده است.

    • استناددهی

    APA: کپی

    نوراله، علی، و رزازی، محمدرضا. (1382). تا کردن متعامد خط کش در فضای d بعدی. کنفرانس سالانه انجمن کامپیوتر ایران. SID. https://sid.ir/paper/815612/fa

    Vancouver: کپی

    نوراله علی، رزازی محمدرضا. تا کردن متعامد خط کش در فضای d بعدی. 1382. Available from: https://sid.ir/paper/815612/fa

    IEEE: کپی

    علی نوراله، و محمدرضا رزازی، “تا کردن متعامد خط کش در فضای d بعدی،” presented at the کنفرانس سالانه انجمن کامپیوتر ایران. 1382، [Online]. Available: https://sid.ir/paper/815612/fa

    مقالات مرتبط نشریه ای

  • ثبت نشده است.

    • مقالات مرتبط همایشی

  • ثبت نشده است.

    • طرح های مرتبط

  • ثبت نشده است.

    • کارگاه های پیشنهادی






    بازگشت به بالا
    telegram sharing button
    whatsapp sharing button
    linkedin sharing button
    twitter sharing button
    email sharing button
    email sharing button
    email sharing button
    sharethis sharing button