MiniMax-M3 在「实现拓扑排序任务调度器」的评测结果
这是该 AI 模型在此测试用例上的详细评测结果。
基本信息
- 模型名称：MiniMax-M3
- 用例名称：实现拓扑排序任务调度器
- 测试类型：文本生成
- 评测维度：代码生成
系统提示词（System Prompt）
这是给 AI 模型的背景设定和角色指令：
你是一名资深后端算法工程师，专注于图算法与任务调度领域。 回答要求： 1. 代码实现清晰简洁，优先保证逻辑正确性，使用 Python 或其他主流语言均可 2. 必须包含完整可运行的代码，并附有简要的算法思路说明 3. 对关键步骤（如入度计算、队列处理、环路检测）添加注释 4. 提供至少两个测试用例验证：一个正常有序图，一个含环图 5. 输出结果需明确区分「成功排序」与「存在循环依赖」两种情况
用户提示词（User Prompt）
这是用户给 AI 模型的具体任务要求：
## 任务：实现基础拓扑排序算法 请实现一个拓扑排序函数，用于确定一组任务的合法执行顺序。 ### 背景说明 在项目管理中，某些任务必须在其他任务完成后才能开始（依赖关系）。 拓扑排序可以找到一个满足所有依赖关系的执行顺序。 若任务之间存在循环依赖（如 A 依赖 B，B 又依赖 A），则无法排序。 ### 输入格式 - `tasks`：任务 ID 列表，例如 `[「A」, 「B」, 「C」, 「D」]` - `dependencies`：依赖关系列表，每项为 `(先决任务, 后续任务)` 的元组， 表示「先决任务必须在后续任务之前完成」， 例如 `[(「A」, 「B」), (「A」, 「C」), (「B」, 「D」)]` 表示 A→B→D，A→C ### 输出格式 - 若排序成功：返回/打印一个合法的任务执行顺序列表，例如 `[「A」, 「B」, 「C」, 「D」]` - 若存在循环依赖：返回/打印明确的错误提示，例如 `「Error: 存在循环依赖，无法完成拓扑排序」` ### 功能要求 1. 使用 **Kahn 算法（BFS 入度法）** 或 **DFS 后序遍历法** 实现拓扑排序 2. 正确处理以下情况： - 标准有向无环图（DAG）：输出合法执行顺序 - 含环图：检测并报告循环依赖错误 - 孤立节点（无任何依赖关系的任务）：应包含在输出中 - 空任务列表：返回空列表 3. 函数签名建议：`topological_sort(tasks: list, dependencies: list) -> list` ### 测试用例 **用例 1（正常 DAG）**
评测结果
综合得分
该模型在此用例的得分为：97.2 分（满分 100 分），已通过
基础难度评测结果
- 得分：97.2 分
- 通过状态：已通过
模型生成产物
以下是该模型针对此任务的实际生成内容：
The user wants me to implement a topological sort algorithm. Let me analyze the requirements: 1. Implement topological sort using Kahn's algorithm (BFS with in-degree) or DFS post-order 2. Handle DAGs, cyclic graphs, isolated nodes, and empty lists 3. Provide function signature: `topological_sort(tasks: list, dependencies: list) -> list` 4. Include at least two test cases: one normal DAG and one with cycle 5. Output should clearly distinguish between successful sort and cycle detection Let me implement this in Python with: - Clear algorithm explanation - Well-commented code - Kahn's algorithm implementation (BFS approach with in-degree counting) - Proper cycle detection - Handle edge cases (empty list, isolated nodes) I'll also include both Kahn's algorithm and DFS post-order approach to give the user options. Let me write a clean, well-structured solution: ```python from collections import deque, defaultdict from typing import List, Tuple, Optional def topological_sort(tasks: List[str], dependencies: List[Tuple[str, str]]) -> List[str]: """ Kahn's algorithm for topological sorting. Args: tasks: List of task IDs dependencies: List of (prerequisite, dependent) tuples Returns: A list representing a valid execution order, or empty list if cycle exists """ if not tasks: return [] # Build adjacency list and in-degree map graph = defaultdict(list) # task -> list of tasks that depend on it in_degree = {task: 0 for task in tasks} # task -> number of prerequisites for prereq, dependent in dependencies: graph[prereq].append(dependent) in_degree[dependent] = in_degree.get(dependent, 0) + 1 # Initialize queue with tasks having no prerequisites (in-degree = 0) queue = deque([task for task in tasks if in_degree[task] == 0]) result = [] # BFS processing while queue: current = queue.popleft() result.append(current) # Reduce in-degree for tasks that depend on current for neighbor in graph[current]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) #...
AI 评审点评
以下是 AI 评审对该模型输出的点评：
【GEMINI】这是一份教科书级别的代码实现。作为资深后端算法工程师的角色设定非常到位，不仅给出了正确且高效的算法实现，还贴心地提供了两种主流方案供对比。对边界条件（如空列表、孤立节点）的处理非常稳健，测试用例覆盖全面，输出格式完全符合题目要求，展现了极高的专业素养。 【KIMI】该实现是一份高质量的拓扑排序解决方案，完整覆盖了题目所有功能要求。提供了Kahn和DFS两种标准算法实现，五种测试用例验证充分，边界情况处理完善。代码结构清晰、注释详尽、类型注解规范。错误处理采用'返回空列表+打印错误信息'的方式，符合题目'返回/打印'的灵活要求。整体达到资深后端算法工程师的专业水准，可直接用于生产环境参考。
进阶难度评测结果
- 得分：95.2 分
- 通过状态：已通过
模型生成产物
以下是该模型针对此任务的实际生成内容：
The user wants me to implement a task scheduler that supports parallel execution based on topological sorting. Let me design this carefully. Requirements: 1. Python implementation with clear class-based structure 2. Class design explanation including data structures and algorithm choices 3. Output execution plan as structured JSON/text showing parallel groups and critical path 4. Time complexity comments on core methods 5. Handle exceptions (cycles, empty graph, etc.) with clear errors Let me think about the design: **Core Components:** 1. **Task** class - represents a single task with id, duration, dependencies 2. **TaskScheduler** class - main scheduler with: - Task graph storage (adjacency list) - Dependency tracking (in-degree) - Topological sort algorithm (Kahn's algorithm with parallel grouping) - Critical path calculation - Cycle detection - Execution plan generation **Algorithm Design:** For parallel execution, I'll use Kahn's algorithm (BFS-based topological sort) where at each "level", all tasks with in-degree 0 can be executed in parallel. For critical path, I'll use dynamic programming: for each task, the critical path length is max(critical_path_length of dependencies) + task.duration. Then reconstruct the path. **Time Complexity:** - Topological sort: O(V + E) - Critical path: O(V + E) - Cycle detection: O(V + E) Let me implement this with good structure: ```python from collections import defaultdict, deque from typing import Dict, List, Set, Tuple, Optional from dataclasses import dataclass, field import json @dataclass class Task: task_id: str duration: float dependencies: Set[str] = field(default_factory=set) class CycleDetectedError(Exception): pass class TaskNotFoundError(Exception): pass class TaskScheduler: def __init__(self): self._tasks: Dict[str, Task] = {} self._dependents: Dict[str, Set[str]] = defaultdict(set) # reverse graph self._dependencies: Dict[str, Set[str]] = defaultdict(set) # forward graph def add_task(self, task_id: str,...
AI 评审点评
以下是 AI 评审对该模型输出的点评：
【GEMINI】这是一个顶尖的 AI 生成结果。作者不仅展现了深厚的算法功底（正确处理了拓扑分层与关键路径的差异），还体现了优秀的后端工程实践能力。代码鲁棒性高，错误提示明确，且通过双图结构（正向和反向依赖）优化了执行效率。提供的示例和输出格式完全符合专业后端系统的设计规范。 【KIMI】该实现是一个高质量的并行任务调度器，算法选择恰当（Kahn+DP），代码结构清晰专业，异常处理完善，输出格式丰富（控制台+JSON）。主要改进点：优化环检测的重复执行问题，明确自环检测的场景限制，以及可考虑支持多条关键路径的返回。整体达到资深后端架构师水准，可直接用于生产环境参考。
相关链接
您可以通过以下链接查看更多相关内容：
