Prolog新手求助：任务最早开始时间计算问题

嘿，作为Prolog新手碰到这个计算任务最早开始时间的问题，确实容易卡壳——我当初刚学的时候也对着依赖关系懵了好一阵！别着急，我来给你拆解怎么用Prolog搞定这个需求。

首先得把规则吃透：

• 没有前置任务的任务，最早开始时间（EST）就是0
• 有前置任务的任务，它的EST等于所有前置任务的「最早完成时间（EST+任务耗时）」里的最大值——毕竟得等所有前置都做完，才能启动当前任务

我们分三步来写代码：定义任务耗时、定义依赖关系、写核心计算谓词。

1. 定义任务耗时 #

先把每个任务需要的时间用事实声明出来，格式是task_duration(任务ID, 耗时)：

% 示例任务：a耗时2，b耗时3，以此类推
task_duration(a, 2).
task_duration(b, 3).
task_duration(c, 1).
task_duration(d, 4).
task_duration(e, 2).

2. 定义前置依赖关系 #

同样用事实声明哪个任务依赖哪个前置任务，格式是prerequisite(任务ID, 前置任务ID)：

% 示例依赖：b必须等a做完，d必须等b和c都做完
prerequisite(b, a).
prerequisite(c, a).
prerequisite(d, b).
prerequisite(d, c).
prerequisite(e, d).

3. 核心计算谓词 #

这部分是关键，我们写两个谓词：一个算最早开始时间，一个可以辅助算最早完成时间。

计算最早开始时间 #

% 情况1：没有前置任务的任务，EST为0
earliest_start_time(Task, 0) :-
    \+ prerequisite(Task, _),  % \+ 表示“不存在”，即该任务没有任何前置
    task_duration(Task, _).

% 情况2：有前置任务的任务，取所有前置完成时间的最大值作为EST
earliest_start_time(Task, Est) :-
    prerequisite(Task, _),  % 确认该任务有前置
    % 收集所有前置任务的最早完成时间
    findall(FinishTime, 
            (prerequisite(Task, PreTask), 
             earliest_start_time(PreTask, PreEst), 
             task_duration(PreTask, PreDur), 
             FinishTime is PreEst + PreDur), 
            AllFinishTimes),
    max_list(AllFinishTimes, Est).  % 取最大值就是当前任务的EST

辅助计算最早完成时间（可选） #

如果想直接看任务什么时候能做完，可以加这个谓词：

earliest_finish_time(Task, FinishTime) :-
    earliest_start_time(Task, Est),
    task_duration(Task, Dur),
    FinishTime is Est + Dur.

比如我们查询任务e的最早开始时间：

?- earliest_start_time(e, Est).
Est = 9.

对应的计算逻辑是：

• a的EST=0，完成时间=0+2=2
• b的EST=2，完成时间=2+3=5；c的EST=2，完成时间=2+1=3
• d的EST=max(5,3)=5，完成时间=5+4=9
• e的EST=9，完成时间=9+2=11

• 一定要确保任务依赖是有向无环图（DAG），不能出现循环依赖（比如a依赖b，b又依赖a），否则Prolog会陷入无限递归
• 所有任务的耗时和依赖都要完整定义，不然谓词会返回false

内容的提问来源于stack exchange，提问作者Mantas Astra