هل هناك خوارزميات أسرع من dijkstra؟

Question

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

يقول ويكيبيديا، أن Dijkstra في O (| E | + | V | * Log (| V |)) (باستخدام كومة Fibonacci).

أنا لا أبحث عن التحسينات التي، على سبيل المثال، نصف وقت التنفيذ، ولكن الخوارزميات بدلا من ذلك في تعقيد وقت مختلف (مثل الذهاب من O (N * Log N) إلى O (N)).

علاوة على ذلك، أود أن أعرف رأيك في النهج التالي:

1. تحديد GCD من جميع أوزان الحافة.
2. تحويل الرسم البياني إلى رسم بياني مع أوزان حافة موحدة.
3. استخدم BFS للعثور على أقصر مسار بين رأسين معينين.

مثال للنقطة 2:
تخيل أن يكون GCD 1. ثم سأحول الحافة
أ ---> ب (حافة الوزن 3)
إلى
A-> a '-> a' '-> B (3 مرات Edge Weight 1)
يكلف هذا التحول وقتا ثابتا وسيتعين القيام به مرة واحدة لكل حافة. لذلك أتوقع أن تكون هذه الخوارزمية في O (| E |) (التحول) + O (| E | + | V |) (BFS) = O (2 * | E | + | V |) = O (| E | + | الخامس |)

شكرا لأخذ الوقت الكافي لقراءة سؤالي وآمل عدم خصر وقتك ^ ^. طاب يومك.

Answer 1

تحليل OH الكبير الذي قمت به من أجل خوارزمية الخاص بك معيبة بعمق. افترض أن جميع الحواف أعداد أساسية. سيكون عدد الحواف في الرسم البياني الجديد مساويا لمجموع جميع الأوزان. هكذا O(|E| + |V|) التابع الجديد الرسم البياني في الواقع O(W x |E| + |V|) في الرسم البياني الأصلي الذي يمكن أن يكون أكبر بكثير من O(|E| + |V| log |V|).

Answer 2

هل هناك خوارزميات أسرع من dijkstra؟

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

على الرغم من العدد الأكبر بشكل عام من التكرارات المطلوبة من خلال طريقة Bellman-Forded على طريقة Dijkstra، في الممارسة العملية، يمكن أن تكون طريقة Bellman-Ford متفوقة بسبب النفقات العامة الأصغر [Golden و B. 1976. "أقصر الخوارزميات المسار: المقارنة، "أبحاث العمليات، المجلد. 44، ص. 1164-1168].

الاقتباس أعلاه هو من ديمتري ب. بيرتسيكاس (مارس 1992). "خوارزمية تصحيح تسمية بسيطة وسريعة لأقصر المسارات" (PDF). الشبكات، المجلد. 23، ص 703-709، 1993. http://www.mit.edu/people/dimitrib/slf.pdf.. وبعد استرجاع 2008-10-01.

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

Answer 3

هناك خوارزمية تحتوي على O (1): أدر الأوزان إلى أطوال السلسلة واستخدم الحلقات الرئيسية للعقد (حلقات رئيسية حقيقية مثل تلك الموجودة في جيبك). قم بتوصيل الحلقات الرئيسية بالسلاسل المناسبة. حدد العقدتين وسحبها بعيدا عن بعضها البعض.

اتبع سلاسل Taut من عقدة إلى أخرى. هذا هو أقصر طريق.

لتنفيذ هذا كبرنامج كمبيوتر، ستحتاج إلى اثنين من الروبوتات الصناعية :)

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

Answer 4

هناك دائما *، ويستظير مثل التسلسل الهرمي A * و * JPS.