[−][src]Module rs_graph::search::astar
A* search.
This module implements an A*-search for finding a shortest paths from some node to all other nodes. Each node may be assigned a potential (or "heuristic value") estimating the distance to the target node. The potential $h\colon V \to \mathbb{R}$ must satisfy \[ w(u,v) - h(u) + h(v) \ge 0, (u,v) \in E \] where $w\colon E \to \mathbb{R}$ are the weights (or lengths) of the edges. (The relation must hold for both directions in case the graph is undirected).
If $s \in V$ is the start node and $t$ some destination node, then $h(u) - h(t)$ is a lower bound on the distance from $u$ to $t$ for all nodes $u \in V$. Hence, f the shortest path to some specific destination node $t$ should be found the canonical choice for $h$ is such that $h(t) = 0$ and $h(u)$ is a lower bound on the distance from $u$ to $t$.
Example
use rs_graph::traits::*; use rs_graph::search::astar; use rs_graph::string::{from_ascii, Data}; use rs_graph::LinkedListGraph; let Data { graph: g, weights, nodes, } = from_ascii::<LinkedListGraph>( r" *--1--*--1--*--1--*--1--*--1--*--1--*--1--* | | | | | | | | 1 1 1 1 1 1 1 1 | | | | | | | | *--1--*--2--*--1--*--2--e--1--f--1--t--1--* | | | | | | | | 1 1 1 1 1 2 1 1 | | | | | | | | *--1--*--1--*--2--c--1--d--1--*--2--*--1--* | | | | | | | | 1 1 1 1 1 1 1 1 | | | | | | | | *--1--s--1--a--1--b--2--*--1--*--1--*--1--* | | | | | | | | 1 1 1 1 1 1 1 1 | | | | | | | | *--1--*--1--*--1--*--1--*--1--*--1--*--1--* ", ) .unwrap(); let s = nodes[&'s']; let t = nodes[&'t']; // nodes are numbered row-wise -> get node coordinates let coords = |u| ((g.node_id(u) % 8) as isize, (g.node_id(u) / 8) as isize); let (xs, ys) = coords(s); let (xt, yt) = coords(t); // manhatten distance heuristic let manh_heur = |u| { let (x, y) = coords(u); ((x - xt).abs() + (y - yt).abs()) as usize }; // verify that we do not go in the "wrong" direction for (v, _, _) in astar::start(g.neighbors(), s, |e| weights[e.index()], manh_heur) { let (x, y) = coords(v); assert!(x >= xs && x <= xt && y >= yt && y <= ys); if v == t { break; } } // obtain the shortest path directly let (path, dist) = astar::find_undirected_path(&g, s, t, |e| weights[e.index()], manh_heur).unwrap(); assert_eq!(dist, 7); let mut pathnodes = vec![s]; for e in path { let uv = g.enodes(e); if uv.0 == *pathnodes.last().unwrap() { pathnodes.push(uv.1); } else { pathnodes.push(uv.0); } } assert_eq!(pathnodes, "sabcdeft".chars().map(|c| nodes[&c]).collect::<Vec<_>>());
Structs
AStar | A* search iterator. |
Data | The data stored with an edge during the search. |
SumAccumulator | Accumulates by adding distance and weight. |
Traits
AStarHeuristic | A heuristic providing a node potential. |
Accumulator | A binary operation used to accumulate edge weight and distance. |
Functions
default_data | Return the default data structure to be used in the A*-search. |
find_directed_path | Run an A*-search on a directed graph and return the path. |
find_undirected_path | Run an A*-search on an undirected graph and return the path. |
start | Start and return an A*-iterator using default data structures. |
start_directed | Start an A*-search on a directed graph. |
start_generic | Start and return an A*-iterator with a custom accumulator and custom data structures. |
start_undirected | Start an A*-search on a undirected graph. |
start_with_data | Start and return an A*-iterator with custom data structures. |
Type Definitions
AStarDefault | The A*-iterator with default types. |
DefaultMap | Default map type to be used in an A* search. |
DefaultPriQueue | Default priority queue type to be used in an A* search. |