اقتراحات أسهل خوارزميات لبعض عمليات الرسم البياني

Question

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

العمليات التي ستحتاج إلى القيام بها هي على النحو التالي:

• سرد جميع المستخدمين في شبكة الرسم البياني بالنظر إلى المسافة x
• اذكر جميع المستخدمين في شبكة الرسم البياني إعطاء مسافة x ونوع العلاقة
• احسب أقصر مسار بين مستخدمين على شبكة الرسم البياني بالنظر إلى نوع من العلاقة
• احسب الحد الأقصى للمسافة بين مستخدمين على شبكة الرسم البياني
• احسب المستخدمين الأكثر تمولة على شبكة الرسم البياني

بعض الملاحظات حول تطبيق الرسم البياني الخاص بي:

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

ما أعرفه حول ما أحتاج إلى فعله:

• لا أعرف ما إذا كان هذا هو الأسهل كما قلت أعلاه ، ولكن بالنسبة لأقصر مسار بين مستخدمين ، أعتقد أن خوارزمية Dijkstra هي ما يبدو أن الناس يوصون به كثيرًا ، لذا أعتقد أنني ذاهب إلى ذلك.
  • لقد كنت أبحث والبحث وأجد صعوبة في تنفيذ هذه الخوارزمية ، هل يعرف أي شخص أي برنامج تعليمي أو شيء سهل الفهم حتى أتمكن من تنفيذ هذه الخوارزمية بنفسي؟ إذا كان ذلك ممكنًا ، مع أمثلة رمز المصدر C ، فإن ذلك سيساعد كثيرًا. أرى العديد من الأمثلة مع تدوينات الرياضيات ولكن هذا يربكني أكثر.
  • هل تعتقد أنه سيساعد إذا "حولت" الرسم البياني إلى مصفوفة مجاورة لتمثيل الروابط وزن ونوع العلاقة؟ هل سيكون من الأسهل أداء الخوارزمية على ذلك بدلاً من القوائم المرتبطة؟ يمكنني بسهولة تنفيذ وظيفة للقيام بهذا التحويل عند الحاجة. أنا أقول هذا لأنني شعرت أنه سيكون أسهل بعد قراءة صفحتين حول هذا الموضوع ، لكنني قد أكون مخطئًا.
• ليس لدي أي أفكار حول العمليات الأربع الأخرى ، والاقتراحات؟

Answer 1

سرد جميع المستخدمين في شبكة الرسم البياني بالنظر إلى المسافة x

مسافة X من ماذا؟ من عقدة البداية أو المسافة X بين أنفسهم؟ يمكنك ان تعطي مثالا؟ قد يكون هذا أو لا يكون بسيطًا مثل إجراء بحث BF أو تشغيل Dijkstra.

على افتراض أنك تبدأ في عقدة معينة وتريد سرد جميع العقد التي لها مسافات X إلى عقدة البداية ، ما عليك سوى تشغيل BFS من عقدة البداية. عندما تكون على وشك إدخال عقدة جديدة في قائمة الانتظار ، تحقق مما إذا كانت المسافة من العقدة البدء إلى العقدة التي تريد إدخال العقدة الجديدة من + وزن الحافة من العقدة التي تريد إدخال العقدة الجديدة من إلى العقدة الجديدة هي <= X. إذا كانت أقل بدقة ، فقم بإدخال العقدة الجديدة وإذا كانت متساوية ، فما عليك سوى طباعة العقدة الجديدة (وأدخلها فقط إذا كان يمكنك أيضًا الحصول على 0 كوزن حافة).

اذكر جميع المستخدمين في شبكة الرسم البياني إعطاء مسافة x ونوع العلاقة

أنظر فوق. مجرد عامل في نوع العلاقة في BFS: إذا كان نوع الوالد مختلفًا عن النموذج الذي تحاول إدراجه في قائمة الانتظار ، فلا تدخله.

احسب أقصر مسار بين مستخدمين على شبكة الرسم البياني بالنظر إلى نوع من العلاقة

تعتمد الخوارزمية على عدد من العوامل:

• كم مرة ستحتاج إلى حساب هذا؟
• كم عدد العقد لديك؟

بما أنك تريد بسهولة ، فإن الأسهل هم روي فلويد وديكسترا.

• باستخدام Roy-Floyd هو مكعب في عدد العقد ، غير فعال. استخدم هذا فقط إذا كنت تستطيع تشغيله مرة واحدة ثم أجب على كل استعلام في O (1). استخدم هذا إذا كنت تستطيع الاحتفاظ بمصفوفة مجاورة في الذاكرة.
• Dijkstra's هي التربيعية في عدد العقد إذا كنت تريد أن تبقيها بسيطة ، ولكن عليك تشغيله في كل مرة تريد حساب المسافة بين العقدتين. إذا كنت ترغب في استخدام Dijkstra's ، فاستخدم قائمة متاخمة.

