مسار الطول الثابت بين عقدين رسم بياني

Question

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

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

Answer 1

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

تجاهل ذلك ، ولكن ؛ مع بعض تمثيل الرسم البياني:

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

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

Answer 2

هل جربت تكرار DFS?

Answer 3

النهج الغبي: (بنية البيانات هي مجموعة من المداخن). هذا يقوم بشكل أساسي بالبحث عن العرض الأول (BFS) إلى العمق N ، باستثناء أنه إذا تم السماح بالحلقات (لم توضح ولكن أفترض أنها) ، فأنت لا تستبعد العقد التي تمت زيارتها من مزيد من البحث.

1. اضغط على عقدة البدء على مكدس مخزّن في الصفيف في الفهرس 0 (الفهرس = العمق)

2. لكل مستوى/فهرس "L" 0-N:

   لكل عقدة على مكدس مخزّن على المستوى "L" ، ابحث عن جميع جيرانها ، ودفعها إلى كومة مخزنة في المستوى "L+1".

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

3. توقف عند إنهاء المستوى "N-1".

4. حلقة على جميع العقد التي أضفتها للتو إلى المكدس في الفهرس "N" والعثور على عقدة الوجهة الخاصة بك. إذا وجدت: النجاح ، إن لم يكن ، لا مثل هذا المسار.

يرجى ملاحظة أنه إذا كان "كل عقدة يمكن توصيل

(ومع ذلك ، فإن الصيغة طويلة جدًا بحيث لا يمكن الكتابة في حقل إدخال النص في Stackoverflow)