当前位置：首页 > news >正文

Floyd与A*算法解析：最短路径与骑士攻击实战

news 2026/8/7 10:43:44

1. 项目概述

"代码随想录算法训练营第六十天"这个标题背后隐藏着两个经典的算法题目：97号题"小明逛公园"和127号题"骑士的攻击"。作为算法训练营的收官之作，这两个题目分别代表了图论和搜索算法中的典型问题。

在实际编程面试中，类似"小明逛公园"的最短路径问题和"骑士的攻击"这样的棋盘搜索问题经常出现。根据我的面试官经验，这类题目能够很好地考察候选人对基础算法的掌握程度和问题建模能力。

2. 核心算法解析

2.1 小明逛公园与Floyd算法

"小明逛公园"本质上是一个多源最短路径问题。公园可以建模为一个带权有向图，其中节点代表景点，边代表路径，权重代表距离。Floyd算法是解决这类问题的经典方案。

Floyd算法的核心思想是动态规划。它通过三重循环逐步更新所有节点对之间的最短距离：

def floyd(graph): n = len(graph) dist = [[float('inf')]*n for _ in range(n)] for i in range(n): for j in range(n): if i == j: dist[i][j] = 0 elif graph[i][j] != 0: dist[i][j] = graph[i][j] for k in range(n): for i in range(n): for j in range(n): if dist[i][j] > dist[i][k] + dist[k][j]: dist[i][j] = dist[i][k] + dist[k][j] return dist

注意：Floyd算法的时间复杂度是O(n³)，适合节点数较少的情况（通常n<200）。对于大型图，Dijkstra或A*算法更合适。

2.2 骑士的攻击与A*搜索

"骑士的攻击"是一个典型的棋盘搜索问题，要求计算骑士在棋盘上能够攻击的所有位置。这个问题可以转化为图搜索问题，其中每个棋盘格子是一个节点，骑士的合法移动构成边。

A*算法是解决这类问题的高效方法。它结合了Dijkstra的最短路径保证和启发式搜索的效率：

def a_star(start, target, board_size): def heuristic(pos): # 曼哈顿距离启发函数 return abs(pos[0]-target[0]) + abs(pos[1]-target[1]) open_set = {start} came_from = {} g_score = {start: 0} f_score = {start: heuristic(start)} while open_set: current = min(open_set, key=lambda pos: f_score[pos]) if current == target: return reconstruct_path(came_from, current) open_set.remove(current) for neighbor in get_knight_moves(current, board_size): tentative_g = g_score[current] + 1 if tentative_g < g_score.get(neighbor, float('inf')): came_from[neighbor] = current g_score[neighbor] = tentative_g f_score[neighbor] = tentative_g + heuristic(neighbor) if neighbor not in open_set: open_set.add(neighbor) return None

3. 算法实现细节

3.1 Floyd算法的优化技巧

在实际编码中，Floyd算法有几个关键优化点：

初始化技巧：可以直接用图的邻接矩阵初始化距离矩阵，避免多余的赋值操作
提前终止：如果发现dist[i][k]或dist[k][j]为无穷大，可以跳过内层循环
空间优化：对于无向图，可以利用对称性只计算一半矩阵

3.2 A*算法的启发函数选择

对于棋盘类问题，启发函数的选择直接影响算法效率：

曼哈顿距离：适用于只能上下左右移动的场景
切比雪夫距离：max(dx, dy)，更适合国际象棋中骑士的移动方式
欧几里得距离：直线距离，计算成本较高但更精确

对于骑士移动问题，切比雪夫距离是最合适的启发函数：

def chebyshev_heuristic(pos, target): return max(abs(pos[0]-target[0]), abs(pos[1]-target[1]))

4. 常见问题与解决方案

4.1 Floyd算法中的负权边处理

Floyd算法可以处理负权边，但不能处理负权环。如果图中存在负权环，算法会给出错误结果。解决方法：

运行算法后检查对角线元素：如果dist[i][i]<0，说明存在经过i的负权环
对于必须处理负权环的场景，可以考虑Bellman-Ford算法

4.2 A*算法的可采纳性保证

A*算法要保证找到最优解，启发函数必须满足可采纳性（admissible）条件：

启发函数不能高估实际成本
对于国际象棋骑士移动，每个移动的成本是1，所以启发函数值必须≤实际步数

如果启发函数不满足这些条件，A*可能找到非最优解或者效率降低。

5. 性能对比与选择建议

5.1 Floyd vs Dijkstra vs A*

算法	时间复杂度	空间复杂度	适用场景
Floyd	O(n³)	O(n²)	多源最短路径，小规模图
Dijkstra	O(E + VlogV)	O(V)	单源最短路径，无负权边
A*	取决于启发函数质量	O(V)	单源单目标，有良好启发函数

5.2 骑士攻击问题的多种解法

对于"骑士的攻击"问题，除了A*算法外，还可以考虑：

BFS：简单可靠，适合小棋盘
双向BFS：从起点和终点同时搜索，效率更高
预处理法：预先计算每个位置的攻击范围，查询时直接返回

选择哪种方法取决于具体需求：

如果是单次查询，BFS足够
如果是多次查询，预处理更高效
如果棋盘很大且有明确目标位置，A*最优

6. 实际编码技巧

6.1 图的表示方法选择

对于"小明逛公园"这类问题，图的表示方式影响算法实现：

邻接矩阵：适合稠密图，Floyd算法直接使用
邻接表：适合稀疏图，节省空间
边列表：某些特定算法需要

Python实现邻接矩阵的示例：

# 公园地图示例：4个景点，0表示无直接路径 park_map = [ [0, 2, 6, 4], # 景点0到其他景点的距离 [float('inf'), 0, 3, float('inf')], # 景点1 [7, float('inf'), 0, 1], # 景点2 [5, float('inf'), 12, 0] # 景点3 ]

6.2 骑士移动的生成方法

对于棋盘问题，生成合法移动是关键步骤。国际象棋骑士的移动是"日"字形：

def get_knight_moves(pos, board_size): x, y = pos moves = [] # 8个可能的移动方向 directions = [(1,2),(2,1),(-1,2),(-2,1), (1,-2),(2,-1),(-1,-2),(-2,-1)] for dx, dy in directions: nx, ny = x + dx, y + dy if 0 <= nx < board_size and 0 <= ny < board_size: moves.append((nx, ny)) return moves

提示：使用生成器表达式可以更高效地生成移动，特别是对于大型棋盘。

7. 测试用例设计

7.1 最短路径测试要点

测试Floyd算法时，应该考虑以下情况：

普通连通图
存在不可达节点
带负权边但不含负权环
完全图（每两个节点间都有边）
稀疏图（边数远小于完全图）

7.2 骑士攻击测试场景

对于骑士问题，关键测试用例包括：

棋盘角落位置
中心位置
边界位置
极小棋盘（3×3）
极大棋盘（性能测试）

示例测试用例：

def test_knight_attack(): # 测试8x8棋盘 assert len(get_knight_moves((0,0), 8)) == 2 assert len(get_knight_moves((3,3), 8)) == 8 assert len(get_knight_moves((7,7), 8)) == 2