مرجع
آخر الزيارات

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

724 كلمة•0 مشاهدة•🗒️ منذ 14 يوماً
باختصار: مسألة أقرب زوج من النقاط هي من أهم مسائل الهندسة الإحصائية. في هذه المقالة 6 أقسام: «أقل مسافة = لانهاية»، «UCSB Lecture Notes» و«حالة الإستواء» وغيرها.
المحتويات
  1. أقل مسافة = لانهاية
  2. UCSB Lecture Notes
  3. حالة الإستواء
  4. خوازمية البحث الشامل
  5. ديناميكية مشكلة أقرب - زوج
  6. دع ب = ب[س], ق = ب[ص]
مسألة أقرب زوج من النقاط

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

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

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

أقل مسافة = لانهاية

من ص = ص + 1 إلى الطول (ط)

من س = 1 إلى الطول (ط) - 1

UCSB Lecture Notes

وفي هذا السياق، rosettacode.org - Closest pair of points implemented in multiple programming languages

Line sweep algorithm for the closest pair problem

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

الجواب النهائي هو الحد الأدنى بين ، ، و.

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

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

من جانب آخر، حل المسألة بالاستدعاء ذاتي في المجموعات الفرعية اليمنى واليسرى، ينتج هذا الجانب الأيسر والجانب الأيمن و، على التوالي

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

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

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

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

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

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

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

الملاحظات

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

دع ب = ب[س], ق = ب[ص]

  • إذا المسافة(ب, ق) < أقل مسافة:
  • أقل مسافة = المسافة(ب, ق)
  • أقرب زوج = (ب, ق)
  • أرجع أقرب زوج

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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