Prolog 中的动态规划调度器
我正在尝试在 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 代码，所以我的程序可能不惯用。对此的任何建议也将不胜感激。
I'm trying to create a simple scheduler in Prolog that takes a bunch of courses along with the semesters they're offered and a user's ranking of the courses. These inputs get turned into facts like
course('CS 4812','Quantum Information Processing',1.0882353,s2012).
course('Math 6110','Real Analysis I',0.5441176,f2011).
where the third entry is a score. Currently, my database is around 60 classes, but I'd like the program to eventually be able to handle more. I'm having trouble getting my DP implementation to work on a nontrivial input. The answers are correct, but the time spent is on the same order as the brute force algorithm. I handle memoization with a dynamic predicate:
:- 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)).
The arguments to dpScheduler are the optimal schedule (a tuple of a list of classes and its score), the classes chosen so far, and how many classes are remaining to be chosen for the Fall 2011, Spring 2012, Fall 2012, and Spring 2013 semesters. Once the scheduler has a compete schedule, it gets the score with evalSchedule, which just sums up the scores of the classes.
dpScheduler((Acc,X),Acc,0,0,0,0) :-
!, evalSchedule(X,Acc).
I broke up dpScheduler up for each semester, but they all pretty much look the same. Here is the clause for Fall 2011, the first semester chosen.
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).
The lemma predicate computes all the subgoals.
lemma(Results,Courses,Acc,F11,S12,F12,S13) :-
findall(Result,
(member(Course,Courses), memo(Result,[Course|Acc],F11,S12,F12,S13)),
Results).
My performance has been horrendous, and I'd be grateful for any pointers on how to improve it. Also, I'm a new Prolog programmer, and I haven't spent much time reading others' Prolog code, so my program is probably unidiomatic. Any advice on that would be much appreciated as well.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
性能不佳有几个原因：
首先，assert/3 不是很快，所以如果有很多断言，你会花很多时间。
然后，prolog 使用基于第一个参数的哈希表来匹配子句。在你的例子中，第一个参数是结果，它在调用时没有被实例化，所以我认为你会因此而受到性能损失。您可以通过重新排序参数来解决这个问题。我认为您可以更改哈希表所基于的参数，但我在 swi-prolog 手册中没有看到如何更改：/
另外，prolog 并不是真正以出色的性能而闻名 xd
我建议使用 XSB（如果可能）提供自动记忆（表格）；你只需写
:-table(my_predicate/42) 它会处理一切。我认为它也比 swipl 快一点。
除此之外，您可以尝试使用包含所有计算值的列表并将其传递；可能是关联列表。
编辑：我真的不明白你在哪里调用记忆谓词
There are a couple of reasons for bad performance:
First of all, assert/3 is not very fast so you spend a lot of time there if there are a lot of asserts.
Then, prolog uses a hash table based on the first argument to match clauses. In your case, yhe first argument is the Result which is uninstantiated when it's called so I think you would have a performance penalty because of that. You could solve this be reordering the arguments. I thought that you could change the argument on which the hash table is based but i dont see how in the swi-prolog manual :/
Also, prolog isnt really renowned for great performance xd
I suggest to use XSB (if possible) which offers automatic memoization (tabling); you simply write
:-table(my_predicate/42) and it takes care of everything. I think that it's a bit faster than swipl too.
Other than that, you could try to use a list with all the calculated values and pass it around; maybe an association list.
edit: i dont really see where you call the memoization predicate