首页 文章

在Erlang中查找有向循环图中一个顶点的所有可能路径

提问于
浏览 次
6

我想实现一个函数，该函数在有向循环图G中找到来自源顶点V的所有可能顶点的所有可能路径 .

性能现在没关系，我只是想了解算法 . 我已经阅读了深度优先搜索算法的定义，但我并不完全理解该怎么做 .

我没有在这里提供任何完整的代码，因为我不知道如何：

  • 存储结果（连同A-> B-> C->我们还应该存储A-> B和A-> B-> C）;

  • 代表图形（有向图？元组列表？）;

  • 要使用多少递归（处理每个相邻的顶点？） .

How can I find all possible paths form one given source vertex in a directed cyclic graph in Erlang?

UPD：基于到目前为止的答案，我必须重新定义图形定义：它是一个非非循环图形 . 我知道如果我的递归函数遇到一个循环，它就是一个无限循环 . 为了避免这种情况，我可以检查当前顶点是否在结果路径的列表中 - 如果是，我停止遍历并返回路径 .

UPD2: 感谢发人深省的评论！是的，我需要找到所有简单路径，这些路径没有从一个源顶点到所有其他源的循环 .

在这样的图表中：

Non-acyclic graph

使用源顶点A算法应找到以下路径：

  • 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:

问题是常规的深度优先搜索算法将首先进入路径之一：（A，B，C，D）或（A，D，C，B）并且永远不会进入第二条路径 .

在任何一种情况下，它都是唯一的路径 - 例如，当常规DFS从（A，B，C，D）回溯时，它返回到A并检查是否访问了D（A的第二个邻居） . 由于常规DFS为每个顶点维护一个全局状态，因此D将具有“已访问”状态 .

所以，我们必须引入一个依赖于递归的状态 - 如果我们从（A，B，C，D）回溯到A，我们应该在结果列表中有（A，B，C，D），我们应该在算法的最开始，将D标记为未访问 .

我试图优化尾递归的解决方案，但算法的运行时间仍然不可行 - 遍历16个顶点的微小图形需要大约4秒，每个顶点有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).

有什么想法在可接受的时间运行吗？

graph erlang depth-first-search directed-graph

3 回答

  • 1

    Edit: 好的，我现在明白了，你想要找到有向图中顶点的所有简单路径 . 因此，正如您已经意识到的那样，使用回溯的深度优先搜索将是合适的 . 一般的想法是去邻居，然后去另一个（不是你太难了 . 例如，在每一步你需要标记顶点'explored'或'unexplored'取决于你是否是一个问题，a正确实现的算法应该花费O（n ^ 2）的时间 . 所以我没有已经访问过，并且循环或循环 .

    我还没有真正阅读过您的程序，但深度优先搜索的Wiki页面有一个简短的伪代码程序，您可以尝试使用您的语言进行复制 . 将图形存储为邻接列表以使其更容易 .

    Edit: 是的，对不起，你说得对，当你获得20个以上的顶点时，标准的DFS搜索还是很多路径 . 真的没办法，因为如果你希望你的程序输出所有可能的路径，那么你确实必须输出所有d ^ n .

    我很想知道您是否需要针对特定任务执行此操作，或者只是想尝试对此进行编程 . 如果是后者，您只需要对小的，稀疏连接的图表感到满意 .

    回复于
  • 2

    我不明白问题 . 如果我有图G =（V，E）=（{A，B}，{（A，B），（B，A）}），则存在从A到B的无限路径{[A，B]，[ A，B，A，B]，[A，B，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个节点的完全连接图中所有节点的所有路径 . 它是你的任务的上限，所以我认为你不想这样做 . 我想你想要别的东西 .

    回复于
  • 2

    无论如何都不是改进的算法解决方案，但是您通常可以通过生成多个工作线程来提高性能，这可能是每个第一级节点一个，然后聚合结果 . 这通常可以相对容易地改善幼稚蛮力算法 .

    你可以在这里看到一个例子：Some Erlang Matrix Functions，在maximise_assignment函数中（从截至今天的第191行开始的评论） . 同样，基础算法存在相当天真和蛮力，但并行化可以很好地加速许多形式的矩阵 .

    我过去使用过类似的方法来查找图中哈密顿路径的数量 .

    回复于

相关问题