diff options
| -rwxr-xr-x[-rw-r--r--] | astar.rs | 52 |
1 files changed, 19 insertions, 33 deletions
@@ -1,10 +1,9 @@ -#![allow(unused_attributes)] -#![allow()] /* +# ![allow(unused_attributes)] +# ![allow()] /* SRC=${0##*./} BIN=${SRC%.*} rustc --test -o $BIN.tmp $SRC && ./$BIN.tmp $@ && rm $BIN.tmp -exit $? -#*/ +exit $? # */ // ================================================================ // @@ -32,6 +31,7 @@ pub mod astar { pub struct Link<Node_Id, Cost> { pub neighbor : Node_Id, pub exact_distance : Cost, + pub estimate : Cost, } #[derive(Debug, Clone, Default)] @@ -135,16 +135,14 @@ pub mod astar { return Some(forward); } - pub fn iteration<Node_Id, Cost, Neighbor, Heuristic, Error_Type>( + pub fn iteration<Node_Id, Cost, Neighbor, Error_Type>( state : &mut State<Node_Id, Cost>, mut neighbor : Neighbor, - mut heuristic : Heuristic ) -> Result<Status, Error_Type> where Node_Id : Debug + Clone + Default + PartialEq, Cost : Debug + Clone + Default + PartialOrd + Add<Output = Cost>, - Neighbor : FnMut(Node_Id, usize) -> Result<Option<Link<Node_Id, Cost>>, Error_Type>, - Heuristic : FnMut(Node_Id) -> Result<Cost, Error_Type> + Neighbor : FnMut(Node_Id, usize) -> Result<Option<Link<Node_Id, Cost>>, Error_Type> { if state.open.is_empty() { return Ok(Status::FAIL); @@ -192,7 +190,7 @@ pub mod astar { // let exact_distance = nearest_node.clone().exact_distance + link.clone().exact_distance; - let estimate = heuristic(link.clone().neighbor)?; + let estimate = link.clone().estimate; let neighbor_node = Node { id : link.neighbor, @@ -312,7 +310,8 @@ mod tests { if k == index { return Ok(Some(Link::<i64, i64> { neighbor : dst, - exact_distance : cost + exact_distance : cost, + estimate : (8 - dst).abs(), })); } else { k += 1; @@ -322,16 +321,12 @@ mod tests { return Ok(None); }; - let heuristic = |id : i64| -> Result<i64, ()> { - return Ok((8 - id).abs()); - }; - let mut state = init(0i64, 5i64, i64::MAX); let mut steps = 0; loop { steps += 1; - let status = iteration(&mut state, neighbor, heuristic).unwrap(); + let status = iteration(&mut state, neighbor).unwrap(); if status != Status::PROGRESS { assert_eq!(status, Status::SUCCESS); break; @@ -370,7 +365,8 @@ mod tests { if k == index { return Ok(Some(Link::<i64, i64> { neighbor : dst, - exact_distance : cost + exact_distance : cost, + estimate : (15 - dst).abs(), })); } else { k += 1; @@ -380,16 +376,12 @@ mod tests { return Ok(None); }; - let heuristic = |id : i64| -> Result<i64, ()> { - return Ok((15 - id).abs()); - }; - let mut state = init(0i64, 15i64, i64::MAX); let mut steps = 0; loop { steps += 1; - let status = iteration(&mut state, neighbor, heuristic).unwrap(); + let status = iteration(&mut state, neighbor).unwrap(); if status != Status::PROGRESS { assert_eq!(status, Status::FAIL); break; @@ -427,7 +419,8 @@ mod tests { if k == index { return Ok(Some(Link::<i64, i64> { neighbor : dst, - exact_distance : cost + exact_distance : cost, + estimate : (2 - dst).abs(), })); } else { k += 1; @@ -437,16 +430,12 @@ mod tests { return Ok(None); }; - let heuristic = |id : i64| -> Result<i64, ()> { - return Ok((2 - id).abs()); - }; - let mut state = init(2i64, 2i64, i64::MAX); let mut steps = 0; loop { steps += 1; - let status = iteration(&mut state, neighbor, heuristic).unwrap(); + let status = iteration(&mut state, neighbor).unwrap(); if status != Status::PROGRESS { assert_eq!(status, Status::SUCCESS); break; @@ -483,7 +472,8 @@ mod tests { if k == index { return Ok(Some(Link::<i64, i64> { neighbor : dst, - exact_distance : cost + exact_distance : cost, + estimate : (5 - dst).abs(), })); } else { k += 1; @@ -493,16 +483,12 @@ mod tests { return Ok(None); }; - let heuristic = |id : i64| -> Result<i64, ()> { - return Ok((5 - id).abs()); - }; - let mut state = init(0i64, 5i64, i64::MAX); let mut steps = 0; loop { steps += 1; - let status = iteration(&mut state, neighbor, heuristic).unwrap(); + let status = iteration(&mut state, neighbor).unwrap(); if status != Status::PROGRESS { assert_eq!(status, Status::SUCCESS); break; |