如何用Vec支持HashMap

Question

我試過實現一個通用的A *樹搜索算法。最重要的部分是標有TODO功能hucs：

use std::collections::BinaryHeap; 
use std::collections::HashMap; 
use std::cmp::Ordering; 

pub trait SearchTree<A> { 
    fn available_actions(&self) -> Vec<A>; 
    fn apply_action(&self, act: &A) -> Self; 
} 

pub trait CostSearchTree<A>: SearchTree<A> + Eq { 
    fn action_cost(&self, act: &A) -> f64; 
} 

/// Node in the expanded search tree for uniform cost search with heuristic 
struct HucsNode<A, T> 
where 
    T: CostSearchTree<A>, 
{ 
    cost: f64, 
    heuristic_cost: f64, 
    parent_index: usize, 
    action: Option<A>, 
    tree: T, 
} 

impl<A, T> PartialEq for HucsNode<A, T> 
where 
    T: CostSearchTree<A>, 
{ 
    fn eq(&self, other: &HucsNode<A, T>) -> bool { 
     // Can be used for closed list checking if we just compare the trees 
     return self.tree == other.tree; 
    } 
} 

impl<A, T> Eq for HucsNode<A, T> 
where 
    T: CostSearchTree<A>, 
{ 
} 

impl<A, T> PartialOrd for HucsNode<A, T> 
where 
    T: CostSearchTree<A>, 
{ 
    fn partial_cmp(&self, other: &HucsNode<A, T>) -> Option<Ordering> { 
     Some(self.cmp(other)) 
    } 
} 

impl<A, T> Ord for HucsNode<A, T> 
where 
    T: CostSearchTree<A>, 
{ 
    fn cmp(&self, other: &HucsNode<A, T>) -> Ordering { 
     let self_cost = self.cost + self.heuristic_cost; 
     let other_cost = other.cost + other.heuristic_cost; 

     // Flip for min-heap 
     match other_cost.partial_cmp(&self_cost) { 
      Some(order) => order, 
      _ => Ordering::Equal, 
     } 
    } 
} 

/// Perform a uniform cost search with a monotonous heuristic function on a search tree. 
/// Returns a sequence of actions if a state is found that satisfies the predicate or None if the search terminates before. 
pub fn hucs<A, T: CostSearchTree<A> + Hash>(
    tree: T, 
    predicate: &Fn(&T) -> bool, 
    heuristic: &Fn(&T) -> f64, 
) -> Option<Vec<A>> { 

    let mut node_heap = BinaryHeap::new() as BinaryHeap<HucsNode<A, T>>; 

    // Push the initial node onto the tree 
    node_heap.push(HucsNode { 
     action: None, 
     parent_index: usize::max_value(), 
     cost: 0.0, 
     heuristic_cost: heuristic(&tree), 
     tree: tree, 
    }); 

    let mut old_nodes = Vec::new(); 
    let mut last_node_index = 0 as usize; 

    'outer: while let Some(current_node) = node_heap.pop() { 
     // Break borrows with scope so current_node can be moved out 
     { 
      if predicate(&current_node.tree) { 
       return Some(form_action_sequence(current_node, old_nodes)); 
      } 

      // Check if visited nodes already contains this tree with less cost 
      // TODO: Time complexity is hardly ideal 
      for old_node in old_nodes.iter() { 
       if old_node.tree == current_node.tree && old_node.cost <= current_node.cost { 
        continue 'outer; 
       } 
      } 

      let ref current_tree = current_node.tree; 

      for action in current_tree.available_actions() { 

       let action_cost = current_tree.action_cost(&action); 
       let new_tree = current_tree.apply_action(&action); 
       let new_cost = current_node.cost + action_cost; 

       let new_node = HucsNode { 
        action: Some(action), 
        cost: new_cost, 
        parent_index: last_node_index, 
        heuristic_cost: heuristic(&new_tree), 
        tree: new_tree, 
       }; 

       node_heap.push(new_node); 
      } 
     } 

     old_nodes.push(current_node); 
     last_node_index += 1; 
    } 

    return None; 
} 

