随机性并非难点：先决条件有向无环图（DAG）教学序列中的归约与复杂性

文章背景与核心概要

在教育技术领域，如何为学生规划最优的学习路径是一个核心挑战，特别是当知识点之间存在先决条件依赖时。本文将教学序列问题建模为随机最短路径问题，其中学习者尝试掌握某个概念的成功概率取决于当前状态，若失败则状态保持不变。

研究的核心贡献在于证明了该问题的“随机性”可以通过数学归约消除，将其转化为先决条件序理想格上的确定性最短路径问题，且不损失最优解。尽管消除了随机复杂性，研究进一步揭示了该问题在组合优化层面依然是 NP-hard 的。作者通过引入 \(m\Delta\) 诊断指标，对真实教学数据进行了评估，发现实际教学场景往往处于“双重简单”区间，而通过 A* 算法等启发式方法可以有效解决更复杂的构造性实例。

摘要

When a student must learn concepts connected by prerequisite dependencies, when does the order of instruction matter, and what does it cost to find the best one? We study instructional sequencing as a stochastic shortest-path problem in which attempting a concept succeeds with a state-dependent probability and failure leaves the learner state unchanged. We first prove that this stochasticity can be eliminated exactly: the problem collapses to a deterministic shortest-path problem on the lattice of prerequisite order ideals, preserving optimal values and actions. The collapse removes stochastic complexity but not combinatorial complexity: optimal sequencing remains NP-hard -- via reduction from feedback arc set in tournaments -- even with no prerequisite edges, unit costs, uniform binary nonnegative transfer, and success probabilities at least \(1/2\). Hardness is not uniform: when realizable transfer preferences remain jointly acyclic with the prerequisites, any topological order of the residual joint graph is optimal, and fixed prerequisite width yields polynomial-time exact dynamic programming. A computable diagnostic, \(m\Delta\), bounds the value of sequencing before optimization. On 70,893 interactions from an introductory CS course, the diagnostic certifies a doubly easy regime -- little value to optimize and little space to search -- while constructed transfer instances realize the challenging regime, where myopic sequencing suffers large regret yet exact A* with a consistent heuristic expands only linearly many states on that family.

当学生必须学习由先决条件依赖连接的概念时，教学顺序在何时至关重要？寻找最优顺序的代价又是多少？我们将教学序列问题研究为一种随机最短路径问题，其中尝试学习一个概念的成功概率取决于当前状态，而失败则使学习者状态保持不变。我们首先证明了这种随机性可以被精确消除：该问题可归约为先决条件序理想格上的确定性最短路径问题，并保留了最优值和最优动作。这种归约消除了随机复杂性，但并未消除组合复杂性：即使在没有先决条件边、单位成本、统一的二元非负迁移以及成功概率至少为 \(1/2\) 的简化条件下，通过从锦标赛反馈弧集（feedback arc set in tournaments）的归约，我们证明了最优序列问题仍然是 NP-hard 的。这种难度并非普遍存在：当可实现的迁移偏好与先决条件保持联合无环时，剩余联合图的任何拓扑排序都是最优的，且固定的先决条件宽度可实现多项式时间的精确动态规划。我们提出了一种可计算的诊断指标 \(m\Delta\)，用于在优化前界定序列的价值。在针对一门计算机科学入门课程的 70,893 次交互数据测试中，该诊断指标证实了其处于“双重简单”区间——即优化价值小且搜索空间小；而构造的迁移实例则体现了具有挑战性的区间，在这些实例中，短视序列策略会产生巨大的遗憾值，但使用一致启发式函数的精确 A* 算法在该类问题上仅需扩展线性数量的状态。

提交历史

• [v1] 2026年8月5日 周三, 23:00:28 UTC (80 KB)

(注：许可证图标已按系统要求保留)