1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
/** Defines a search space. A search space is a graph structure (directed or not). It contains nodes. The initial state is the entry point of the search procedure. */ pub trait SearchSpace<N,B> { /** returns the initial (or root) node */ fn initial(&mut self) -> N; /** returns the bound value of the node (i.e. f-cost) */ fn bound(&mut self, node: &N) -> B; /** returns true if and only if the node is goal */ fn goal(&mut self, node: &N) -> bool; /** returns the g-cost of the node the h-cost can be computed by substracting the f-cost (SearchSpace.bound) by the g-cost */ fn g_cost(&mut self, n: &N) -> B; /** called when the algorithm finds a new-best-known solution */ fn handle_new_best(&mut self, node: N) -> N { node } // RESTARTING INFORMATION /** called when the algorithm starts */ fn start_search(&mut self, _msg: String) {} /** called when the algorithm restarts */ fn restart(&mut self, _msg: String) {} /** called when the algorithm finishes */ fn stop_search(&mut self, _msg: String) {} // GETTING SEARCH INFORMATION /** displays various statistics about the search (nb nodes, etc.) TODO: use export_statistics to get the statistics in the JSON format, and display them */ fn display_statistics(&self) {} /** registers information about the search statistics in a json file */ fn json_statistics(&self, _json:&mut serde_json::Value) {} /** * requests log headers (does nothing if there is no logging decorator within the algorithm) */ fn request_log_header(&self, _res:Vec<String>) {} /** * requests a logging to appear (does nothing if there is no logging decorator within the algorithm) */ fn request_logging(&self, _res:Vec<String>) {} } /** exports a node to a problem solution Sol. */ pub trait ToSolution<N,Sol> { /** constructs a solution from a goal node panics if the node is not a goal */ fn solution(&mut self, node: &mut N) -> Sol; } /** Defines a guidance function */ pub trait GuidedSpace<N,G> { /** * returns the guide value of the node */ fn guide(&mut self, node: &N) -> G; } /** implements a total neighbor expansion (neighbors) */ pub trait TotalNeighborGeneration<N> { /** returns all neighbors of a given node */ fn neighbors(&mut self, node: &mut N) -> Vec<N>; } /** implements a partial neighbor expansion (next_neighbor) */ pub trait PartialNeighborGeneration<N> { /** returns the next neighbor if it exists, or None */ fn next_neighbor(&mut self, node: &mut N) -> Option<N>; } /** Allows to identify a node. Useful to implement g-cost-dominance / bucket-lists or tabu-search */ pub trait Identifiable<N, Id> { /** returns the ID of the node */ fn id(&self, n: &mut N) -> Id; } /** Represents a search space where nodes can pareto-dominate some other. *i.e.* a node dominantes another if all of its features are better */ pub trait ParetoDominanceSpace<N> { /** returns true if a dominates b */ fn dominates(&self, a:&N, b:&N) -> bool; } /** Represents a search space which there exists a bound on the distance between the root node and any node. This kind of property is frequent in combinatorial branch-and-bounds. */ pub trait BoundedDistanceSpace<N> { /** maximum distance between the root node and a state */ fn maximum_root_distance(&self) -> usize; /** returns the distance from the root of a given node */ fn distance_from_root(&self, n:&N) -> usize; /** returns the distance from root ratio (distance/distance_max) */ fn root_distance_ratio(&self, n:&N) -> f64 { self.distance_from_root(n) as f64 / self.maximum_root_distance() as f64 } }