كيفية حل مشكلة السارق في المنزل

تخيل أنك لص تحاول سرقة أكبر قدر ممكن من الذهب من الحي.

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

تحظى مشكلة House Robber بمشاكل في هندسة البرمجيات ، وربما يرجع ذلك إلى جميع تطبيقاتها العملية (حسب قوله ، نأمل أن يسخر من ذلك).

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

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

لنبدأ بالنظر في إعداد المشكلة: المدخلات والمخرجات والقيود ، وما إلى ذلك. مع أي مشكلة ، من الجيد دائمًا توضيح ماهية كل هذه الأشياء وماذا تعني.

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

سيكون ناتجك عددًا صحيحًا واحدًا ، ويمثل أقصى كمية من الذهب يمكنك سرقتها من الحي.

هكذا على سبيل المثال:

عندما يتعلق الأمر بحل المشكلات ، من الجيد دائمًا أن نبدأ بمثال بسيط بما فيه الكفاية حتى نتمكن من استعراض الإجابة ، ولكن معقدًا بدرجة كافية حتى لا تكون تافهة. سيكون هذا فحصًا معقولًا لمناهجنا وسيوفر بيانات قيمة (ملاحظات) حول المشكلة.

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

يمكننا أيضًا البدء في عمل بعض التنبؤات حول تعقيد الوقت / الفضاء. غالبًا ما لا يمنحك القائمون بإجراء المقابلات قيدًا محددًا لأن ذلك قد يكون تلميحًا كبيرًا. سيقولون فقط شيئًا مثل "افعل ما بوسعك".

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

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

بالنظر إلى أننا يجب أن نسرق من مجموعة فرعية من المنازل للعثور على الكمية المثلى من الذهب لسرقة ، ما هي مجموعات فرعية نحتاج لاختبار؟

الاجابة:

إذن ما الذي يشكل مجموعة صالحة من المنازل؟ أي ترك يترك منزلًا واحدًا على الأقل بين أي منزلين يتعرضان للسرقة.

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

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

إليك ما يبدو في مثالنا السابق:

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

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

ترجمة ذلك إلى رمز مستعار منخفض المستوى (مزيج من اللغة الإنجليزية والكود):

إليك الشكل الذي يظهر به الرمز في JavaScript ، باستخدام تكرار طريقة المساعدة:

الآن دعونا نحلل التعقيد الزمني لهذا النهج. عند التفكير في هذا بسذاجة ، قد يبدو اختبار كل المجموعات الممكنة من المنازل وكأنه كثير من العمل ، خاصة عندما يكون الحي كبيرًا (العديد من العناصر في المجموعة).

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

طريقة العمل من خلال هذا بمفردك هي من خلال مقارنة حجم العمل الإضافي الذي يجب عليك القيام به عن طريق إضافة 1 منزل إضافي إلى الجوار. في هذا المثال ، هذا يعني معرفة عدد المجموعات الإضافية التي تم إنشاؤها وتحتاج إلى اختبارها عند إضافة منزل آخر إلى الحي.

إليك كيفية القيام بذلك في مثال بسيط:

يتم اختبار التوليفات السوداء عند إعطائها كلاً من المدخلات ، واللون الأحمر مخصص فقط للمدخلات الأكبر

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

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

يمكنك حتى كتابة التعليمات البرمجية لمعرفة عدد مرات إصابة الحالة الأساسية بأحجام مختلفة للإدخال:

حاول تشغيل هذا الرمز. نرى ما يطبع.

تنبيه المفسد:

أعلم أنني كنت في مهب

لكن من بعض النواحي ، لا ينبغي أن يكون الأمر مفاجأة إذا نظرت حقًا إلى مجموعتي الكود جنبًا إلى جنب.

إذا قمت بالفعل برسم الأرقام في جدول النتائج ، فستحصل على شيء من هذا القبيل في مقياس السجل:

عند النظر في التعقيد الكلي للمساحة ، نحتاج إلى فحص كل عدد المكالمات الموجودة في مكدس المكالمة في أي وقت ، وأي مساحة إضافية نستخدمها خارج العودية:

