خوارزمية البحث عن الرسم البياني

Question

أنا أبحث عن خوارزمية رسم بياني تحتوي على بعض الخصائص غير العادية.

كل حافة في الرسم البياني هي إما حافة "أعلى" أو حافة "أسفل".

يمكن للمسار الصحيح أن يمر بعدد غير محدد من "أعلى" متبوعًا بعدد غير محدد من "أسفل"، أو العكس.ومع ذلك، لا يمكن تغيير الاتجاه أكثر من مرة.

على سبيل المثال ، قد يكون المسار الصحيح عبارة

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

Answer 1

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

الأسلاف هنا هي كل الحواف التي تم اجتيازها للوصول إلى العقدة الحالية، على طول أقصر طريق.إحدى الطرق الجيدة لتخزين معلومات السلف هي أن تكون على شكل زوج من الأرقام.إذا كان U في الأعلى وD في الأسفل، فمن الممكن أن يكون أسلاف حافة معينة كذلك UUUDDDD, ، والذي سيكون الزوج 3, 4.لن تحتاج إلى رقم ثالث، بسبب الثابت.

نظرًا لأننا استخدمنا خوارزمية ديكسترا، فقد تم بالفعل الاهتمام بالعثور على مسارات أقصر متعددة.

Answer 2

ربما يمكنك تحويل الرسم البياني الخاص بك إلى رسم بياني موجه عادي ثم استخدام الخوارزميات الموجودة.

تتمثل إحدى الطرق في تقسيم الرسم البياني إلى رسمين بيانيين، أحدهما بكل الحواف العلوية والآخر بجميع الحواف السفلية وبحواف موجهة بين جميع العقد في الرسم البياني الأول والعقدة المقابلة في الرسم البياني الثاني.

قم أولًا بحل المشكلة للبدء في الرسم البياني الأول والانتهاء في الرسم البياني الثاني ثم العكس، ثم حدد الحل الأقصر.

Answer 3

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

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

Answer 4

أ* مع تكلفة مصممة خصيصًا (درجة G) ووظيفة إرشادية (درجة H) يمكنها التعامل معها.

بالنسبة للتكلفة، يمكنك تتبع عدد تغييرات الاتجاه في المسار وإضافة تكلفة لا نهائية على التغيير الثاني (على سبيل المثال.قطع البحث عن تلك الفروع).

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

ربما هناك المزيد من المعلومات حول المجال المتاح لإنشاء الكشف عن مجريات الأمور؟(أي.إحداثيات x وy للعقد في الرسم البياني؟)

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

Answer 5

إذا كان لديك وظيفة بحث قياسية في الرسم البياني، على سبيل المثال Graph.shortest(from, to) في المكتبة، يمكنك التكرار والتصغير في C#/pseudocode:

[ (fst.shortest(A, C) + nxt.shortest(C, B)) 
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(min)

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

[ [fst, nxt, C, fst.shortest(A, C), nxt.shortest(C,B)]
    for C in nodes , (fst, nxt) in [(up, down), (down, up)] ].reduce(myMin)

أين myMin ينبغي مقارنة اثنين [fst, nxt, C, AC, BD] الصفوف وترك تلك التي لديها مسافة أقل، أو كليهما والافتراض reduce هي وظيفة ذكية.

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