Планировщик динамического программирования в прологе - PullRequest
Новая
       22

Планировщик динамического программирования в прологе

3 голосов
/ 01 июня 2011

Я пытаюсь создать простой планировщик в Прологе, который будет проходить несколько курсов вместе с предлагаемыми семестрами и рейтингом курсов пользователя. Эти данные превращаются в факты, подобные 

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).

Мое выступление было ужасным, и я был бы благодарен за любые советы о том, как его улучшить. Кроме того, я новичок в программировании на Прологе, и я не тратил много времени на чтение кода Пролога других, поэтому моя программа, вероятно, не односторонняя. Любые советы по этому вопросу также будут высоко оценены.

1 Ответ

2 голосов
/ 01 июня 2011

Есть несколько причин плохой работы:
Прежде всего, assert / 3 не очень быстрый, поэтому вы проводите там много времени, если есть много утверждений.

Затем пролог использует хеш-таблицу на основе первого аргумента для сопоставления предложений. В вашем случае, первый аргумент - это Результат, который не вызывается, когда он вызывается, поэтому я думаю, что из-за этого у вас будет снижение производительности. Вы могли бы решить это путем изменения порядка аргументов. Я думал, что вы могли бы изменить аргумент, на котором основана хеш-таблица, но я не вижу, как в руководстве по swi-prolog: /

Кроме того, пролог на самом деле не славится отличной производительностью xd

Я предлагаю использовать XSB (если возможно), который предлагает автоматическое запоминание (табулирование); ты просто пишешь : -table (my_predicate / 42) и обо всем позаботится. Я думаю, что это немного быстрее, чем swipl тоже.

Кроме этого, вы можете попытаться использовать список со всеми вычисленными значениями и передать его; может быть список ассоциаций .

edit: я действительно не вижу, где вы называете предикат памятки

...