用Prolog实现动态规划调度

Question

我正在尝试用Prolog创建一个简单的调度器，它接受一系列课程，以及他们提供的学期和用户对课程的排名。这些输入被转换成事实，比如

course('CS 4812','Quantum Information Processing',1.0882353,s2012).
course('Math 6110','Real Analysis I',0.5441176,f2011).

其中第三个条目是分数。目前，我的数据库大约有60个类，但我希望程序最终能够处理更多的类。我很难让我的DP实现在一个非平凡的输入上工作。答案是正确的，但所花费的时间与蛮力算法是相同的。我用一个动态谓词来处理记忆：

:- dynamic(stored/6).
memo(Result,Schedule,F11,S12,F12,S13) :-
  stored(Result,Schedule,F11,S12,F12,S13) -> true;
  dpScheduler(Result,Schedule,F11,S12,F12,S13),
  assertz(stored(Result,Scheduler,F11,S12,F12,S13)).

dpScheduler的参数是最优时间表(班级列表及其分数的元组)，到目前为止选择的班级，以及2011年秋季、2012年春季、2012年秋季和2013年春季学期还有多少课程需要选择。一旦调度器有了竞争时间表，它就会用evalSchedule获得分数，它只是对班级的分数求和。

dpScheduler((Acc,X),Acc,0,0,0,0) :- 
  !, evalSchedule(X,Acc).

我每个学期都会把dpScheduler拆分，但它们看起来都差不多。这是2011年秋季的条款，第一个学期的选择。

dpScheduler(Answer,Acc,N,B,C,D) :-
  !, M is N - 1,
  getCourses(Courses,f2011,Acc),
  lemma([Head|Tail],Courses,Acc,M,B,C,D),
  findBest(Answer,Tail,Head).

lemma谓词计算所有子目标。

lemma(Results,Courses,Acc,F11,S12,F12,S13) :-
  findall(Result, 
    (member(Course,Courses), memo(Result,[Course|Acc],F11,S12,F12,S13)),
    Results).

我的表现一直很糟糕，如果有任何关于如何改进它的建议，我将不胜感激。另外，我是一个新的Prolog程序员，我没有花太多时间阅读别人的Prolog代码，所以我的程序可能是单调的。任何关于这方面的建议都将非常感谢。

Answer 1

性能不佳的原因有几个：

首先，assert/3不是很快，所以如果有很多断言，你会花很多时间。

然后，prolog使用基于第一个参数的哈希表来匹配子句。在你的例子中，第一个参数是在调用时未实例化的结果，所以我认为你会因此而有性能损失。你可以通过重新排序参数来解决这个问题。我认为您可以更改哈希表所基于的参数，但我在swi-prolog手册中看不到这样做:/

此外，prolog并不是真正以出色的性能xd而闻名

我建议使用XSB (如果可能)，它提供了自动记忆化(表)；您只需编写:-table(my_predicate/42)，它会处理所有事情。我觉得它也比swipl快一点。

除此之外，您可以尝试使用一个包含所有计算值的列表并传递它；可能是一个association list。

编辑:我真的看不出你在哪里调用记忆谓词