任务依赖形成环时,一部分任务会一直等不到前置条件。未能排出的任务不一定都在环上,也可能只是依赖了环中的任务;把这两类分开更有助于修复关卡配置。
本篇使用一组可以手算或逐行复查的虚构游戏记录。先读清操作顺序与边界,再看完整过程;它不是某一款现有游戏的隐藏公式,也不要求读者安装工具。
规则与输入
八个节点,边从前置任务指向后续任务。每轮同时移除所有剩余入度为零的节点,直到没有可移除项。另按可达关系找出能沿非空路径回到自己的循环节点,以及它们能够到达的其他受阻节点。
八节点有向边[(0, 1), (0, 6), (1, 2), (1, 4), (2, 0), (2, 3), (4, 5), (4, 6), (5, 6), (7, 0)]
逐步计算与结果
节点0的直接后继[1, 6],沿至少一条边可到达[0, 1, 2, 3, 4, 5, 6];能够回到自身,属于循环成员。
节点1的直接后继[2, 4],沿至少一条边可到达[0, 1, 2, 3, 4, 5, 6];能够回到自身,属于循环成员。
节点2的直接后继[0, 3],沿至少一条边可到达[0, 1, 2, 3, 4, 5, 6];能够回到自身,属于循环成员。
节点3的直接后继[],沿至少一条边可到达[];不能沿非空路径回到自身,不是循环成员。
节点4的直接后继[5, 6],沿至少一条边可到达[5, 6];不能沿非空路径回到自身,不是循环成员。
节点5的直接后继[6],沿至少一条边可到达[6];不能沿非空路径回到自身,不是循环成员。
节点6的直接后继[],沿至少一条边可到达[];不能沿非空路径回到自身,不是循环成员。
节点7的直接后继[0],沿至少一条边可到达[0, 1, 2, 3, 4, 5, 6];不能沿非空路径回到自身,不是循环成员。
移除轮次1,本轮就绪[7],同轮项一起移除后再检查下一轮。
移除轮次[[7]],最终剩余[0, 1, 2, 3, 4, 5, 6];其中环成员[0, 1, 2],仅受环拖住的后继[3, 4, 5, 6]。
怎样独立复核
独立建立可达表:若一个节点可达自身,它位于某个循环中。循环节点及其全部后继应恰好组成移除过程的剩余集合;其余节点可以按轮次完成,不应误标为循环成员。
受阻节点也需要等待修复,但不一定要删掉它自身的依赖。应先检查形成环的边是否写反或遗漏规则。本例只是纯依赖图,没有条件分支、人工跳过或动态新增任务,不能代替完整的任务系统判断。
练习时可以只改变一个输入,再预测哪一步会最先改变。保留中间记录,检查空状态、相等数值和刚好落在边界的情况。最终结果碰巧相同,并不能证明两个过程等价;反过来,采用不同规则得出不同结果,也不应立即视作程序故障。
