समस्या इस प्रकार है: एक उन्मुख भारित ग्राफ़, एक प्रारंभ नोड, एक अंत नोड और एक संख्या k को देखते हुए, सत्यापित करें कि कम से कम लंबाई k के साथ प्रारंभ नोड से अंत नोड तक पथ मौजूद है या नहीं।
यह वह कोड है जिसे मैंने लिखा था और यह सही है लेकिन केवल विशिष्ट ग्राफ में है। उदाहरण के लिए g1 weights1 के साथ इस प्रकार है: यहां छवि विवरण दर्ज करें

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();;

और weight1 और g1 का उपयोग करके मेरे कोड का निष्पादन है: यहां छवि विवरण दर्ज करें

अब, यदि मैं अपना कोड किसी अन्य ग्राफ में निष्पादित करता हूं, उदाहरण के लिए:

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

enter image description here

निम्नलिखित निष्पादन के साथ मेरा कोड विफल रहता है: यहां छवि विवरण दर्ज करें

ऐसा इसलिए है क्योंकि कम से कम k के पथ को खोजने से पहले अंतिम पथ नोड 2 से शुरू होता है, और ऐसा कोई पथ नहीं है जो 2 को 10 से जोड़ सके, लेकिन 1 और 10 के बीच का पथ 10 मौजूद है और इसे चुना नहीं गया है। क्या कोई मुझे समझा सकता है कि मैं यह सुनिश्चित करने के लिए अपना कोड कैसे बदल सकता हूं कि समस्या हर प्रकार के ग्राफ में हल हो गई है?

1
Alessio Mancinelli 15 जिंदा 2020, 10:19

1 उत्तर

सबसे बढ़िया उत्तर

जैसा कि आपने स्वयं कहा है, ब्लॉक

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

विफल हो सकता है क्योंकि वर्तमान पथ के अंतिम तत्व से अंतिम नोड तक पथ के अस्तित्व को कुछ भी सुनिश्चित नहीं करता है।

सबसे आसान उपाय यह है कि इस ब्लॉक को हटा दें और ... बस।

जब एक आंशिक पथ लंबाई सीमा से अधिक होता है तो एल्गोरिदम को स्विच करने की कोई अनिवार्य आवश्यकता नहीं होती है (और यह अनुकूलित करने का प्रयास करने के लिए सही एल्गोरिदम नहीं है)।

1
octachron 15 जिंदा 2020, 13:14