عظيم! لدينا حل عملي لمشكلة السارق في المنزل.

وهذا هو بالضبط المكان الذي سيطلب منك القائم بإجراء المقابلة من خلاله إجراء تحسينات. لذلك دعونا نعود إلى لوحة الرسم ونقدم بعض الملاحظات:

حدسي ، هناك الكثير من المجموعات غير المرغوب فيها التي نختبرها. السبب في ذلك هو أننا نختبر الكثير من المجموعات الأصغر الموجودة في المجموعات الكبيرة. هذا يعني أن هناك مجموعات أفضل تمامًا من غيرها. هذا يعني أنه يمكننا البدء في التفكير في كيفية التخلص من هذه المجموعات الأصغر.

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

هذا ربما يستحق مقالة قصيرة خاصة به

فما هي البصيرة الرئيسية لهذه المشكلة؟

أقصى مسافات بين المنازل * نسرق منها

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

تذكر أن هذه تفاصيل مهمة للمشكلة. إنه شيء تريد أن تسأل عنه.

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

حتى مع هذا المثال ، يمكننا استخلاص استنتاج مهم:

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

دعنا نرى:

يبدو أن النمط يحمل. ولاحظ أنواع الأمثلة التي جربناها. هم مع حلول واضحة يمكننا التحقق.

إذن ما هي الخطوة التالية؟

دعنا نعيد كتابة كل تلك المخرجات كجدول. ستلاحظ أن كل ناتج يتوافق مع إضافة منزل إلى الحي. إليك ما يعنيه ذلك:

في هذه المرحلة ، يجب أن يكون واضحًا ما تعنيه هذه الجداول ، ويجب أن يكون لديك بعض الحدس حول سبب نجاح هذا النهج. والسؤال الرئيسي الذي يجب أن يكون لديك هو "كيف يمكننا إنشاء هذه الجداول؟"

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

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

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

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

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

الأمور تزداد صعوبة في العنصر الثالث. ما هي خياراتنا؟

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

في هذه الحالة ، سنقوم بإضافة الرقم 3في هذه الحالة ، سنقوم بتخطي الرقم والاحتفاظ بـ 5.

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

الآن دعونا نضيف منزلًا رابعًا. ماذا يجب أن نضيف إلى طاولتنا؟

حدسيًا نعلم أن الإجابة هي 8 ، لكن كيف نصل إلى هذا الرقم؟ نحن نضيف واحدة من الأطفال الخمسة ، لكن أي واحد منهم؟

للإجابة على هذا ، دعونا ننظر في إضافة رقم آخر.

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

إذا نظرنا إلى طاولتنا ، يمكننا أن نرى أننا نضيف قيمة المنزل الجديد ، إلى مؤشرات 2 gold max بحد أقصى. لماذا ا؟ لأن هذا هو الحد الأقصى لمقدار الذهب الذي قمنا بتجميعه من مدخلات أصغر وحدتين (ويعرف أيضًا باسم اثنين من المنازل أقل).

في الأساس ، ما نطلبه هنا هو "هل يجب أن نضيف هذا المنزل الجديد وتخطي المنزل السابق أم يجب علينا تخطي هذا المنزل الجديد وسرقة البيت السابق؟" ، ونحن نفعل ذلك في كل مرة نضيف فيها منزلًا جديدًا.

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

مع قول ذلك ، دعنا نترجم هذا إلى رمز زائف:

"لكل منزل في القائمة ، إما أن تضيف الذهب إلى أقصى مؤشرات الذهب 2 أو تبقي مؤشر max gold 1 مرة أخرى."

إذا نظرنا إلى مثالين آخرين ، يمكننا أن نرى أن النمط يثبت:

في المثال الأول ، نضيف الرقم 5 و 8 معًا لأن هذا المبلغ أكبر من 9.

في المثال الثاني ، نحافظ على الرقم 13 ، لأن هذا أكبر من إضافة 1 و 9.

إن ما نعود إليه في النهاية واضح تمامًا: إنه العنصر الأخير في مجموعة max_gold.

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

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

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

فيما يلي الحلول المثلى:

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

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

ترميز سعيد!