ما هي مسافة مانهاتن (Manhattan Distance) في الخوارزميات؟ شرح مبسّط مع أمثلة
مسافة مانهاتن (Manhattan Distance) هي طريقة لقياس البُعد بين نقطتين عبر جمع الفروق المطلقة لإحداثياتهما، أي أنك تتحرك أفقيًا ثم عموديًا فقط، دون أي خط مائل مباشر. إذا كانت لديك نقطتان (x₁, y₁) و(x₂, y₂) فإن المسافة بينهما تُحسب هكذا:
Manhattan distance = |x₁ − x₂| + |y₁ − y₂|
تخيّل أنك تقود سيارة أجرة في مدينة نيويورك: لا يمكنك اختراق المباني قطريًا، بل تسير في شوارع أفقية ورأسية حتى تصل. هذا بالضبط ما تقيسه مسافة مانهاتن، ولهذا تُعرف أيضًا باسم «مسافة سيارة الأجرة» (Taxicab distance) أو «معيار L1».
مثال محلول بسيط
لنفترض نقطتين: A = (1, 2) و B = (4, 6).
- احسب الفرق في المحور الأفقي: |1 − 4| = 3
- احسب الفرق في المحور الرأسي: |2 − 6| = 4
- اجمع القيمتين: 3 + 4 = 7
فمسافة مانهاتن بينهما تساوي 7 وحدات. لاحظ أن الجواب رقم صحيح وسهل، لأننا لم نستخدم أي جذر تربيعي، على عكس المسافة الإقليدية التي كانت ستعطي √(3² + 4²) = 5.
لماذا يفضّلها المبرمجون؟
- الحساب سريع جدًا: عمليات طرح وجمع فقط، بلا جذور ولا أُسّ، وهو ما يُحدث فرقًا حقيقيًا عند تكرار العملية ملايين المرات.
- مناسبة للشبكات المربعة: في أي مسألة تتحرك فيها العناصر أعلى/أسفل/يمين/يسار فقط (مثل رقعة شطرنج أو خريطة لعبة مقسّمة إلى مربعات)، تعكس مسافة مانهاتن الواقع بدقة أكبر من الخط المستقيم.
- أكثر استقرارًا في الأبعاد العالية: عند التعامل مع بيانات ذات عشرات أو مئات الخصائص، يميل معيار L1 إلى التأثر أقل بالقيم الشاذة مقارنة بالمسافة الإقليدية.
مسافة مانهاتن أم المسافة الإقليدية؟
كثيرون يخلطون بينهما، والفرق الجوهري هو: هل الحركة القطرية مسموحة أم لا؟
| المعيار | مسافة مانهاتن (L1) | المسافة الإقليدية (L2) |
|---|---|---|
| القانون | مجموع الفروق المطلقة | الجذر التربيعي لمجموع مربعات الفروق |
| شكل المسار | خطوات أفقية ورأسية | خط مستقيم مائل |
| السرعة الحسابية | أسرع (جمع وطرح) | أبطأ (تربيع وجذر) |
| الأنسب لـ | الشبكات، الحركة رباعية الاتجاهات | الفضاء الحر، الحركة في أي اتجاه |
| مثال على (3,4) | 7 | 5 |
القاعدة العملية: استخدم مانهاتن حين تكون الحركة مقيّدة بشبكة، والإقليدية حين يستطيع العنصر التحرك في أي اتجاه بحرية.
أين تُستخدم فعليًا في الخوارزميات؟
1. خوارزمية A والبحث عن المسار:* أشهر استخدام على الإطلاق. عندما تبحث خوارزمية A* عن أقصر طريق داخل شبكة تُسمح فيها الحركة في أربعة اتجاهات فقط، تُستخدم مسافة مانهاتن كـ«دالة تقدير» (Heuristic) لتخمين المسافة المتبقية إلى الهدف. هي هنا خيار مثالي لأنها لا تبالغ أبدًا في تقدير المسافة الحقيقية، فتبقى الخوارزمية دقيقة (Admissible) وتضمن إيجاد أقصر مسار.
2. تصنيف البيانات والتجميع: في خوارزميات مثل k-الأقرب جيرانًا (k-NN) والتجميع العنقودي (Clustering)، تُستخدم مسافة مانهاتن أحيانًا لقياس التشابه بين العينات بدلًا من الإقليدية، خصوصًا حين تحتوي البيانات على خصائص كثيرة أو قيم متطرفة.
3. البحث عن الجار الأقرب في هياكل مثل KD-Tree: عند تخزين نقاط في شجرة مكانية للبحث السريع عن أقرب نقطة، يمكن اعتماد مسافة مانهاتن كمقياس للبُعد أثناء التنقل بين عُقد الشجرة.
4. معالجة الصور والرؤية الحاسوبية: تُستخدم لقياس الفرق بين قيم البكسلات أو لحساب تحويلات المسافة (Distance Transform).
نصيحة عملية وخطأ شائع
الخطأ الأكثر شيوعًا هو استخدام مسافة مانهاتن كدالة تقدير في شبكة تسمح بالحركة القطرية. في هذه الحالة تبالغ مانهاتن في تقدير المسافة، فتفقد خوارزمية A* ضمان أقصر مسار. إذا كانت الحركة القطرية مسموحة، استخدم بدلًا منها «مسافة تشيبيشيف» (Chebyshev) أو صيغة القطر (Octile). القاعدة الذهبية: طابِق دالة التقدير مع قواعد الحركة المسموحة، وإلا حصلت على نتائج غير مثلى دون أن تدرك السبب.
الأسئلة الشائعة
هل تعمل مسافة مانهاتن في أكثر من بُعدين؟ نعم. المبدأ نفسه يمتد لأي عدد من الأبعاد: تجمع الفروق المطلقة لكل الإحداثيات. في ثلاثة أبعاد مثلًا تصبح |x₁−x₂| + |y₁−y₂| + |z₁−z₂|.
هل يمكن أن تكون مسافة مانهاتن سالبة؟ لا أبدًا. لأننا نستخدم القيمة المطلقة لكل فرق، فالنتيجة دائمًا صفر أو أكبر. تساوي صفرًا فقط حين تتطابق النقطتان.
أيهما أسرع في الحساب، مانهاتن أم الإقليدية؟ مانهاتن أسرع، لأنها تعتمد على الجمع والطرح فقط، بينما تتطلب الإقليدية عمليتي تربيع وجذر تربيعي، وهما أثقل على المعالج عند التكرار الكثيف.
هل صحيح أنها تُستخدم لتقليل التصادمات في جداول التجزئة (Hash Tables)؟ هذا مفهوم شائع لكنه غير دقيق. جداول التجزئة تعتمد على دوال التجزئة (Hash Functions) لتوزيع القيم، لا على قياس المسافة. مسافة مانهاتن مرتبطة بمسائل المسافة والتشابه المكاني، وليست أداة لإدارة التصادمات.