توسعه هسته برای حل تقریبی مساله کوله پشتی چند بعدی با چند انتخاب

سال انتشار: 1386
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,947

فایل این مقاله در 8 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ACCSI13_124

تاریخ نمایه سازی: 25 آبان 1386

چکیده مقاله:

هسته زیر فضایی از فضای جستجوی کل مساله است که در آن راه حل بهینه قرار دارد. در این مقاله ما روشی را برای شناسایی تقریبی هسته در مساله کوله پشتی چند بعدی با چند انتخاب عرضه میکنیم. این روش مبتنی بر تکنیک تجمیع محدودیتها و استفاده از حل خطی مساله میباشد. با استفاده از هسته توسعه یافته الگوریتم تقریبی برای حل مساله عرضه شده است. این الگوریتم یک الگوریتم شاخه و قید برای شمارش کامل هسته میباشد. نتایج ارزیابی تجربی نشان میدهند که جواب این الگوریتم، به طور متوسط، خطای نسبی کمتر از یک درصد نسبت به جواب بهینه را داراست که در مقایسه با بهترین الگوریتم ابتکاری برای حل این مساله بهتر عمل میکند.

کلیدواژه ها:

هسته ، کوله پشتی چند بعدی با چند انتخاب ، کوله پشتی ، هیوریستیک ، بهینه سازی

نویسندگان

طه قاسمی

دانشجوی کارشناسی ارشد، دانشکده کامپیوتر و فناوری اطلاعات دانشگاه صنع

محمدرضا رزازی

دانشیار، دانشکده کامپیوتر و فناوری اطلاعات دانشگاه صنعتی امیرکبیر، ت

مراجع و منابع این مقاله:

لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :
  • محمد رضا رزازی، طه قاسمی، الگوریتم شاخه و قید مبتنی ...
  • S. Martello, P. Toth. Knapsack Problems: Algorithms and Computer Implementa ...
  • M. S h ahad atullah-Khan, Quality adaptation in a multisession ...
  • Jager, Michael Chin, Optimising Quality- of-Service for the Composition of ...
  • Department of Electronic and Informations, University of Berlin, 2007. ...
  • Sbihi, Abdelkader, _ best first search exact algorithm for the ...
  • M. Hifi, M. Michrafy and A. Sbihi, _ Reactive Local ...
  • M. Mostofa Akbar, et. al, *Solving Mu ltidimensional Multiple- choice ...
  • E. Balas, E. Zemel, "An algorithm for large Zero-ore knapsack ...
  • Rafael] Parra- Hernandez _ Nikitas J. Dimopoulos, 00A New Heuristic ...
  • D. Pisinger, "A minimal algorithm for the 0-1 knapsack problem", ...
  • D. Pisinger, "A minimal algorithm jfor the Multiple- choice Knapsack ...
  • Jakob Puchinger, Giinther R. Raidl, Ulrich Pferschy, _ Core Concept ...
  • Gomes da Silva, Carlos, Joao Cl 1maco, Jos e Figueira, ...
  • P. Chu and J. Beasley, "A genetic algorithm Jfor the ...
  • Prabhakant Sinha, Andris A. Zoltners, "The Multiple- Choice Knapsack Problem", ...
  • Fred Glover, *Surrogate Constraint Duality in Mathematical Prog ramming _ ...
  • نمایش کامل مراجع