لماذا إصدار الخوارزمية الخاص بي بطيء جدًا مع هذا الإدخال؟

Question

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

#################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################

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

لقد حاولت مع العودية مقابل قائمة الانتظار, ، مع شجرة مقابل الشبكة/الخريطة (راجع تاريخ جيثب الخاص بي) ولكن دون حظ حتى الآن.

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

هذه هي الطريقة التي أقوم بها بإنتاج الخطوة الواحدة، والتي من خلالها أقوم بتوضيح الحل.

1 single step receives as input which is the move index i
2 then it updates the distance of the current solution draft by summing the distance to the vertex i
3 it updates the current position as of vertex i
4 it also updates the list of predecessors by including vertex i
5 it computes the new tree of reachable vertices starting from the `fullGrid` and taking into account the newly updated list of predecessors

لاحظ أن هذه نسخة مقيدة من TSP حيث يمكن أن تحتوي كل قمة على قائمة من العناصر السابقة كقيد.

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

Start by receiving the graph topology and starting point
    Define a mindistance variable
    and a list of completed solutions, initially empty

    Start looping at the queue of partial solutions
        So a single partial solution is dequeued
        It computes possible vertices based on current predecessors
        Check if nothing remains and adds it to the completed alternatives updating mindistance
        Otherwise loop as in classical BFS
        For all possible moves = reachable vertices

                For each one applies above said single step
                If done updates mindistance and completed alternatives 
                Otherwise enqueue such partial solution 


    Finally select the min alternative by distance.

Answer 1

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

الهدف هو تجنب إضافة عنصر آخر إلى قائمة الانتظار عندما يكون موجودة بالفعل أ عنصر أفضل هناك.

فقط بعض التعليمات البرمجية، فقط لتوضيح المفهوم.

في حالتي لقد اضفت خريطة تمت زيارتها

let mutable visited = Map.empty<char,((char list) * int) list>

وأنا أضع في قائمة الانتظار العناصر الأفضل فقط:

if visited.ContainsKey(solutionNext.tree.area) 
    && (visited.[solutionNext.tree.area] 
        |> List.exists (
            fun (keys, distance) -> 
            distance <= solutionNext.tree.distance
            && solutionNext.keys |> List.forall(fun k -> keys |> List.contains k)
        ))
then () 
else 
    solution_queue <- enqueue solution_queue solutionNext
    let previous = if visited.ContainsKey(solutionNext.tree.area) then visited.[solutionNext.tree.area] else []
    visited <- Map.add solutionNext.tree.area ((solutionNext.keys, solutionNext.tree.distance) :: previous)  visited

وتخطي الأسوأ

while (MyQueue.length solution_queue > 0) do
    let solution = dequeue &solution_queue
    if visited.ContainsKey(solution.tree.area) 
        && (visited.[solution.tree.area] 
            |> List.exists (
                fun (keys, distance) -> 
                distance < solution.tree.distance
                && solution.keys |> List.forall(fun k -> keys |> List.contains k)
            ))
    then () else

دالة التكلفه

من وجهة نظر نظرية، يمكن لـ BFS أن تضمن أن أولا الحل الذي تم إرجاعه سيكون كما قصير بقدر الإمكان، فقط اذا يمكننا أن نفترض أن كل خطوة لها تكلفة قدرها 1.يمكنك اختصار الأمثلة المذكورة أعلاه إلى ذلك، ولكن يظل الخيار الأفضل هو رسم بياني أين ال دالة التكلفه يتم إعادة ضبطه بواسطة حواف طول مختلف.مع وظائف التكلفة الحقيقية يصبح العثور على أقصر طريق أكثر تعقيدًا:هذا هو الحال بالضبط هنا.خاصة لأنه يتعين عليك تحسين أيضًا تعقيد الفضاء (انظر الفقرة السابقة)، وتجنب التعقيد الزمني لأسوأ الحالات $O(ب^د)$, ، مع $ب$ كونه عامل المتفرعة و $د$ عمق الحل الأوللقد وصفت السيناريو حيث $د$ معروفة في البداية (عدد المفاتيح في المتاهة) بينما يتم الحصول على حالة الحافة التي ذكرتها بحجم أكبر $ب$ (عدد معابر المتاهة)