العثور على جميع المسارات الممكنة من قمة الرأس في توجيه دوري البياني في إرلانج

Question

أود أن تنفيذ وظيفة التي يجد كل المسارات الممكنة إلى كل ما يمكن القمم من مصدر الرأس V في موجه دوري الرسم البياني G.

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

ليس لدي أي الانتهاء قطعة من التعليمات البرمجية لتوفير هنا لأنني غير متأكد من كيفية:

• تخزين النتائج (جنبا إلى جنب مع A->B>C> يجب علينا أيضا تخزين A->B و A->B>C) ؛
• يمثل الرسم البياني (digraph?قائمة الصفوف?);
• كم recursions استخدام (العمل مع كل المجاورة قمة?).

كيف يمكنني العثور على جميع المسارات الممكنة شكل واحد نظرا المصدر قمة في توجيه دوري البياني في إرلانج?

محدث:استنادا إلى إجابات حتى الآن يجب أن تعيد تعريف الرسم البياني التعريف:فمن غير احلقي الرسم البياني.وأنا أعلم أنه إذا وظيفة العودية يضرب دورة فمن أجل غير مسمى حلقة.لتجنب ذلك, أنا يمكن أن تحقق فقط إذا الحالية قمة في قائمة الناتجة الطريق - إذا كان الجواب نعم ، لقد وقف عبور وعودة المسار.

---

UPD2: شكرا على التفكير التعليقات!نعم, كنت في حاجة للعثور على جميع مسارات البسيطة التي ليس لها حلقات من مصدر واحد قمة الرأس إلى جميع الآخرين.

في الرسم البياني مثل هذا:

مع المصدر قمة الخوارزمية يجب أن تجد المسارات التالية:

• A,B
• A,B,C
• A ، B ، C ، D
• A,D
• A ، D ، C
• A ، D ، C ، B

التعليمة البرمجية التالية لا وظيفة ، لكنها غير صالحة للاستعمال مع الرسوم البيانية التي لديها أكثر من 20 القمم (أعتقد هو شيء خاطئ مع العودية - يأخذ الكثير من الذاكرة الذي لا ينتهي):

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
            dfs(Neighbours,[Source],[],Graph,Source),
ok.


dfs([],Paths,Result,_Graph,Source) ->
    ?DBG("There are no more neighbours left for vertex ~w~n", [Source]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source) ->
    ?DBG("///The neighbour to check is ~w, other neighbours are: ~w~n",[Neighbour,Other_neighbours]),
    ?DBG("***Current result: ~w~n",[Result]),
    New_result = relax_neighbours(Neighbour,Paths,Result,Graph,Source),

        dfs(Other_neighbours,Paths,New_result,Graph,Source).


