Ocaml：即使已经找到，图中的路径也会重复

Question

我写了一些函数来搜索从起始节点到结束节点的可能路径列表。函数 list_of_paths 正确地 return 列出了从起点到终点的所有可能路径，但即使已经找到了，也会重复列表中的相同路径。

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

returns:
[[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]]

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

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 return是一个节点所有可能的后继者。

函数bfs return从一个起始节点开始所有可达的节点。

函数find_paths_bfs找到一条从一个节点开始到另一个节点结束的路径。

Answer 1

你的实现有点难以理解（至少对于像我这样的 OCaml 新手来说是这样的:)）。我建议先简化它。正如我所说，我是 OCaml 的绝对初学者，所以请对以下内容持保留态度（我很确定我的解决方案远非最佳甚至惯用），但我会选择类似的东西：

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]]

更新。与您的类型定义相比，类型定义得到了简化；我的代码很可能无法立即使用您的类型。

Ocaml：即使已经找到，图中的路径也会重复

Ocaml: path in a graph is repeated even if this has already been found

ocaml

graph

function

list

breadth-first-search