BFS算法，跟踪路径

Question

这里有人熟悉 BFS 和跟踪吗？我是第一次编写算法，它找到了最短路径，但追踪最短路径是我遇到的问题。下面的列表是之前索引(y, x)的列表，当它到达(0, 5)时有两条路径，一条向左，一条向右，我只想包含通往的路径目的地，但我不知道如何让它发挥作用。我跟踪前一个节点，但是一旦我们到达 (0, 5)，前一个节点的设置就开始混乱，因为有两条路径。因此我无法从目的地回溯。

您是如何跟踪以前的情况并使其发挥作用的？我已经阅读了很多文章，但仍然没有找到任何真正向我解释的内容。

非常感谢任何帮助

[
(0, 0), 
(1, 0), 
(2, 0), 
(2, 1), 
(2, 2), 
(2, 3), 
(3, 3), 
(4, 3), 
(5, 3), 
(5, 4), 
(5, 5), 
(4, 5), 
(3, 5), 
(2, 5), 
(1, 5), 
(0, 5), <-- starts to mess up here becuase there are two paths to take, left and right
(0, 6), <-- to the right
(0, 4), <-- to the left
(0, 7), <-- to the right
(0, 3), <-- to the left
(0, 8), <-- to the right
(1, 7), <-- to the left and one down
(0, 2), <-- to the left
(0, 9)  <-- to the right (also happens to be the destination)
]

代码：

use std::collections::VecDeque;

fn bfs(arr: [[i32; 10]; 10], target: i32) -> bool {
    let mut visited = [[false, false, false, false, false, false, false, false, false, false]; 10];
    let mut queue: VecDeque<(i32, i32)> = VecDeque::new();
    queue.push_back((0, 0));

    let mut previous_nodes = Vec::new();
    let mut previous = (-1, -1);
    while !queue.is_empty() {
        let (y, x) = queue.pop_front().unwrap();

        if visited[y as usize][x as usize] == true {
            continue;
        }

        visited[y as usize][x as usize] = true;
        previous_nodes.push(previous);
        previous = (y, x);

        
        print!("{}[2J", 27 as char);
        for y in 0..visited.len() {
            for x in 0..visited.len() {
                if arr[y][x] == target && visited[y][x] == true {
                    print!("X ");
                } else if visited[y][x] == true {
                    print!("0 ");
                } else if arr[y][x] == 3 {
                    print!("# ");
                } else {
                    print!(". ");
                }
            }
            print!("\n");
        }
        print!("\n");
        

        if arr[y as usize][x as usize] == target {
            for entry in previous_nodes {
                println!("{:?}", entry);
            }
            return true;
        }

        if x + 1 < arr.len() as i32 && arr[y as usize][(x + 1) as usize] != 3 {
            queue.push_back((y, x + 1));

        }

        if y + 1 < arr.len() as i32 && arr[(y + 1) as usize][x as usize] != 3 {
            queue.push_back((y + 1, x));

        }

        if x - 1 >= 0 && arr[y as usize][(x - 1) as usize] != 3 {
            queue.push_back((y, x - 1));

        }

        if y - 1 >= 0 && arr[(y - 1) as usize][x as usize] != 3 {
            queue.push_back((y - 1, x));
        }
    }
    false
}

