Ocaml:使用bfs的最长路径 [英] Ocaml: Longest path using bfs

问题描述

问题如下:给定定向加权图，起始节点，终止节点和数字k，验证是否存在从起始节点到终止节点的长度至少为k的路径.
这是我写的代码，它是正确的，但仅在特定图中显示.例如，带有 weights1 的 g1 如下:

The problem is as follow: Given an oriented weighted graph, a start node, an end node and a number k, verify if exist a path from the start node to the end node with at least length k.
This is the code i wrote and it's correct but only in specific graph. For example g1 with weights1 is as follows:

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

let f1 = function
1 -> [5]
| 2 -> [1;3;4]
| 3 -> [6]
| 4 -> [3]
| 5 -> [2;6]
| 6 -> [7]
| _ -> [];;

type 'a graph = Graph of ('a -> 'a list);;
let g1 = Graph f1;;

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

let f2 = function
1 -> [2;5]
| 2 -> [3]
| 3 -> [4;6]
| 4 -> [6]
| 5 -> [6]
| 6 -> [2;7]
| _ -> [];;

let g2 = Graph f2;; 


exception NotFound;;
exception Errore;;


(* Function that return the weight of an edge given 2 nodes*)
let rec get_k x y = function
    [] -> 0
    |(a,b,c)::rest -> if((a=x && c=y))then b else get_k x y rest;;


(* Function that calculate the total cost of a given path*)
let cost_of_path path weight = 
    let rec sum cost = function
        []->raise Errore
        |x::y::rest -> sum (cost + get_k x y weight) (y::rest)
        |_::[]->cost 
in sum 0 path;;

(*this function print the list of the path*)
let rec printList = function [] -> print_newline()
    | x::rest -> print_int(x); print_string("; "); printList rest;;

(* Simple bfs function, return only 1 path that connect the start node to the final node*)
let bfs start last_node (Graph succ) =
    let extends path = printList path;
        List.map (function x -> x::path) (List.filter (function x -> not (List.mem x path)) (succ (List.hd path)))
        in let rec aux last_node = function
            [] -> raise Not_found 
            | path::rest -> 
                if (last_node = List.hd path) then List.rev path
                else aux last_node (rest @ (extends path))                     
in aux last_node [[start]];; 


let loghest_path start final_node k weight (Graph succ)=
    let extends path = printList path;
        List.map (function x -> x::path)(succ (List.hd path))    
        in let rec aux final_node = function
            [] -> raise NotFound 
            | path::rest -> 
                (*if the cost of this path is >= k and the last node is the final node, return that path.*)
                if ((cost_of_path (List.rev path) weight >= k) && (List.hd path == final_node)) then List.rev path 

                (*HERE IS THE ERROR: if the total weight of the singole path is >= k but the last node is not the final node,
                find a path that connect the last node of this path to the final node using bfs. It can happen that the path exists
                but it return "Not_Found".*)
                else if((cost_of_path (List.rev path) weight) >= k)
                then (List.rev (List.tl path)) @ bfs (List.hd path) (final_node) (Graph succ)

                (* If the weight is not yet k than extend the path and try another one in list 'rest' *)
                else aux final_node (rest @ (extends path))
in aux final_node [[start]];;


(*Function that calls the other function 'loghest_path' and print the result *)
let find_path start final_node k weigths (Graph succ)=
    let result = (loghest_path start final_node k weigths (Graph succ)) in 
    print_string("Final Path:"); printList result ;
    print_string("The weight is:"); print_int (cost_of_path result weigths); print_newline();;

使用weights1和g1执行我的代码是:

And an execution of my code using weights1 and g1 is:

现在，如果我在另一个图形中执行代码，例如:

Now, if i execute my code in another graph, for example:

let weights3 =[(1,1,2);(1,1,3);(1,1,4);(2,1,5);(2,1,6);(3,1,7);(3,1,8);(4,1,9);(4,1,10);(10,1,1)];;
let f3 = function
1 -> [2;3;4]
| 2 -> [5;6]
| 3 -> [7;8]
| 4 -> [9;10]
| 10 -> [1]
| _ -> [];;
let g3 = Graph f3;;

执行以下命令后，我的代码将失败:

With the following execution my code fails:

这是因为在找到至少为k的路径之前的最后一条路径以节点2开头，并且不存在可以将2与10连接的路径，但是存在权重为10的1和10之间的路径，并且不存在被选中.有人可以向我解释如何更改代码以确保每种图形都可以解决问题吗?

This because the last path before finding a path that is at least k starts with node 2, and there isn't a path that can connect 2 with 10, but a path between 1 and 10 of weights 10 exists and it's not been chosen. Can someone explain to me how can i change my code to make sure that the problem is solved in every type of graph?

推荐答案

正如您所说的那样，障碍

As you stated yourself, the block

    else if((cost_of_path (List.rev path) weight) >= k)
    then (List.rev (List.tl path)) @ bfs (List.hd path) (final_node) (Graph succ)

之所以会失败，是因为无法确保存在从当前路径的最后一个元素到最终节点的路径.

can fail because nothing ensures the existence of a path from the the last element of the current path to the final node.

最简单的解决方法是简单地删除该块，然后就可以了.

The easiest fix is to simply delete this block and ... that's it.

当一个局部路径大于长度阈值时，并没有迫切需要切换算法(这不是尝试优化的正确算法).

There are no imperious needs to switch algorithms when one partial path is greater than the length threshold (and this is not the right algorithm to try to optimize).

这篇关于Ocaml:使用bfs的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！