DFS BFS UCS

以下是对DFS、BFS和UCS的介绍：

DFS（深度优先搜索）：总是扩展最深层的节点，使用的是LIFO队列，即使用的是stack栈。DFS在生成节点时做的goal test，因此在搜索树中，DFS总是沿着最深的路径搜索，直到找到目标状态或者无法继续搜索为止。DFS的优点是空间复杂度低，但是可能会陷入局部最优解。

BFS（广度优先搜索）：总是扩展最浅层的节点，使用的是FIFO队列，即使用的是queue队列。BFS在扩展节点时做的goal test，因此在搜索树中，BFS总是沿着最浅的路径搜索，直到找到目标状态或者无法继续搜索为止。BFS的优点是可以找到最优解，但是空间复杂度较高。

UCS（最佳优先搜索）：总是扩展当前代价最小的节点，使用的是priority queue优先队列。UCS在扩展节点时做的goal test，因此在搜索树中，UCS总是沿着代价最小的路径搜索，直到找到目标状态或者无法继续搜索为止。UCS的优点是可以找到最优解，且可以在frontier集中记录所有合适的解，但是空间复杂度较高。

以下是对DFS、BFS和UCS的演示：

假设我们要在一个迷宫中找到从起点到终点的最短路径，其中1表示墙，0表示可以通过的路。迷宫如下所示：

1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 0 1
1 0 1 0 1 0 1 1 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 1 1

我们可以使用DFS、BFS和UCS来寻找最短路径。其中DFS使用stack栈，BFS使用queue队列，UCS使用priority queue优先队列。具体实现可以参考以下代码：

# DFS
def dfs(maze, start, end):
    stack = [(start, [start])]
    visited = set()
    while stack:
        node, path = stack.pop()
        if node == end:
            return path
        if node not in visited:
            visited.add(node)
            for neighbor in get_neighbors(maze, node):
                stack.append((neighbor, path + [neighbor]))
    return None

# BFS
def bfs(maze, start, end):
    queue = [(start, [start])]
    visited = set()
    while queue:
        node, path = queue.pop(0)
        if node == end:
            return path
        if node not in visited:
            visited.add(node)
            for neighbor in get_neighbors(maze, node):
                queue.append((neighbor, path + [neighbor]))
    return None

# UCS
def ucs(maze, start, end):
    queue = [(0, start, [start])]
    visited = set()
    while queue:
        cost, node, path = heapq.heappop(queue)
        if node == end:
            return path
        if node not in visited:
            visited.add(node)
            for neighbor in get_neighbors(maze, node):
                new_cost = cost + 1
                heapq.heappush(queue, (new_cost, neighbor, path + [neighbor]))
    return None

# 获取邻居节点
def get_neighbors(maze, node):
    neighbors = []
    row, col = node
    if row > 0 and maze[row-1][col] == 0:
        neighbors.append((row-1, col))
    if row < len(maze)-1 and maze[row+1][col] == 0:
        neighbors.append((row+1, col))
    if col > 0 and maze[row][col-1] == 0:
        neighbors.append((row, col-1))
    if col < len(maze[0])-1 and maze[row][col+1] == 0:
        neighbors.append((row, col+1))
    return neighbors