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も保持する必要があります。私は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, 
{ 
} 

、これを解決するために、私はちょうどこのようVecとでその内容を検索し、キーとして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

他のタイプのバッキングストレージ（TypedArena、たとえばtyped-arena crate）を使用する方が簡単だと思います。

しかし、額面で質問をすると、あなたが扱っている問題はRust borrowing rulesによって引き起こされます。つまり、（&）と同じスコープ内の同じオブジェクトへの可変参照（&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()秒のカップルが他の場所で必要とされます。