relax_neighbours(Neighbour,Paths,Result,Graph,Source) ->
     case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("Found an unvisited neighbour ~w, path is: ~w~n",[Neighbour,Paths]),
            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("The neighbours of the unvisited vertex ~w are ~w, path is:
                ~w~n",[Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,[Neighbour|Paths],Result,Graph,Source);
            true ->
                [Paths|Result]

        end.

---

UPD3:

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

في كلتا الحالتين سيكون الطريق الوحيد - على سبيل المثال ، عند العادية DFS تتراجع من (أ ، ب ، ج ، د) يعود إلى ويتحقق إذا كان د (الثانية جارة أ) يتم زيارتها.ومنذ العادية DFS يحافظ دولة عالمية لكل قمة الرأس ، د أن يكون 'زيارة' الدولة.

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

لقد حاولت أن أمثل حل الذيل متكررة واحدة, ولكن لا يزال وقت تشغيل خوارزمية غير مجدية - يستغرق حوالي 4 ثوان لاجتياز صغيرة الرسم البياني 16 القمم مع 3 حواف في قمة الرأس:

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
    Result = ets:new(resulting_paths, [bag]),
Root = Source,
            dfs(Neighbours,[Source],Result,Graph,Source,[],Root).


dfs([],Paths,Result,_Graph,Source,_,_) ->
    ?DBG("There are no more neighbours left for vertex ~w, paths are ~w, result is ~w~n", [Source,Paths,Result]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source,Recursion_list,Root) ->
    ?DBG("~w *Current source is ~w~n",[Recursion_list,Source]),
    ?DBG("~w Checking neighbour _~w_ of _~w_, other neighbours are: ~w~n",[Recursion_list,Neighbour,Source,Other_neighbours]),



?    DBG("~w Ready to check for visited: ~w~n",[Recursion_list,Neighbour]),

 case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("~w Found an unvisited neighbour ~w, path is: ~w~n",[Recursion_list,Neighbour,Paths]),
New_paths = [Neighbour|Paths],
?DBG("~w Added neighbour to paths: ~w~n",[Recursion_list,New_paths]),
ets:insert(Result,{Root,Paths}),

            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("~w The neighbours of the unvisited vertex ~w are ~w, path is: ~w, recursion:~n",[Recursion_list,Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,New_paths,Result,Graph,Neighbour,[[[]]|Recursion_list],Root);
            true -> 
            ?DBG("~w The neighbour ~w is: already visited, paths: ~w, backtracking to other neighbours:~n",[Recursion_list,Neighbour,Paths]),
ets:insert(Result,{Root,Paths})

end,

        dfs(Other_neighbours,Paths,Result,Graph,Source,Recursion_list,Root).

أي أفكار لتشغيل هذا في وقت مقبول?

Answer 1

تحرير: حسنا أنا أفهم الآن, كنت تريد أن تجد جميع مسارات بسيطة من قمة الرأس في الرسم البياني موجهة.حتى البحث المتعمق الأول مع التراجع سيكون مناسبة, كما كنت قد أدركت.الفكرة العامة هي أن تذهب إلى الجيران ، ثم انتقل إلى أحد آخر (لا واحد التي قمت بزيارتها), و استمر حتى تصل إلى طريق مسدود.ثم التراجع إلى آخر vertex كنت في اختيار مختلفة الجار ، إلخ.تحتاج إلى الحصول على ذكي بت صحيح, ولكن لا ينبغي أن يكون من الصعب جدا.E. g.في كل خطوة تحتاج إلى تسمية القمم 'استكشاف' أو 'غير مستكشفة' اعتمادا على ما إذا كنت قد قمت بالفعل بزيارة لهم من قبل.أداء لا ينبغي أن يكون مشكلة ، نفذت بشكل صحيح الخوارزمية يجب أن تأخذ ربما O(n^2) مرة.لذلك أنا لا أعرف ما تقومون به خطأ, ربما كنت في زيارة الكثير من الجيران ؟ E. g.ربما يتم إعادة النظر الجيران التي قمت بزيارتها بالفعل ، تدور في حلقات أو شيء من هذا.

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

تحرير: نعم, آسف, أنت على حق, القياسية DFS البحث لا تعمل كما هو عليه ، تحتاج إلى ضبط قليلا بحيث لا إعادة النظر في القمم وقد زار من قبل.حتى يسمح لك بزيارة أي من القمم باستثناء تلك التي لديك بالفعل المخزنة في المسار الحالي الخاص بك.هذا يعني بالطبع بلدي تشغيل الوقت كان خاطئا تماما ، تعقيد خوارزمية الخاص بك سوف يكون من خلال السقف.إذا كان متوسط التعقيد من الرسم البياني الخاص بك هو د+1, ثم سيكون هناك ما يقرب من د*د*د*...*د = د^ن المسارات الممكنة.حتى لو كل vertex 3 فقط من الجيران, لا يزال هناك عدد غير قليل من مسارات عندما تحصل على أكثر من 20 القمم.ليس هناك طريقة حول ذلك حقا, لأنه إذا كنت تريد الخاص بك البرنامج إلى إخراج جميع المسارات الممكنة ثم في الواقع سيكون لديك إلى إخراج كل د^ن منهم.

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

Answer 2

لا أفهم السؤال. إذا كان لدي رسم بياني G= (V، E)= ({A، B}، {(A، B)، (B، A)}) ، فهناك مسارات لا نهائية من A إلى B {[A، B]، [ أ ، ب ، أ ، ب] ، [أ ، ب ، أ ، ب ، أ ، ب] ، ...}. كيف يمكنني العثور على جميع المسارات الممكنة لأي رأس في الرسم البياني الدوري؟

تحرير:

هل حاولت حتى حساب نمو المسارات المحتملة لبعض الرسوم البيانية أو تخمينها؟ إذا كان لديك رسم بياني متصل بالكامل ، فستحصل على

• 2 - 1
• 3 - 4
• 4 - 15
• 5 - 64
• 6 - 325
• 7 - 1956
• 8 - 13699
• 9 - 109600
• 10 - 986409
• 11 - 9864100
• 12 - 108505111
• 13 - 1302061344
• 14 - 16926797485
• 15 - 236975164804
• 16 - 3554627472075
• 17 - 56874039553216
• 18-966858672404689
• 19 - 17403456103284420
• 20 - 330665665962403999

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

Answer 3

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

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

لقد استخدمت نهجًا مشابهًا في الماضي للعثور على عدد مسارات هاميلتونيان في رسم بياني.