خوارزمية التقاطع

خوارزمية التقاطع هي خوارزمية توافق تُستخدم لاختيار مصادر تقدير الوقت بدقة من بين عدد من مصادر الوقت المشوشة . وهي جزء من بروتوكول وقت الشبكة الحديث . وهي شكل مُعدّل من خوارزمية مارزولو . ^{[ 1 ] [ 2 ]}

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

بفرض وجود M فترات زمنية على شكل c  ± r (أي [ c − r , c + r ])، تسعى الخوارزمية إلى إيجاد فترة زمنية تحتوي على M − f مصدرًا. يُشار إلى القيمة f بعدد المصادر الخاطئة، أي تلك المصادر التي تحتوي على خطأ (القيمة الفعلية خارج نطاق الثقة ). أفضل تقدير هو الذي يفترض أقل عدد من المصادر الخاطئة، f . تُعتبر النتائج صحيحة إذا كانت f < M /2، وإلا ستُرجع الخوارزمية فشلًا بدلًا من فترة زمنية.   

تبدأ خوارزمية التقاطع بإنشاء جدول من الأزواج <الإزاحة، النوع>. لكل فاصل زمني، توجد ثلاثة عناصر: نقطة النهاية الدنيا، ونقطة المنتصف، ونقطة النهاية العليا، مُصنّفة بالأنواع -1 ، 0، و+1 على التوالي. بالتالي، ينتج عن الفاصل الزمني c  ± r العناصر < c − r , −1 >، < c , 0>، و< c + r , +1>. ثم تُرتّب هذه العناصر حسب الإزاحة. 

المتغيرات: تستخدم هذه الخوارزمية f كعدد المؤشرات الخاطئة، و endcount و midcount أعداد صحيحة. Lower و upper قيم الإزاحات.

0. [تهيئة أفضل قيمة لـ f] ابدأ بـ f = 0، بافتراض أن جميع فترات الإدخال صالحة. في كل مرة لا يتم فيها العثور على فترة، ستتم زيادة قيمة f حتى يتم العثور على فترة أو تصبح f  ≥ M / 2. 
1. [تهيئة] عدد النهاية = 0 وعدد المنتصف = 0.
2. [إيجاد نقطة النهاية الدنيا] ابدأ من بداية القائمة (أدنى إزاحة)، وانظر إلى كل صف بالترتيب. عدد الصفوف  = عدد الصفوف - النوع . إذا كان عدد الصفوف ≥ M - f، فإن الحد الأدنى = الإزاحة ، وانتقل إلى الخطوة 3 لأنه تم العثور على نقطة النهاية الدنيا (المحتملة). إذا كان النوع = 0، فإن عدد الصفوف = عدد الصفوف + 1. كرر ذلك مع الصف التالي. إذا وصلت إلى نهاية القائمة، فانتقل إلى الخطوة 6.         
3. [تم العثور على نقطة نهاية دنيا مؤقتة، قم بالتهيئة للعثور على نقطة النهاية العليا] اضبط عدد النهايات = 0.
4. [تحديد عدد نقاط المنتصف] ابدأ من نهاية القائمة واتجه نحو الإزاحات الأدنى. عدد نقاط المنتصف  = عدد نقاط المنتصف + النوع . إذا كان عدد نقاط المنتصف ≥ M − f، فإن الإزاحة العليا = الإزاحة ، انتقل إلى الخطوة 5. إذا كان النوع = 0، فإن عدد نقاط المنتصف = عدد نقاط المنتصف + 1. كرر ذلك للصف التالي. إذا وصلت إلى نهاية القائمة، فانتقل إلى الخطوة 6.         
5. إذا كان الحد الأدنى  ≤ الحد الأعلى والعدد المتوسط ​​≤ f، فقم بإرجاع الفترة [ نقطة النهاية الدنيا ، نقطة النهاية العليا ] كفترة ثقة ناتجة.   
6. [زيادة عدد المؤشرات الخاطئة] f  = f +1. إذا كانت f ≥ M /2، فقم بالإنهاء وأرجع FAILED، وإلا فانتقل إلى الخطوة 1.