分别用两种估价函数实现完整的代码

由于完整地实现一个A*算法涉及到很多细节，包括数据结构、状态空间的搜索以及路径回溯等，我将以Python语言为例，并简要展示如何使用启发式估价函数。这里我会展示曼哈顿距离估价和简单的广度优先搜索（即无启发式版本）。

### 1. 曼哈顿距离估价（A*）

首先需要定义一些基本的数据结构和辅助函数：

import heapq

class Node:
    def __init__(self, position, parent=None, g=0, h=0, f=0):
        self.position = position
        self.parent = parent
        self.g = g
        self.h = h
        self.f = f

def manhattan_distance(position, target):
    return sum(abs(x - y) for x, y in zip(position, target))

def heuristic_g_score(node, target):
    return node.g + manhattan_distance(node.position, target.position)

def a_star_search(maze, start, end, open_set=None):
    if open_set is None:
        open_set = []
        
    if start is None:
        start = Node(start, g=0, h=manhattan_distance(start, end))
    
    open_set.append((start.f, start))
    explored = set()

    while open_set:
        _, current = heapq.heappop(open_set)
        if current.position == end.position:
            path = [end]
            while current.parent:
                path.append(current)
                current = current.parent
            return path[::-1]

        explored.add(current.position)
        for neighbor in neighbors(maze, current.position):
            if neighbor.position in explored:
                continue
            
            tentative_g_score = current.g + 1
            if neighbor not in open_set or tentative_g_score < neighbor.g:
                neighbor.g = tentative_g_score
                neighbor.h = manhattan_distance(neighbor.position, end.position)
                neighbor.f = neighbor.g + neighbor.h
                heapq.heappush(open_set, (neighbor.f, neighbor))

    return None  # 没有找到路径

# 辅助函数：获取邻居节点
def neighbors(maze, position):
    rows, cols = len(maze), len(maze[0])
    yield from ((x+1, y) if 0 <= x < cols and maze[x][y] == 0 else None
               for x, y in ((position[0], position[1]), (position[0]-1, position[1]), (position[0], position[1]-1), (position[0], position[1]+1)))

### 2. 广度优先搜索（无启发式）

from collections import deque

def bfs_search(maze, start, end):
    visited = set()
    queue = deque([(start, 0)])

    while queue:
        position, depth = queue.popleft()
        if position == end:
            path = [end]
            while position != start:
                path.append(position)
                position, _ = queue.pop()
            return path[::-1]

        if position not in visited:
            visited.add(position)
            for neighbor in neighbors(maze, position):
                if neighbor is not None and neighbor not in visited:
                    queue.append((neighbor, depth + 1))

    return None  # 没有找到路径

这两个函数都是在给定的`maze`、起点`start`和终点`end`上寻找路径。`bfs_search`没有使用启发式，而`a_star_search`利用了曼哈顿距离作为启发式。