مسألة إيجاد أقرب زوج من النقاط

مسألة أقرب زوج من النقاط أو مسألة أقرب زوج هي مسألة في الهندسة الحسابية : معطى${\displaystyle n}$لإيجاد زوج من النقاط في الفضاء المتري ، يجب إيجاد أقصر مسافة بينهما. تُعدّ مسألة إيجاد أقرب زوج من النقاط في المستوى الإقليدي ^{[ 1 ]} من أوائل المسائل الهندسية التي تمّ تناولها في بدايات الدراسة المنهجية للتعقيد الحسابي للخوارزميات الهندسية.

توجد خوارزميات عشوائية لحل المشكلة في زمن خطي ، في فضاءات إقليدية يُعامل بُعدها كثابت لأغراض التحليل التقاربي . ^{[ 2 ] [ 3 ] [ 4 ]} وهذا أسرع بكثير من...${\displaystyle O(n^{2})}$الوقت (المعبر عنه هنا برمز Big O ) الذي يمكن الحصول عليه بواسطة خوارزمية ساذجة لإيجاد المسافات بين جميع أزواج النقاط واختيار أصغرها.

من الممكن أيضًا حل المشكلة دون استخدام العشوائية، في نماذج آلات الوصول العشوائي للحوسبة ذات الذاكرة غير المحدودة التي تسمح باستخدام دالة الجزء الصحيح ، في الأنظمة شبه الخطية${\displaystyle O(n\log \log n)}$^{[ 5 ]} في نماذج حسابية أكثر تقييدًا، مثل شجرة القرار الجبرية ، يمكن حل المشكلة في وقت أبطأ نوعًا ما${\displaystyle O(n\log n)}$^{[ 6 ]} يُعدّ هذا الحد الزمني الأمثل لهذا النموذج، وذلك من خلال اختزاله من مشكلة تفرد العنصر . تُدرَّس خوارزميات خط المسح وخوارزميات فرق تسد ذات هذا الحد الزمني الأبطأ عادةً كأمثلة على تقنيات تصميم الخوارزميات هذه. ^{[ 7 ] [ 8 ]}

تعتمد خوارزمية رابين (1976) العشوائية ذات الوقت المتوقع الخطي ، والتي عدّلها ريتشارد ليبتون قليلاً لتسهيل تحليلها، على ما يلي، على مجموعة مدخلات${\displaystyle S}$يتكون من${\displaystyle n}$النقاط في${\displaystyle k}$الفضاء الإقليدي ذو الأبعاد n:

1. يختار${\displaystyle n}$أزواج من النقاط عشوائياً وبشكل منتظم، مع الإعادة، ولتكن${\displaystyle d}$ليكن أقصر مسافة بين الأزواج المختارة.
2. قم بتقريب نقاط الإدخال إلى شبكة مربعة من النقاط يكون حجمها (المسافة بين نقاط الشبكة المتجاورة) هو${\displaystyle d}$واستخدام جدول التجزئة لتجميع أزواج نقاط الإدخال التي تقترب من نفس نقطة الشبكة.
3. لكل نقطة إدخال، احسب المسافة إلى جميع المدخلات الأخرى التي إما أن تقرب إلى نفس نقطة الشبكة أو إلى نقطة شبكة أخرى داخل جوار مور لـ${\displaystyle 3^{k}-1}$نقاط الشبكة المحيطة.
4. أعد أصغر المسافات التي تم حسابها خلال هذه العملية.

ستحدد الخوارزمية دائمًا الزوج الأقرب بشكل صحيح، لأنها ترسم أي زوج أقرب من المسافة.${\displaystyle d}$إلى نفس نقطة الشبكة أو إلى نقاط شبكة متجاورة. إن أخذ عينات منتظمة من الأزواج في الخطوة الأولى من الخوارزمية (مقارنةً بطريقة رابين المختلفة لأخذ عينات من عدد مماثل من الأزواج) يبسط إثبات أن العدد المتوقع للمسافات التي تحسبها الخوارزمية خطي. ^{[ 4 ]}

بدلاً من ذلك، تمر خوارزمية مختلفة (Khuller & Matias (1995)) بمرحلتين: عملية ترشيح عشوائية متكررة تقرب أقرب مسافة إلى نسبة تقريبية قدرها${\displaystyle 2{\sqrt {k}}}$بالإضافة إلى خطوة نهائية تحول هذه المسافة التقريبية إلى أقرب مسافة دقيقة. وتكرر عملية التصفية الخطوات التالية حتى${\displaystyle S}$يصبح فارغًا:

1. اختر نقطة${\displaystyle p}$عشوائياً وبشكل منتظم من${\displaystyle S}$.
2. احسب المسافات من${\displaystyle p}$إلى جميع النقاط الأخرى${\displaystyle S}$ودع${\displaystyle d}$لتكون هذه المسافة هي الحد الأدنى.
3. قم بتقريب نقاط الإدخال إلى شبكة مربعة بحجم${\displaystyle d/(2{\sqrt {k}})}$واحذف من${\displaystyle S}$جميع النقاط التي لا توجد بها نقاط أخرى في حي مور التابع لها.

المسافة التقريبية التي تم التوصل إليها من خلال عملية الترشيح هذه هي القيمة النهائية لـ${\displaystyle d}$، محسوبة في الخطوة السابقة${\displaystyle S}$تصبح فارغة. كل خطوة تزيل جميع النقاط التي يكون أقرب جار لها على مسافة${\displaystyle d}$أو أكبر، على الأقل نصف النقاط المتوقعة، ومن ثمّ يتبين أن إجمالي الوقت المتوقع للترشيح خطي. بمجرد الحصول على قيمة تقريبية لـ${\displaystyle d}$إذا عُرف ذلك، فيمكن استخدامه في الخطوات النهائية لخوارزمية رابين؛ في هذه الخطوات، تحتوي كل نقطة شبكية على عدد ثابت من المدخلات يتم تقريبها إليها، وبالتالي يكون الوقت خطيًا مرة أخرى. ^{[ 3 ]}

يتم صياغة النسخة الديناميكية لمسألة أقرب زوج على النحو التالي:

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

إذا كانت حدود جميع النقاط معروفة مسبقًا، وكانت دالة الجزء الصحيح ذات الزمن الثابت متاحة، فإن القيمة المتوقعة${\displaystyle O(n)}$تم اقتراح بنية بيانات ذات مساحة تدعم الوقت المتوقع${\displaystyle O(\log n)}$عمليات الإضافة والحذف ووقت استعلام ثابت. عند تعديلها لنموذج شجرة القرار الجبرية، ستتطلب عمليات الإضافة والحذف${\displaystyle O(\log ^{2}n)}$الوقت المتوقع. ^{[ 9 ]} إن تعقيد خوارزمية أقرب زوج ديناميكي المذكورة أعلاه يتزايد أُسّيًا في البُعد.${\displaystyle d}$وبالتالي تصبح هذه الخوارزمية أقل ملاءمة للمسائل ذات الأبعاد العالية.

خوارزمية لحل مشكلة أقرب زوج ديناميكي في${\displaystyle d}$طُوِّر الفضاء البُعدي بواسطة سيرجي بيسبامياتنيخ في عام 1998. ^{[ 10 ]} يمكن إدراج النقاط وحذفها في${\displaystyle O(\log n)}$الوقت لكل نقطة (في أسوأ الحالات).

• نظم المعلومات الجغرافية
• البحث عن أقرب جار