fn main() {
    let data = [
        [0, 3, 0, 0, 0, 0, 0, 0, 0, 1],
        [0, 3, 3, 3, 3, 0, 3, 0, 3, 3],
        [0, 0, 0, 0, 3, 0, 3, 0, 0, 0],
        [3, 3, 3, 0, 3, 0, 3, 3, 3, 0],
        [0, 0, 3, 0, 3, 0, 3, 0, 3, 0],
        [0, 0, 3, 0, 0, 0, 3, 0, 3, 0],
        [0, 3, 3, 3, 3, 3, 3, 0, 3, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 3, 3, 3, 3, 3, 3, 3, 3, 3],
        [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    ];

    let b = bfs(data, 1);

    println!("Found: {}", b);
}

Answer 1

首先，我开始进行一些代码清理，使其更加简洁，并制作了 rust playground to experiment with. There are two main approaches to solving this problem. Either you keep track of the path taken in the queue or the visited nodes. The easiest approach for you would likely be to simply adapt your code to have the visited nodes array point to the previous node in the path from each visited node. playground link

fn bfs(arr: [[i32; 10]; 10], target: i32) -> Option<Vec<(i32, i32)>> {
    let mut visited = [[None; 10]; 10];
    let mut queue: VecDeque<(i32, i32)> = VecDeque::new();
    queue.push_back((0, 0));

    // Put some filler into the first location
    visited[0][0] = Some((0, 0));
    
    while let Some((y, x)) = queue.pop_front() {
    
        // Prind debug info
        println!("\nExpanding ({}, {})", x, y);
        for y in 0..visited.len() {
            for x in 0..visited.len() {
                if arr[y][x] == target && visited[y][x].is_some() {
                    print!("X ");
                } else if visited[y][x].is_some() {
                    print!("0 ");
                } else if arr[y][x] == 3 {
                    print!("# ");
                } else {
                    print!(". ");
                }
            }
            println!();
        }

        // Check if this position is the target
        if arr[y as usize][x as usize] == target {
            let mut path_taken = Vec::new();
            path_taken.push((y, x));
            
            let mut prev_x = x;
            let mut prev_y = y;
            while prev_x != 0 || prev_y != 0 {
                let (py, px) = visited[prev_y as usize][prev_x as usize].unwrap();
                path_taken.push((py, px));
                prev_y = py;
                prev_x = px;
            }
            
        
            return Some(path_taken.into_iter().rev().collect())
        }

        // Iterate over adjacent offsets
        for (dx, dy) in &[(1, 0), (0, 1), (-1, 0), (0, -1)] {
            // Check if offset is within bounds
            if x + dx < 0
                || y + dy < 0
                || (y + dy) as usize >= arr.len()
                || (x + dx) as usize >= arr[(y + dy) as usize].len()
            {
                continue;
            }

            // Check if offset points to valid location
            if arr[(y + dy) as usize][(x + dx) as usize] == 3 {
                continue;
            }
            
            if visited[(y + dy) as usize][(x + dx) as usize].is_some() {
                continue;
            } 

            visited[(y + dy) as usize][(x + dx) as usize] = Some((y, x));
            queue.push_back((y + dy, x + dx));
        }
    }
    None
}

不过，我个人更喜欢跟踪队列中路径的方法，以减少小路径的内存需求。虽然这与您原来的问题不一样，但我最喜欢的版本是以一种更好地表示它如何使用类型参数进行数学描述的方式来编写 BFS。 playground link

fn bfs<N, F, R>(start: N, end: N, expand: F) -> Option<SearchPath<N>>
    where N: Copy + Eq + Hash,
          F: Fn(N) -> R,
          R: IntoIterator<Item=N> {
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    
    queue.push_back(SearchPath(start, None));
    visited.insert(start);
    
    while let Some(SearchPath(node, path)) = queue.pop_front() {
        if node == end {
            return Some(SearchPath(node, path))
        }
        
        let path = Rc::new(SearchPath(node, path.clone()));
        
        for edge in expand(node) {
            if !visited.contains(&edge) {
                visited.insert(edge);
                queue.push_back(SearchPath(edge, Some(path.clone())));
            }
        }
    }
    
    None
}

#[derive(Clone, PartialEq, Eq)]
pub struct SearchPath<N> (N, Option<Rc<SearchPath<N>>>);

impl<N: Debug> Debug for SearchPath<N> {
    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
        match &self.1 {
            Some(v) => write!(f, "{:?} -> {:?}", v, &self.0),
            None => write!(f, "{:?}", &self.0)
        }
    }
}

更进一步，如果我们添加更多的类型参数，我们可以做更多的事情。现在可能有点难读，但这让我们可以做的是使用 search 作为基础，从图论中实现一堆不同的搜索方法。从本质上讲，这个新功能 search 归结了许多搜索方法的核心组件。

/// A general purpose graph search.
///  - start: Initial value to use in search queue
///  - expand: A function that takes a path, expands the edges of the top node,
///       then places the next elements in the queue according to the current search
///       approach. Additional ordering constraints may also be applied.
///  - next_node: A helper function which takes a path and evaluates if the search goal
///       has been reached. If the goal has been reached, None is returned and the current
///       path is returned. Otherwise, the top node in the given path is returned so
///       that it can be expanded.
fn search<N, P, F, R>(start: P, expand: F, next_node: R) -> Option<P>
where
    N: Eq + Hash,
    F: Fn(&P, &mut VecDeque<P>),
    R: Fn(&P) -> Option<N>,
{
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();

    queue.push_back(start);
    while let Some(path) = queue.pop_front() {
        let node = match next_node(&path) {
            Some(v) => v,
            None => return Some(path),
        };

        if visited.contains(&node) {
            continue;
        }
        visited.insert(node);

        expand(&path, &mut queue);
    }
    None
}

#[derive(Clone, PartialEq, Eq)]
pub struct WeightedSearchPath<N>(i32, N, Option<Rc<SearchPath<N>>>);

/// An example using search to find the most efficient path with weighted graph edges 
fn weighted_search<N, F, R>(start: N, end: N, expand: F) -> Option<WeightedSearchPath<N>>
where
    N: Copy + Eq + Hash,
    F: Fn(N) -> R,
    R: IntoIterator<Item=(i32, N)>,
{
    search(
        WeightedSearchPath(0, start, None),
        |WeightedSearchPath(cost, node, path), queue| {
            let path = Rc::new(SearchPath(*node, path.clone()));
            for (weight, edge) in expand(*node) {
                queue.push_back(WeightedSearchPath(cost + weight, edge, Some(path.clone())));
            }
            
            queue.make_contiguous().sort_by_key(|x| x.0);
        },
        |WeightedSearchPath(_, node, _)| {
            if *node == end {
                return None;
            }
            Some(*node)
        },
    )
}

BFS算法，跟踪路径

BFS algorithm, tracking the path

algorithm

breadth-first-search

rust