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³)适合节点数较少的情况通常n200。对于大型图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, keylambda 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 None3. 算法实现细节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*算法时间复杂度空间复杂度适用场景FloydO(n³)O(n²)多源最短路径小规模图DijkstraO(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)) 28. 算法扩展与应用8.1 动态规划的进一步优化Floyd算法可以通过分块处理优化内存访问模式提高缓存命中率。对于特别大的图可以考虑分块Floyd算法并行化处理使用更高效的矩阵运算库如NumPy8.2 启发式搜索的变种A*算法有多种改进版本IDA*迭代加深的A*节省内存D*动态环境中的A*变种Theta*允许任意角度移动的路径规划对于游戏开发等实时应用这些变种算法非常有用。9. 面试常见问题在技术面试中与这两个题目相关的问题可能包括Floyd算法为什么能处理负权边A*算法的最优性条件是什么如何证明一个启发函数是可采纳的骑士移动问题中为什么切比雪夫距离比曼哈顿距离更适合当图的规模很大时如何优化Floyd算法准备这些问题可以帮助你在面试中更好地展示算法理解能力。10. 学习资源推荐要深入理解这些算法我推荐以下资源《算法导论》中的图算法章节《人工智能现代方法》中的搜索算法部分LeetCode上的相关题目访问所有节点的最短路径Floyd应用进击的骑士骑士移动问题可视化工具VisualGo.net 的图算法可视化Red Blob Games 的路径规划教程在实际编码练习中我建议先从简单的BFS实现开始逐步过渡到更复杂的A*算法。对于Floyd算法可以先用小规模的图手动计算验证代码正确性。