ما مدى فائدة السماح لأستاذ كمبيوتر باستخدام خوارزمية جشعة لاستعادة سيارة مسروقة؟

بقلم سوبر نيرو

خلال عطلة عيد الميلاد العام الماضي، تعرضت شي يييو، الأستاذة المساعدة الدائمة والمشرفة على الدكتوراه في قسم علوم الكمبيوتر في جامعة نوتردام، والأستاذة المساعدة الدائمة في قسم الإلكترونيات، لعملية تفتيش سيارة على غرار هوليوود.

في غضون 24 ساعة من اختطاف السيارة، استخدم البروفيسور شي وظيفة تحديد المواقع الضبابية التي توفرها السيارة نفسها نهج جشع، تمكن بسرعة ودقة من تحديد موقع السيارة، واستعاد سيارته.

مراجعة الحالة

 

ساوث بيند 

شيكاغو

انطلقت

 

استراحة الغداء

اليوم الأول الساعة 12:00 صباحًا سرقة السيارات توقف البروفيسور شي في محطة وقود لإضافة الضغط إلى الإطارات. عندما كان البروفيسور شي يتفقد حالة السيارة، انتهز اثنان من رجال العصابات الفرصة لسرقة السيارة. في حالة من الذعر، وضع البروفيسور شي هاتفه المحمول سراً في الجيب خلف المقعد.
	اليوم الأول الساعة 17:00 مساءً ابدأ التتبع بعد أن اتصل بالشرطة دون جدوى، قرر البروفيسور شي العثور على موقع السيارة في أسرع وقت ممكن بنفسه. عدت إلى المدرسة وبدأت في التتبع، لكن موقع الهاتف لم يعد متاحًا.

اليوم الثاني الساعة 5:00 صباحًا تحديد المواقع الضبابية استخدم البروفيسور شي نظام Mazda Mobile Start (MMS) المدمج في السيارة للعثور على موقع السيارة الغامض، والذي كان على بعد أكثر من 80 كيلومترًا منه، مع خطأ في النظام يتراوح بين 6 و7 أمتار.

اليوم الثاني الساعة 7:00 صباحًا 60 مترا بعيدا عن بعضها البعض! توصل البروفيسور شي إلى استنتاج سريع من خلال الخوارزمية الجشعة:عندما نجد أن المسافة النسبية لم تعد تتناقص، توقف في الوقت المناسب واستمر في البحث في الاتجاه الرأسي. وباستخدام هذه الطريقة، نجح البروفيسور شي في تقليص المسافة إلى 60 مترًا فقط، وفي النهاية تمكن من تحديد موقعها بدقة في المرآب.

اليوم الثاني الساعة 9:00 صباحًا الشرطة عاجزة أثناء انتظار وصول الشرطة، اكتشف البروفيسور شي وشياو وانج أن اللصوص ربما لاحظوا شيئًا غير عاديًا وهربوا بالسيارة. سلم البروفيسور شي الهاتف للشرطة واستمر في تعقب السيارة، لكن الشرطة فشلت في البحث وفقًا لتوجيهات خوارزمية البروفيسور شي.

اليوم الثاني الساعة 10:00 صباحًا استعيد سيارتك! بعد أن استعاد البروفيسور شي هاتفه، واصل استخدام خوارزمية العثور على السيارة وأخيرًا عثر على السيارة المسروقة في موقف للسيارات. نجحت الشرطة في إرجاع السيارة للأستاذ شي.

خدعة البروفيسور شي النهائية في مطاردة السيارات: الخوارزمية الجشعة

تم حل حادثة سرقة السيارة المتوترة هذه في غضون 24 ساعة فقط، وكل ذلك بفضل تنفيذ البروفيسور شي واستنتاجه الدقيق للخوارزمية.

حتى الشرطة اندهشت من السرعة التي تمكن بها البروفيسور شي من حل المسألة:

ما كان ينبغي عليهم أن يعبثوا بأساتذة علوم الحاسوب! هل هم أغبياء؟ كيف لهم أن يسرقوا أساتذة علوم الحاسوب؟

وأوضح البروفيسور شي أن التكنولوجيا الأساسية لتحديد موقع المركبات هي في الواقع النهج الجشع الأكثر مباشرة في خوارزميات الكمبيوتر.

خوارزمية الجشع،تُعرف أيضًا باسم خوارزمية الجشع، وهي واحدة من أشهر الخوارزميات الكلاسيكية في الرياضيات وعلوم الكمبيوتر.

عندما يحل مشكلة، بغض النظر عما حدث قبل ذلك أو بعده، فهو يهتم فقط بالحالة الحالية ويحصل فقط على الحل الأمثل للمشكلة الفرعية الحالية. ومع ذلك، طالما يمكن استخدام الحل الأمثل المحلي الذي تم الحصول عليه في كل مرة، فمن الممكن استخلاص الحل الأمثل العالمي أو الهدف الأمثل.

