trjhtr

I have implemented a Greedy Best First Search algorithm in Rust, since I couldn't find an already implemented one in the existing crates. I have a small pet project I do in Rust, and the Greedy BFS is at the core of it.

The algorithm is designed to be as flexible as possible. Theoretically, this algorithm could be used as a greedy depth-first search or as a greedy a*. I want to design a good algorithm that I could later use in any other project needing it, not only this one.

I am quite new to Rust and this is the second project I do in this language. Also, I am new to writing optimized algorithms. Since this search will be called often, my main concern is performance. What are some tips and tricks to make the algorithm perform better?

Of course any other critique and comment is welcome. Bellow is the code:

//! Here is the algorithm for the Greedy Best First Search (Greedy BFS).
//! A greedy best first search is an informed search(such as a*) that does not backtrack.
//!
//! While regular BFSs keep a priority queue in order to expand the best node (thus eventually going back in the graph if it proves to be a better node),
//! the greedy version does not keep any other potential nodes. It always only expands the current node and chooses the best one, which becomes the next current_node.
//! All the other nodes are discarded. Thus, the greedy version cannot backtrack.
//!
//! Obviously, the Greedy BFS is not Complete nor Optimal. The advantage of Greedy BFS is that it is fast and doesn't use much memory.
//! The maximum memory it uses is the maximum number of neighbours a node can have.
//! Most of the time, the Greedy BFS is used only to rapidly give an approximation of the desired answer.
//! Still, the approximation can only be as good as the given information (heuristic - h, or cost - g, or f = h + g,
//! or whatever information is best for the current problem). Thus it is very important to choose relevant information for the model !!
//!
//! There are 4 ways a Greedy BFS can stop:
//!
//! 1) Finding the goal. Obviously, when the goal state is found, there is no need to continue the search.
//! But Greedy BFS is not Complete, thus there is no guarantee that the goal will be found. Depending on the quality of the information given
//! this might happen more or less often, but sometimes it might not happen at all! For this reason this is one of the least used stopping
//! condition for the Greedy BFS.
//!
//! 2) When the approximation is good enough. Since the Greedy BFS is used to find a fast approximation, this stopping condition makes much more
//! sense than 1). The algorithm is given a way to test how good the found state is (e.g. an error function) and a minimal/maximal acceptable value.
//! At every step, when the algorithm chooses the best option from the given neighbours it will also test the new state. If it meets the given
//! criteria, then the algorithm stops and returns the solution.
//!
//! 3) When there are no more neighbours. Depending on the search space, since the Greedy BFS cannot backtrack, the algorithm might reach a node
//! which does not have any acceptable neighbours (e.g. the graph is a tree and the algorithm found a leaf). Obviously then the algorithm stops,
//! as there is nothing more it can do. This is the default stopping condition for the algorithm. Unless a different condition is met or if the
//! user decided not to opt in on the other stopping conditions, the algorithm will run until it finds a node which does not have any acceptable
//! neighbours. The user must be very cautious of not opting in on other stopping conditions though: if the graph has any cycles the algorithm
//! might be stuck in an infinite loop!
//!
//! 4) If the algorithm has reached a certain depth. The user might decide to put a limit on the number of nodes the algorithm can visit.
//! If given this number (e.g. k), the algorithm will visit up to k nodes. When it reaches the kth node it directly returns the result.


///The Greedy BFS is designed to perform a search on a graph-like structure.
/// This Graph-like structure is represented by a series of nodes that can give away their neighbours.
pub trait GraphNode

 ///returns an iterator over graph nodes, that are the neighbour of the current node
 fn neighbours(&self) -> Box<Iterator<Item=Self>>;


