سلام دراري, في الحياة بصفة عامة كنكونوا مخيرين بين بزاف نتاع الحوايج ؟ وخاص فجميع الحالات نختاروا الاحسن بناتها, أو على الاقل نعتاقدوا أن دالك الخيار للي تخدناه هو الافضل.
Greedy Algorithms
في عالم البرمجة هناك المثل ! فأغلب الخوارزميات البرمجية إلا مقلتش كلها, كيتم تطبيق عليهم خواص الفرز بين النتائج لاختيار الأفضل بناتها.
مثلا : فتحديث 2016 ل محرك البحث جوجل كان ثورة بحثية فهد المجال تحث عنوان
How does Google decide which search results to display?
أو بمعنى أخر كيفاش ان جوجل تتقرر أي صفحة بحث تبين للمستخدم . للعلم فقط فاش اي مستخدم عادي كيقوم بالبحث على أي حاجة فجوجل فالنتيجة تتكون مجموعة نتاع الصفحات النتائج. وفعملية تحديد أي صفحة غادي تبان ليك، كيتخاد بعين الاعتبار مجموعة نتاع الاشياء بحال مكان الاقامة. اللغة. المعلومات للي مجموعة على داك الشخص (cookies)...
معلينا. شنو هي الحاجة جديدة للي عرفناها في سنة 2016… هي إمكانية مقارنة اكثر من جوج صفحات مع بعض وختيار الافضل ! تقدر تقول ان هدي حاجة بسيطة أننا نقارنوا كثر من جوج نتاع الحوايج مع بعض. أه بسيطة الى مكانش ف كل مقارن اكثر من مليون نتيجة.
على العموم في البرمجة ديما ناس تيتقاتلوا باش يصنعو خوارزميات تتخدم بكافئة اكثر, ومنين تنقول الكفائة يعني يكون وقت تشغيل الخوارزمية و المساحة للي تتاخد قلال.
وهدي هي المشكلة للي كانت في عملية المقارنة. أن شركة جوجل كان تتقلب على طريقة للي تقارن بيها ملايين نتائج البحث في اقل مدة ممكنة. في الاول كانت مقارنة جوج نتاع الصفحات فقط, ولكن من بعد تحسين من الخوارزمية ولا بالامكان نقارنوا اكثر من جوج صفحات مع نفس مدة التشغيل.
من هنا كتبان الأهمية نتاع الخوارزميات للي تيعاونوا في المقارنة. بطبيعة الحال كاين طرق غبية للي نقدروا نخدموا بيها باش نقارنوا. تتكون هد الطرق الغبية بديهية و ساحقة للمساحة التشغيل و وقت التشغيل. وكاين طرق دكية للي في الغالب تتكون تتعتامد على المنطق الرياضي في عملية المقارنة. تتعطينا مدة تشغيل و مساحة تشغيل قليلة بزاف.
ومن هد الطرق الدكية للي تنخدموا سواءا في عملية المقارنة أو عملية اختيار الافضل أو أو …
هي Greedy.
شنو هي Greedy ؟
بكل بساطة هي مجموعة نتاع شروط الفرز. كفاش ؟ تخايل معايا واحد الشخص تيقلب على احسن سيارة في العالم باش يشريها. الطريقة الغبية هي انه يدور على أي سيارة فهد العالم ويقرنها مع ختها حتا يلقا احسن سيارة في العالم. ولكن الا حطينا شي شروط للي غادي يعونونا في الاختيار, غادي تسهال القدية بزاف : مثلا نديروا معيار السعر أنو يكون فايت واحد الرقم. زائد معيار البلد المصنع نقدروا نزيدوا سنة التصنيع وهنا غتكون عملية البحث أكثر سهولة. هكذا تتخدم بكل بساطة خوارزمية greedy.
نحلوا مشكل برمجي بخوازمية greedy
المشكلة مشهورة وسميتها Array Partition I. بكل بساطة كيتم إعطاءك مصفوفة من الاعداد :
nums = [1,4,3,2]
المطلوب منك هو تلقا اكبر مجموع نتاع جوج اعداد صغيرة. كفاش ؟ مثال نيت على داك المصفوفة للي لفوق :
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
ومنه غيكون غيكون اكبر مجموع هو : 4
كفاش حلينا هد المشكلة. بكل بساطة درنا foor loop تتبدا من index رقم 0. وتتزيد بجوج نتاع الاعداد.
for(int i = 0; i < nums.length; i+=2)
من بعد قرنا بين جوج نتاع الاعداد ف كل دورة للي هوما
nums[i] and nums[i+1]
Nums = [1 , 4 , 3 , 2]
i i+1 i i+1
من بعد بكل بساطة خزنا اصغر متغير بين كل جوج نتاع الاعداد باش تعطينا في الاخير اكبر مجموع نتاع جوج نتاع الاعداد صغيرة في المصفوفة.
هكدا انكونوا حلينا هد المشكلة بستعمالب خوارزمبة ل greedy. وكان الاستعمال نتاعها فتحديد شرط إنا عدد ايتم الجمع نتاعو. وإنا عدد ما غديش يتم الجمع نتاعو.