قام البروفيسور شي بتطبيق الخوارزمية الجشعة على تقنية العثور على سيارة:
  عند القيادة، إذا وجدت أن المسافة النسبية بينك وبين السيارة لم تعد تتناقص، فتوقف عن القيادة على الفور.
  ثم واصل البحث في الاتجاه الرأسي.

هذا هو هيكل البحث الحلزوني الذي يضمن أنه يمكن أن يتقارب دائمًا في بحث رتيب في اتجاه المسافة المتناقصة.

وفي النهاية، ومع وجود شخصين فقط في السيارة، تمكن البروفيسور شي بسرعة من تحديد موقع السيارة المسروقة من خلال توجيه برنامج الملاحة مع وجود خطأ يبلغ 3 كيلومترات. كانت الخوارزمية الجشعة هي الأداة الأكثر دقة.

تطبيقات كلاسيكية أخرى للخوارزميات الجشعة

باعتبارها واحدة من الخوارزميات الكلاسيكية، فإن الخوارزمية الجشعة لا تستخدم على نطاق واسع.

لأن الخوارزمية الجشعة لا تستطيع تحقيق الحل الأمثل العالمي إلا من خلال حل استراتيجية الحل الأمثل المحلي. لذلك، يجب أن ننتبه إلى ما إذا كانت المشكلة مناسبة لاستراتيجية الخوارزمية الجشعة وما إذا كان الحل الذي تم العثور عليه هو بالتأكيد الحل الأمثل للمشكلة.

على سبيل المثال، في مشكلة حقيبة الظهر ومشكلة المسار، يتم استخدام الخوارزميات الكلاسيكية التالية لشرح جمال الجشع:

خوارزمية ديكستراإنها خوارزمية لحساب أقصر مسار من مصدر واحد (SSSP) في رسم بياني موجه مرجح، ابتكرها عالم الكمبيوتر إدسجر ديكسترا في عام 1956 ونشرت في عام 1959.

المشاكل التي يحلها هي:
بالنظر إلى الرسم البياني G ورأس المصدر v، ابحث عن أقصر مسار من v إلى جميع الرؤوس في الرسم البياني.

تم تصميم خوارزمية ديكسترا باستخدام نموذج الخوارزمية الجشعة:

قم بإنشاء أقصر مسار لكل رأس واحد تلو الآخر بالترتيب المتزايد لطول المسار.أثناء تنفيذ الخوارزمية، يجب الحفاظ على مجموعة رؤوس SS، والتي تخزن الرؤوس التي تم العثور على أقصر مسار لها. من الضروري أيضًا الحفاظ على مصفوفة المسافة dist، حيث يمثل dist[i] طول المسافة بين الرأس i وعقدة المصدر s.

• عند تهيئة S، فهو يتضمن فقط العقدة المصدر s؛ يتم تهيئة dist[]dist[]: dist[i]= arc[s][i]، arc هي مصفوفة الجوار للرسم البياني. يمثل V−SV−S مجموعة الرؤوس التي لم يتم العثور على أقصر مسار لها؛

• ضع distdist بترتيب تصاعدي، واختر أقصر مسار، وأضف الرؤوس المقابلة من V−SV−S إلى S، وفي كل مرة تتم إضافة رأس جديد u إلى S، يلزم تحديث distdist، أي ما إذا كان s يمكنه الوصول إلى رؤوس أخرى أقرب من خلال الرأس u. 
  هذا يعني أنه إذا كان dist[u] + arc[u][v] < dist[v]، فقم بتحديث dist[v]=dist[u]+arc[u][v] 

• كرر الخطوات المذكورة أعلاه حتى تصبح S=VS=V 

بيضة عيد الفصح: نوع جديد من الأسئلة من الخوارزمية الجشعة

لقد صادف ذلك اليوم الوطني للبلاد، ودعا الملك وزراءنا للعب لعبة بجوائز. أولاً، طلب من كل وزير أن يكتب عدداً صحيحاً على يده اليمنى واليسرى، وكتب الملك نفسه أيضاً عدداً صحيحاً على يده اليمنى واليسرى.

ثم دع هؤلاء الوزراء يصطفون في صف واحد، بحيث يقف الملك في مقدمة الفريق. بعد اصطفافهم، سيحصل جميع الوزراء على عدد من العملات الذهبية كمكافأة من الملك. عدد العملات الذهبية التي يتلقاها كل وزير هو:النتيجة هي حاصل ضرب الأرقام الموجودة على اليد اليسرى لجميع الأشخاص أمام الوزير، مقسومًا على الرقم الموجود على يده اليمنى، ثم يتم التقريب للأسفل.

لا يريد الملك أن يتلقى أي وزير مكافآت كبيرة بشكل خاص، لذا فهو يرغب منك مساعدته في إعادة ترتيب ترتيب الفريق بحيث يتلقى الوزير الذي يتلقى أكبر عدد من المكافآت أقل قدر ممكن من المكافآت.

(لاحظ أن الملك يكون دائمًا في مقدمة الصف.)