هل هناك أفضل من القوة الغاشمة خوارزمية توليد الرسم البياني الذي يتعلق هي سلسلة تحرير المسافة=1?

Question

أنا مهتم في إنشاء الرسوم البيانية القمم التي هي سلاسل و الحواف التي تمثل علاقة لها تعديل المسافة من 1 تحت سلسلة معينة متري.

واضح النهج هو جعل جميع $\فارك{ن^2-ن}{2}$ مقارنات بين $n$ القمم ، مما يتيح لنا $O(n^2)$ الوقت التعقيد.

باستثناء parallelizing المقارنات ، هل هناك خوارزمية أفضل من حيث الوقت التعقيد ؟

أنا مهتم في سلسلة المقاييس حيث سلاسل مختلفة الطول المسموح بها.

Answer 1

في أسوأ الحالات، سيعمل أي خوارزمية من هذه الخوارزمية $ \ omega (n ^ 2) $ لأن الرسم البياني الخاص بك يمكن أن يكون له $ \ أوميغا (n ^ 2) $ حواف.

بالمناسبة، هل أنت مهتم ببعض سلسلة سلسلة معينة؟

Answer 2

أنه من الممكن استخدام BK-الأشجار لتسريع هذا.إدراج $n$ العناصر في شجرة يأخذ $O(n \log n)$ الوقت.بعد هذا يمكنك الاستعلام الشجرة لجميع سلاسل الذين تحرير المسافة بالضبط واحدة من المدخلات الخاصة بك.أفعل هذا من أجل كل السلاسل يأخذ مرة أخرى $O(n^2)$ التعقيد ولكن مع قليل جدا من العامل الثابت (هذه الصفحة يذكر فقط 5-8% من شجرة يتعين تفتيشها في الاستعلام).

هنا وصف قصير كيف يعمل:

هيكل البيانات

BK-شجرة إما

• فارغة
• عقدة مع قيمة الجذر $r$ ومجموعة من فهرستها الأطفال $c_i$, كل BK-شجرة (تنفيذها باستخدام تجزئة الخريطة ، صفيف حيوية أو ما شابه)

متري (مهم!) المسافة وظيفة $d(x,y)$ يستخدم الإدراج و الاستفسارات.

إدراج السلسلة $s$

• إذا كانت الشجرة الفارغة ، وجعلها عقدة جديدة مع $s$ كما الجذر قيمة و لا الأطفال
• إذا كانت الشجرة هو عقدة مع الجذر $r$ والأطفال $c_i$, اسمحوا $k=d(r,s)$.
  • إذا $k=0$, تخطي الإدراج كما $s$ هو بالفعل في جذور
  • وإلا متكرر إدراج $s$ في $k$-ال الطفل شجرة $c_k$.

الخطوة الأخيرة يجعل التأكد من أن كافة العقد في $c_i$ وقد المسافة $i$ إلى الجذر

الاستعلام عن سلسلة $s$

• إذا كانت الشجرة فارغة ، إرجاع أية نتائج
• إذا كانت الشجرة هو عقدة مع الجذر $r$ والأطفال $c_i$, اسمحوا $k=d(r,s)$.
  • إذا $k=1$, إضافة $r$ نتيجة (ملاحظة:هذه الخطوة هي مختلفة عن المعتاد BK-شجرة الاستفسارات)
  • وبالإضافة إلى ذلك ، بشكل متكرر الاستعلام $s$ من الأطفال $c_{د-1}$, $c_d$ و $c_{د+1}$.عودة جميع النتائج من تلك الاستفسارات

الخطوة الأخيرة هناك سحر BK-الأشجار, كما أنها لا تحتاج إلى التحقق من الأطفال الآخرين بسبب المسافة يجري متري.وهنا جزئية دليل على الآخرين لماذا لا تحتاج إلى فحص:

دعونا نفترض أن هناك بعض سلسلة $x$ التي لديها مسافة واحدة من الاستعلام ، لذلك $د(s, x)=1$, لكنه في الطفل شجرة $c_{k+2}$.ونحن نعلم أن $d(r, x)=ك+2$ من إجراء الإدراج.لكن هذا (مع المساواة في المثلث على مساحات متري) يعطي

$$ k+2=d(r, x)\leq d(r, s)+د(s,x)=k+1 $$

ولكن هذا هو التناقض!مماثلة يمكن القيام به بالنسبة لجميع الأطفال $i>k+1$ و $i.وهذا يعني أن جميع السلاسل في الأطفال الآخرين لن يكون مسافة واحدة قبل البناء ، لذلك نحن لسنا في حاجة حتى تحقق لهم ، مما يوفر وقت المعالجة.

تحرير:تفسير آخر: https://signal-to-noise.xyz/post/bk-tree/