فيما يلي تطبيقات C: روي فلويد و Dijkstra_1, Dijkstra_2. يمكنك العثور على الكثير على Google مع "<algorithm name> c implementation".

تعديل: Roy-Floyd أمر غير وارد لـ 18 000 عقد ، وكذلك مصفوفة مجاورة. سوف يستغرق الأمر الكثير من الوقت للبناء والطريقة التي الكثير من الذاكرة. أفضل رهان لك هو إما استخدام خوارزمية Dijkstra لكل استعلام ، ولكن يفضل تنفيذ Dijkstra باستخدام كومة - في الروابط التي قدمتها ، استخدم كومة للعثور على الحد الأدنى. إذا قمت بتشغيل Dijkstra الكلاسيكي في كل استعلام ، فقد يستغرق ذلك أيضًا وقتًا طويلاً للغاية.

خيار آخر هو استخدام بيلمان فورد خوارزمية في كل استعلام ، والتي ستمنحك O(Nodes*Edges) وقت التشغيل لكل استعلام. ومع ذلك ، هذا مبالغ كبيرة إذا لم تقم بتنفيذها كما تخبرك ويكيبيديا بذلك. بدلاً من ذلك ، استخدم قائمة انتظار مشابهة لقائمة انتظارها المستخدمة في BFS. عندما تقوم العقدة بتحديث المسافة من المصدر ، أدخل تلك العقدة مرة أخرى في قائمة الانتظار. سيكون هذا سريعًا جدًا في الممارسة العملية ، وسيعمل أيضًا من أجل الأوزان السلبية. أقترح عليك استخدام هذا أو Dijkstra مع كومة ، لأن Dijkstra الكلاسيكية قد يستغرق وقتًا طويلاً على 18000 عقد.

احسب الحد الأقصى للمسافة بين مستخدمين على شبكة الرسم البياني

أبسط طريقة هي استخدام التراجع: جرب جميع الاحتمالات والحفاظ على أطول مسار موجود. هذا هو NP-complete, ، لذلك الحلول متعددة الحدود غير موجودة.

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

احسب المستخدمين الأكثر تمولة على شبكة الرسم البياني

وهذا يعني أنك تريد العثور على قطر الرسم البياني. إن أبسط طريقة للقيام بذلك هي العثور على المسافات بين كل عقدتين (جميع الأزواج أقصر المسارات - إما تشغيل Roy -Floyd أو Dijkstra بين كل عقدتين واختيار الاثنين مع أقصى مسافة).

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

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

لا ، تعد مصفوفة المجاورة وروي فلويد فكرة سيئة للغاية إلا إذا كان التطبيق يستهدف أجهزة الكمبيوتر العملاقة.

Answer 2

هذا يفترض O(E log V) هو وقت تشغيل مقبول ، إذا كنت تفعل شيئًا عبر الإنترنت ، فقد لا يكون هذا ، وسيتطلب ذلك بعض الآلات التي تعمل بالطاقة العالية.

• سرد جميع المستخدمين في شبكة الرسم البياني بالنظر إلى المسافة x

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

• اذكر جميع المستخدمين في شبكة الرسم البياني إعطاء مسافة x ونوع العلاقة

قد يكون هو نفسه تقريبًا كما هو مذكور أعلاه - فقط استخدم بعض الوظائف حيث سيكون الوزن لا نهائي إذا لم يكن من العلاقة الصحيحة.

• احسب أقصر مسار بين مستخدمين على شبكة الرسم البياني بالنظر إلى نوع من العلاقة

كما هو مذكور أعلاه ، بشكل أساسي ، فقط حدد مبكرًا إذا كنت تتطابق مع المستخدمين. (بدلاً من ذلك ، يمكنك "الالتقاء في الوسط" ، وإنهاء مبكرًا إذا وجدت شخصًا ما على أقصر شجرة تمتد)

• احسب الحد الأقصى للمسافة بين مستخدمين على شبكة الرسم البياني

أطول مسار هو مشكلة NP-Complete.

• احسب المستخدمين الأكثر تمولة على شبكة الرسم البياني

هذا هو قطر الرسم البياني ، الذي يمكنك قراءته عالم الرياضيات.

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

Answer 3

أبسط خوارزمية لحساب أقصر مسار بين العقدتين فلويد وارشال. إنه مجرد حلق ثلاثي الحلقات ؛ هذا هو.

يحسب الكل-أقصر مسار في O(N^3), ، لذلك قد يقوم بعمل أكثر من اللازم ، وسوف يستغرق بعض الوقت إذا N ضخم.