华为OD机试真题 - 找终点

介绍

“找终点”是华为在线编程考试中的一道经典题目，主要考察候选人对深度优先搜索(DFS)或广度优先搜索(BFS)算法的掌握程度。这道题通常给定一个二维矩阵，矩阵中包含不同的值，其中某个值代表起始点，另一个值代表可通行路径，还有一个目标值代表终点。任务是从起始点找到到达终点的路径。

应用使用场景

1. 路径规划：用于机器人在二维网格地图中的路径寻找。
2. 迷宫求解：解决迷宫问题，找到从入口到出口的路径。
3. 计算机游戏开发：例如，寻找从角色当前位置到目标位置的最短路径。

原理解释

该问题可以通过图遍历算法来解决，常用的方法有：

• 深度优先搜索 (DFS)：沿着可能的路径不断深入，直到无法继续，再回溯查找其他路径。
• 广度优先搜索 (BFS)：一层一层地探索每个可能的移动，确保在找到的第一个解时即为最短路径。

算法原理流程图

+-------------------+
|   Initialize      |
|   - Read grid     |
|   - Locate start  |
+---------+---------+
          |
          v
+-------------------+
|   Add start to    |
|   queue or stack  |
+---------+---------+
          |
          v
+-------------------+
| While queue/stack |
| is not empty:     |
| - Get next node   |
| - If end, return  |
| - Else, add       |
|   neighbors       |
+---------+---------+
          |
          v
+-------------------+
| Return no path    |
| found             |
+-------------------+

算法原理解释

深度优先搜索 (DFS)

DFS 使用栈（递归调用隐式使用系统栈）从起始节点开始，不断深入探索未被访问的邻居节点。如果达到终点，则返回路径；否则回溯并探索其他路径。

广度优先搜索 (BFS)

BFS 使用队列，从起始节点开始逐层向外扩展，并在到达终点时立即返回，因为 BFS 确保了首次到达终点即为最短路径。

实际详细应用代码示例实现

from collections import deque

def find_end_bfs(grid, start, end):
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    queue = deque([start])
    visited = set(start)

    while queue:
        x, y = queue.popleft()
        
        if (x, y) == end:
            return True
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] != 1 and (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append((nx, ny))

    return False

# Example usage:
grid = [
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [1, 0, 0, 0]
]
start = (0, 0)
end = (3, 3)

print(find_end_bfs(grid, start, end))  # Output: True

测试代码

def test_find_end_bfs():
    grid = [
        [0, 0, 1, 0],
        [0, 1, 0, 0],
        [0, 0, 0, 1],
        [1, 0, 0, 0]
    ]
    assert find_end_bfs(grid, (0, 0), (3, 3)) == True
    assert find_end_bfs(grid, (0, 0), (0, 2)) == False
    assert find_end_bfs(grid, (0, 0), (1, 2)) == True

test_find_end_bfs()

部署场景

该算法可部署在各种需要路径规划的应用场景中，如自动驾驶导航系统、无人机的飞行路径优化、游戏中的AI角色路径规划等。

材料链接

• 深度优先搜索 (DFS) - Wikipedia
• 广度优先搜索 (BFS) - Wikipedia

总结

“找终点”问题是典型的图遍历问题，可以利用 DFS 和 BFS 算法高效地解决。通过结合这些算法，我们可以在各种复杂环境中进行路径规划。

未来展望

随着图遍历和路径规划算法的不断改进和优化，这些技术将在自动化导航、智能交通系统和智能机器人领域发挥越来越重要的作用。未来，还可以结合机器学习算法，进一步提高路径规划的效率和智能性。