///The Greedy BFS requires that the model of the search problem it is intended to solve has a specific structure.
///
/// First and foremost: the information about the problem.
/// In this implementation the information about a node must be reduced to a value function that returns a f64.
/// A **bigger** value means **better**, thus the search algorithm will always choose the node that returns the biggest value.
/// The function should give the value based only on a node and the current path.
///
/// Then we need to represent the opt-in stop conditions that are problem dependent: if a path is the goal,
/// or if a path is close enough to the goal to stop. (for some problems only the last node might be relevant, but the entire path
/// is given, in order to loose the problem modeling conditions).
/// These functions should do all the logic behind finding if the stop condition is met or not and should return only a boolean value.
///
/// While the limited depth stop condition is not tied to the model of the problem, it is better to have all the
/// opt-in stop conditions in one place, thus the trait also has a function that returns the max depth. A max depth of 0 means no limit.
///
/// Lastly, there are some problems that might want to update some state as the search goes on and more nodes are added to the path.
/// The state of the problem might be critical in deciding the right value for the value function or if a stopping condition is met.
/// For this the trait has a default function called update that the algorithm calls before adding a new node to the path.
pub trait SearchProblem<Node:GraphNode>

 /// The function that gives the value of a node given the current path.
 /// It represents the information about the problem, given to the searching algorithm.
 fn value(&self, node:&Node, current_path: &Vec<Node>) -> f64;

 /// The function that decides if the search algorithm has found the goal.
 /// As an opt-in stop condition it has a default behaviour - returns false
 fn found_goal(&self, current_path: &Vec<Node>) -> boolfalse

 /// The function that decides if the algorithm has found a path that is good enough.
 /// As an opt-in stop condition it has a default behaviour - returns false
 fn is_good_enough(&self, current_path: &Vec<Node>) -> boolfalse

 /// The function that returns the maximum depth (length) the algorithm should go for
 /// The default value is 0, meaning that there is no max depth
 fn max_depth(&self) -> usize0

 /// The function that updates some state of the SearchProblem every time a new node is added.
 /// While this might not be needed for many problems, there might still be some that need to adapt
 /// the searching algorithm dynamically.
 /// This is an opt-in function. The method does not do anything, by default.
 fn update(&mut self, new_node:&Node)


/// Finds a path in a graph-like structure, starting from a "root" node using the Greedy Best First Search algorithm.
pub fn greedy_bfs<Node, Problem>(root: Node, problem:&mut Problem) -> Vec<Node>
where Node:GraphNode,
 Problem: SearchProblem<Node>,

 let mut path = Vec::new();
 path.push(root);

 let max_depth = problem.max_depth();
 let mut depth:i32 = 0;

 if max_depth == 0 depth = -1

 while !problem.found_goal(&path) && !problem.is_good_enough(&path) && depth < max_depth as i32

 let mut neighbours = path.last().unwrap().neighbours();
 let first_neighbour = neighbours.next();
 let mut best_node:Node;
 match first_neighbour 
 Some(n) => best_node = n,
 None => break
 
 let mut best_node_value = problem.value(&best_node, &path);

 for node in neighbours
 let new_value = problem.value(&node, &path);
 if new_value > best_node_value 
 best_node = node;
 best_node_value = new_value;
 
 
 problem.update(&best_node);
 path.push(best_node);

 if max_depth > 0 depth += 1
 
 return path;

I will post comments not about your performances, but about your writing style, because some things can be shortened.

Simplify vector creation:

let mut path = Vec::new();
path.push(root);

can be written as:

let mut path = vec![root];

Put your conditional expression all-in-one:

let mut depth:i32 = 0;

if max_depth == 0 depth = -1

can be:

let mut depth = if max_depth == 0 -1 else 0 ;

You better express your attempt with this. Also, you do not need to put the type of depth, this is i32 by default. If you want to run at least one time the while block, this is better (in my sense) to write this:

let max_depth = problem.max_depth().max(1); // depth is at least one
let mut depth = 0;

Do not rewrite common algorithms:

All this:

 let mut neighbours = path.last().unwrap().neighbours();
 let first_neighbour = neighbours.next();
 let mut best_node:Node;
 match first_neighbour 
 Some(n) => best_node = n,
 None => break
 ;
 let mut best_node_value = problem.value(&best_node, &path);

 for node in neighbours
 let new_value = problem.value(&node, &path);
 if new_value > best_node_value 
 best_node = node;
 best_node_value = new_value;
 
 

is a max_by_key:

extern crate ordered_float;

// ...

let best_node = match neighbours.max_by_key(|node| OrderedFloat(problem.value(&node, &path))) 
 Some(node) => node,
 None => break,

This cannot work as-in, because path cannot be borrowed twice, but if you rewrite your data structure differently, this could be ok.

Do not use &Vec<T>

Use &[T] instead.

Be careful about code formatting

This could seem meaningless, but people can be embarrassed by missing spaces, or other badly formatted things. Do not be afraid to use the official code formatter.