اختيار الحل الأمثل باستخدام خوارزمية Branch and Bound
نشر في جامعة تشرين
بتاريخ 2018
في مجال
والبحث باللغة
العربية
تحميل البحث
الملخص بالعربية
في المشكلة التي نعالجها, تحتاج شركة اتصالات إلى بناء مجموعة من الأبراج الخلوية لتوفير خدمة الاتصالات الخليوية للسكان في منطقة جغرافية. تم تحديد عدد من المواقع المحتملة لبناء الأبراج. يعتم اختيار هذه المواقع على عدة عوامل ، بما في ذلك مدى اتساق البرج مع البيئة المحيطة وارتفاع التضاريس, تتمتع الأبراج بمدى تغطية ثابت ، وبسبب قيود الميزانية ، لا يمكن بناء سوى عدد محدود منها . بالنظر إلى هذه القيود ، ترغب الشركة في توفير تغطية لأكبر قدر ممكن من السكان, والهدف هو اختيار في أي من المواقع المحتملة يجب أن تقوم الشركة ببناء الأبراج.
إن المشكلة التي شرحناها يمكن نمذجتها لتصبح أحد أمثلة مشكلة 0/1 knapsack الشهيرة لذلك شرحنا في الحلقة مفهوم مشكلة 0/1 Knapsack والطرق المستخدمة في الحل, وتوسعنا في الشرح عن خوارزمية Branch and Bound كونها تعتبر أفضلها.
المراجع المستخدمة
Knapsack problem- Wikipedia, the free encyclopedia. https://en.wikipedia.org/wiki/Knapsack_problem.
The Info List- Knapsack Problem.http://theinfolist.com/php/SummaryGet.php?FindGo=Knapsack%20Problem.
Hristakeva, Maya and DiptiSrestha. “Different Approaches to Solve the 0/1 Knapsack Problem”, MICS 2005 proceedings.www.micsymposium.org/mics_2005/papers/paper102.pdf.
Levitin, Anany. The Design and Analysis of Algorithms. New Jersey: Pearson Education Inc., 2003.
Branch and Bound- Wikipedia, the free encyclopedia. https://en.wikipedia.org/wiki/Branch_and_bound
A Study of Performance Analysis on Knapsack Problem, International Journal of Computer Applications (0975 – 8887) National Conference on “Recent Trends in Information Technology” (NCRTIT-2016). Pushpa S.K. Information Science Department BMS Institute of Technology Bangalore, India Mrunal T.V. Information Science Department BMS Institute of Technology Bangalore, India C. Suhas Information Science Department BMS Institute of Technology Bangalore, India
Branch and bound, Geeksforgeeks https://www.geeksforgeeks.org/branch-and-bound-set-2-implementation-of-01-knapsack/
A MIXED INTEGER LINEAR PROGRAMMING APPROACH FOR DEVELOPING SALARY ADMINISTRATION SYSTEMS, 12-2016 Taner Cokyasar University of Tennessee, Knoxville, cokyasar@vols.utk.edu