الرئيسيةعريقبحث

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

☰ جدول المحتويات

الزوج من النقاط الأكثر قربا ممثلا باللون الأحمر

مسألة أقرب زوج من النقاط (Closest pair of points problem)‏ هي من أهم مسائل الهندسة الإحصائية. تهدف فكرتها إلى إيجاد أقرب نقطتين في مجموعة تحتوي س من النقاط في أقرب مسافة ممكنة. مسألة أقرب زوج من النقاط في مسافة إقليدية[1] كانت من بين أولى المشاكل الهندسية التي تم علاجها في أصول الدراسة المنهجية من التعقيدالحسابي للخورزميات الهندسية.

الخوارزمية الأكثر معرفة لإيجاد المسافة بين جميع أزواج النقاط في مساحة من البعد د واختيار الحد الأدنى تتطلب من الوقت (O(n log n في مسافة إقليدية في بعد ثابت د. في نموذج شجرة القرارات الجبرية الخوارزمية (O(n log n هي المثالية.المثالية يتبع من ملاحظتها أن مشكلة تفرد العنصر (مع الحد الأدنى ل(Ω(n log n ) قابلة للاختزال لمسألة أقرب زوج من النقاط سواءٌ الحد الأدنى هو صفر بعد حل مسألة أقرب زوج من النقاط نستطيع الإجابة على سؤال عما إذا كان هنالك نوعان من نقاط متطابقة.

في النموذج الحسابي الذي يفترض أن دالتا الجزء الصحيح و السقف محسوب في وقت ثابت المسألة يمكن حلها في وقت (O(n log log n.[2] إذا سمحنا التوزيع العشوائي لاستخدامها مع دالتا السقف يصبح حل المسألة في وقت (O(n[3][4]

خوازمية البحث الشامل

مسألة أقرب زوج من النقاط يمكن حسابه في (رمز O الكبير(n2 من خلال استخدام بحث شامل. ولإتمام ذلك يجب حساب المسافة بين كل زوج من النقاط المختلفة حيث أن عدد هذه النقاط يساوي ن(ن-1)/2، و إيجاد زوج من النقاط بأقصر مسافة، كالآتي.

أقل مسافة = لانهاية من س = 1 إلى الطول(ط) - 1 من ص = ص + 1 إلى الطول(ط) دع ب = ب[س], ق = ب[ص] إذا المسافة(ب, ق) < أقل مسافة: أقل مسافة = المسافة(ب, ق) أقرب زوج = (ب, ق) أرجع أقرب زوج

حالة الإستواء

المسألة يمكن حلها في (O(n log n من الوقت بإستخدام الاستدعاء ذاتي و خوارزمية فرق تسد،مثل[1]:

  1. ترتيب النقاط بالنسبة إلى إحداثيات س.
  2. تقسيم مجموعة من النقاط إلى مجموعتين فرعيتين متساوية الحجم عن طريق خط عمودي س = س mid.
  3. حل المسألة بالاستدعاء ذاتي في المجموعات الفرعية اليمنى واليسرى، ينتج هذا الجانب الأيسر و الجانب الأيمن dLmin و dRmin،على التوالي
  4. العثور على مسافة الحد الأدنى dLRmin من بين مجموعة من أزواج من النقاط حيث نقطة واحدة تقع على الجهة اليسرى من تقسيم الرأسي و النقطة الثانية تكمن في الجهة اليمنى.
  5. الجواب النهائي هو الحد الأدنى بين dLmin، dRmin، و dLRmin.


Divide-and-conquer: sparse box observation


تبين أن الخطوة  الرابعة يمكن تحقيقه في الزمن الخطي، مرة أخرى فإن نهج الطريقة الساذجة يتطلب حساب المسافات لجميع أزواج اليسار و اليمين، كمثال في وقت تربيعي. وتستند الملاحظة الرئيسية على تبعثر الممتلكات التالية من مجموعة نقطة. نحن نعلم بالفعل أن أقرب زوج من النقاط هو أبعد عن بعضهما البعض من المسافة = min(dLmin, dRmin) لذلك، لدينا لكل نقطة ن إلى يسار الخط الفاصل لمقارنة المسافات إلى النقاط التي تقع في المستطيل الأبعاد (المسافة , 2 ⋅ المسافة ) لى اليمين من الخط الفاصل، كما هو مبين في الشكل. وما هو أكثر من ذلك، هذا المستطيل يمكن أن يحتوي على ستة نقاط كحد أعلى مع أزواج ذوي المسافة dRmin. ولذلك، فإنه يكفي لحساب المسافات في معظم 6ن بين اليسار واليمين في الخطوة  الرابعة.[5] العلاقة تكرار لعدد من الخطوات التي يمكن أن تكتب كالآتي T(n) = 2 T(n/2) + O(n) والتي يمكن أن تحل باستخدام النظرية الرئيسة للحصول على O(n log n).

كما أن أقرب زوج من النقاط يعرف كحافة في تثليث ديلاوني و تتوافق مع اثنين من الخلايا المجاورة في مخطط فورونوي أقرب زوج من النقاط يمكن تحديده في الزمن الخطي نظرا لاننا عندما واحد من هذين الهيكلين. حساب تثليث ديلاوني أو مخطط فورونوي تأخذ من الوقت O(n log n). هذه الأساليب ليست فعالة ل البعد d>2 في حين أن خوارزمية فرق - تسد يمكن تعميمها على اتخاذ O(n log n) من الوقت لأي قيمة ثابتة من d.

ديناميكية مشكلة أقرب - زوج

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

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

إذا كان مستطيل الإحاطة الأصغر لجميع النقاط معروفة مسبقا و الوقت ثابت باستخام دلتا الجزء الصحيح متوافرة، فإن من المتوقع تنفيذ (O(n من هيكل البيانات المقترح الذي يدعم (O(log n من الوقت المتوقع للحذف و الإضافة. عندما تعدل نموذج شجرة القرارات الجبرية، الإضافة و الحذف تستغرق (O(log2 n من الوقت المتوقع.[6] ومن الجدير بالذكر، على الرغم من أن تعقيد ديناميكية الخوارزمية أقرب الزوج المذكور أعلاه هو الأسي في البعد د، وبالتالي مثل خوارزمية يصبح أقل مناسبة لمشاكل الأبعاد العالية.

الملاحظات

  1. M. I. Shamos and D. Hoey. "Closest-point problems." In Proc. 16th Annual جمعية مهندسي الكهرباء والإلكترونيات Symposium on Foundations of Computer Science (FOCS), pp. 151—162, 1975 (DOI 10.1109/SFCS.1975.8) نسخة محفوظة 18 مايو 2015 على موقع واي باك مشين.
  2. S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979
  3. S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995
  4. Richard Lipton (24 September 2011). "Rabin Flips a Coin". مؤرشف من الأصل في 16 فبراير 2019.
  5. Cormen, Leiserson, Rivest, and Stein, 2001.
  6. Mordecai Golin, Rajeev Raman, Christian Schwarz, Michiel Smid, "Randomized Data Structures For The Dynamic Closest-Pair Problem", SIAM J. Comput., vo. 26, no. 4, 1998, preliminary version reported at the 4th Annu. ACM-SIAM Symp. on Discrete Algorithms, pp. 301–310 (1993)

المراجع

موسوعات ذات صلة :