/// Restore the sequence of actions that was used to get to this node by climbing the tree of expanded nodes 
fn form_action_sequence<A, T: CostSearchTree<A>>(
    leaf: HucsNode<A, T>, 
    mut older_nodes: Vec<HucsNode<A, T>>, 
) -> Vec<A> { 

    let mut action_vector = Vec::new(); 

    let mut current = leaf; 

    while let Some(action) = current.action { 
     action_vector.insert(0, action); 

     // Safe to swap as nodes' parents are always before them 
     current = older_nodes.swap_remove(current.parent_index); 
    } 

    return action_vector; 
} 

的問題是，查找當前節點是否是通過掃描在舊節點的舊節點花費的時間太長了。因此我想添加一個HashMap。因爲我也需要能夠通過索引訪問舊節點以形成最終的解決方案動作序列，所以我還需要保留Vec。爲了解決這個問題我想補充說，我可以插入HashMap作爲重點，只是查找的內容在VEC像這樣的包裝：我無法弄清楚如何在hucs方法實現這個

use std::hash::Hash; 
use std::hash::Hasher; 

struct BackedHashWrapper<'a, T: 'a + Hash + Eq> { 
    source: &'a Vec<T>, 
    index: usize, 
} 

impl<A, T> Hash for HucsNode<A, T> 
where 
    T: CostSearchTree<A> + Hash, 
{ 
    fn hash<H>(&self, state: &mut H) 
    where 
     H: Hasher, 
    { 
     self.tree.hash(state); 
    } 
} 

impl<'a, T> Hash for BackedHashWrapper<'a, T> 
where 
    T: Eq + Hash, 
{ 
    fn hash<H>(&self, state: &mut H) 
    where 
     H: Hasher, 
    { 
     self.source[self.index].hash(state); 
    } 
} 

impl<'a, T> PartialEq for BackedHashWrapper<'a, T> 
where 
    T: Eq + Hash, 
{ 
    fn eq(&self, other: &BackedHashWrapper<T>) -> bool { 
     self.source[self.index] == other.source[other.index] 
    } 
} 

impl<'a, T> Eq for BackedHashWrapper<'a, T> 
where 
    T: Eq + Hash, 
{ 
} 

，我嘗試以下只是將元素添加到HashMap中

... 
let mut old_nodes = Vec::new(); 
let mut hash_map = HashMap::new(); 
... 

    ... 
    hash_map.insert(BackedHashWrapper {source: &old_nodes, index: last_node_index}, current_node.cost); 
    old_nodes.push(current_node); 
    last_node_index += 1; 
    ... 

但借檢查不會讓我創造這樣一個BackedHashWrapper而源向量是可變的。很顯然，我這樣做完全是錯誤的，所以我怎麼才能做到這一點，而不必克隆樹或任何操作？

Answer 1

我想使用其他類型的後備存儲更容易（例如typed-arena crate中的TypedArena）。

但是在面值問題上，您正在處理的問題是由Rust borrowing rules造成的。那就是你不能在同一個範圍內共享（&）和mutable（&mut）引用或對同一對象的多個可變引用。

hash_map在您的示例中存儲對矢量的共享引用「凍結」它，這使得無法修改矢量，而hash_map位於範圍內。

解決此問題的方法是interior mutability pattern。

在你的情況下，你可以使用RefCell<Vec<T>>來修改矢量，同時保存多個引用。

use std::cell::RefCell; 

type RVec<T> = RefCell<Vec<T>>; 

struct BackedHashWrapper<'a, T: 'a + Hash + Eq> { 
    source: &'a RVec<T>, 
    index: usize, 
} 

... 
impl<'a, T> Hash for BackedHashWrapper<'a, T> 
where 
    T: Eq + Hash, 
{ 
    fn hash<H>(&self, state: &mut H) 
    where 
     H: Hasher, 
    { 
     self.source.borrow()[self.index].hash(state); 
    } 
} 
... 
// Similar changes for Eq and PartialEq 
... 
let mut old_nodes: RVec<_> = RefCell::default(); 
let mut hash_map = HashMap::new(); 
... 

    ... 
    hash_map.insert(BackedHashWrapper {source: &old_nodes, index: last_node_index}, current_node.cost); 
    old_nodes.borrow_mut().push(current_node); 
    last_node_index += 1; 
    ... 

或許這樣的borrow() S和borrow_mut()旨意在其他地方是必需的。