Ocaml:即使已经找到图形，也会重复图形中的路径 [英] Ocaml: path in a graph is repeated even if this has already been found

问题描述

我写了一些函数来搜索从起始节点到终止节点的可能路径列表.函数list_of_paths正确返回从起点到终点的所有可能路径，但是即使已找到列表，也重复列表内的相同路径.

I wrote some function to search the list of possible paths from a starting node to an ending node. The function list_of_paths correctly returns all the possible paths from a starting point to an ending point but the same path inside the list is repeated even if this has already been found.

例如调用该函数:
list_of_paths 2 7 (List.rev (bfs g1 2)) (node_succ g1) 2

For example calling the function:
list_of_paths 2 7 (List.rev (bfs g1 2)) (node_succ g1) 2

返回:
[[2; 3; 6; 7]; [2; 3; 6; 7]; [2; 3; 4; 6; 7]; [2; 3; 6; 7]; [2; 1; 5; 6; 7]; [2; 3; 6; 7]; [2; 1; 5; 6; 7]]

如您所见，重复相同的路径.有人可以告诉我错误在哪里吗?这是我写的代码:

As you can see the same paths is repeated. Can someone tell me where the mistake is? This is the code i wrote:

type weight = int;;
type 'a graph = Gr of (int * weight * int) list;;
let g1 =  Gr [(1,3,2);(1,9,5);(2,2,3);(5,4,6);(3,1,6);(3,7,4);(6,2,7);(4,4,6)];;

let rec node_succ (Gr graph) node =
    let rec f_aux = function
        [] -> []
        | (x,y,z)::tail -> 
            if x = node then z::f_aux tail
            else if z = node then x::f_aux tail
            else f_aux tail in f_aux graph;;

let bfs graph s =
    let rec search visited_nodes = function 
        [] -> visited_nodes 
        | head::tail -> 
        if List.mem head visited_nodes then search visited_nodes tail
        else search (head::visited_nodes) (tail @ (node_succ graph head)) in search [] [s];;


let find_paths_bfs start stop graph =
    let extends paths = 
        List.map (function x -> x::paths) (List.filter (function x -> not (List.mem x paths)) (graph (List.hd paths)))
                in let rec s_aux stop = function
                    [] -> raise Not_found
                    | paths::tail -> 
                        if stop = List.hd paths then List.rev paths
                        else s_aux stop (tail @ (extends paths)) in s_aux stop [[start]];; 

let rec list_of_paths start stop reachable_nodes fun_graph_succ s =
    if reachable_nodes = [] then []
    else ((find_paths_bfs s start fun_graph_succ)@(List.tl(find_paths_bfs start stop fun_graph_succ)))
        ::(list_of_paths (List.hd reachable_nodes) stop (List.tl reachable_nodes) fun_graph_succ s);;

函数node_succ返回节点的所有可能的后继者.

The function node_succ returns all the possible successors of a node.

函数bfs从起始节点返回所有可达节点.

The function bfs return all the reachable nodes from a starting node.

函数find_paths_bfs查找从一个节点开始到另一个节点的单个路径.

The function find_paths_bfs find a single path starting from a node and ending to another.

推荐答案

您的实现有点难以解释(至少对于像我这样的OCaml新手而言).我建议先简化一下.正如我说的那样，我绝对是OCaml的初学者，所以请带一点盐(我敢肯定我的解决方案远非最优甚至惯用)，但我会选择类似的东西:

Your implementation is a bit hard to reason about (at least for an OCaml newbie like me :)). I'd suggest to simplify it first. As I said I'm an absolute beginner with OCaml, so take the following with a grain of salt (I'm quite sure my solution is far from being optimal or even idiomatic), but I'd go with something like:

let g1 = [(1,3,2);(1,9,5);(2,2,3);(5,4,6);(3,1,6);(3,7,4);(6,2,7);(4,4,6)];;

(* almost exact clone of your node_succ with the filtering capability added *)
let neighbors node graph except =
  let rec aux = function
    | [] -> []
    | (l,_,r)::tail ->
      if l == node then r::(aux tail)
      else if r == node then l::(aux tail)
      else aux tail
  in List.filter (fun x -> not (List.mem x except)) (aux graph)
;;

let walk graph start stop =
  let rec aux paths_found = function
    (* Unreachable branch taking into account the way we call aux; added to calm down the compliler *)
    | []::_ -> failwith "starting node is not specified"
    (* When nothing to traverse left just return the paths found *)
    | [] -> paths_found
    | (last_visited::tl as current)::left_to_traverse ->
        (* if the last visited node is equal to the stop one it means we found a target path - adding it (reversed) to the result and continue with the paths to traverse left *)
        if last_visited = stop then aux ((List.rev current)::paths_found) left_to_traverse
        (* otherwise, take the non-visited nodes that are reachable from the last visited one (except the ones from the tail that are visited already)... *)
        else match neighbors last_visited graph tl with
          (* ... and if there are none of them it means we are done with the current path, it's a dead end, just continue with the paths to traverse left *)
          | [] -> aux paths_found left_to_traverse
          (* ... and if there are some, "expand" the paths to traverse:
            1) create new path based on the current one by adding the neighbour
            2) add (1) to the paths to traverse
            3) repeat 1-2 for the next neighbour etc.
            4) continue traversing with the result of 1-3
          *)
          | ns -> 
            let next = List.fold_left (fun l x -> (x::current)::l) left_to_traverse ns in
            aux paths_found next
  in aux [] [[start]]
;;

walk g1 2 7 ;;
- : int list list = [[2; 1; 5; 6; 7]; [2; 3; 6; 7]; [2; 3; 4; 6; 7]]

UPD.与您的类型定义相比，类型定义得到了简化；我的代码很可能无法与您的类型配合使用.

UPD. Type definitions are simplified compared to your ones; my code most probably won't work with your types out of the box.

这篇关于Ocaml:即使已经找到图形，也会重复图形中的路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！