подходит фильмы на DVD, работает, но стиль / код вопросы

Question

Я сделал программу для пролога, чтобы показать мне лучший способ установки материала на DVD.Вопросы приведены в комментариях к коду для справки, который я вставлю ниже, но он сводится к следующему:

1. Существует ли своего рода оператор с перевернутым вырезом, который заставляет его искатьбольше хотя уже совпадает?Посмотрите fitexact, что-то вроде fitexact (Size, Sum, L, L): - Sum

2. Какой лучший способ отслеживать уже обработанные фильмы?Я убираю их, но удивляюсь, как это сделать без этого.

3. fitfuzzy использует конструкцию if then.Я не уверен, что думать о них, это кажется странным в прологе.Однако попытка сделать его рекурсивным оставил меня в замешательстве:)

    % given a list of movies and sizes, try to fit them all onto dvd's
    % wasting as little space as possible.

    % set the dvd size
    dvdsize(4812).

    % sum of all movies in the db
    movies_size(Size) :- findall(S, movie(_,S), LS), sum_list(LS,Size).

    % count of all movies in the db
    movies_count(Count) :- findall(S, movie(_,S), LS), length(LS,Count).

    % see which ones fit exactly
    % this is where i got into trouble, the original idea was to make
    % it like the fuzzy search below but i don't understand how i can 
    % express 'when there are no more movies which make an exact fit,
    % and the sum is smaller then the dvdsize the list is ok too'. 
    fitexact(Movies) :- dvdsize(Size), fitexact(Size, 0, [], Movies).

    % Stop when there's a perfect fit
    % so here i tried Size,Sum and Sum<Size in the body. That obviously
    % doesn't work since it instantly matches. 
    fitexact(Size, Size, Movies, Movies).
    % since otherwise the same movies show up on different dvd's i 
    % thought it would be best to delete them after they fitted. 
    % if I don't want to do that, what's the best way to make sure once
    % a movie is processed it won't show up again? Should it have an extra
    % flag like processed(movie(name,size,processed) or should i assert 
    % done dvd's and see if they're already in them? I wonder how long this
    % all would take since it's already quite slow as is.
    %% :-
    %%  forall(member(Movie,Movies), retract(movie(Movie,_))). %%, !.

    % Otherwise keep filling
    fitexact(Size, Sum, Acc, Movies) :-
      movie(Movie, MovieSize),
      \+ member(Movie, Acc), % no doubles!
      NewSum is Sum + MovieSize,
      NewSum =< Size,
      fitexact(Size, NewSum, [Movie|Acc], Movies). 

    removedvd(DVD) :- 
      forall(member(Movie,DVD),retract(movie(Movie,_))).

    % do a fuzzy fit, try exact fits with decreasing size when
    % there are no exact fits.
    fitfuzzy(DVD) :- dvdsize(Size), fitfuzzy(DVD,Size,0).
    fitfuzzy(_,Size,Size) :- movies_size(Size), !.
    fitfuzzy(_,Size,Size) :- dvdsize(Size), !.
    fitfuzzy(DVD,Size,Wasted) :-
      CheckSize is Size - Wasted,
    % this feels like a horrible way to do this. I very much like suggestions
    % about how to make it recursive or better in general.
      ( fitexact(CheckSize, 0, [], DVD)
      -> removedvd(DVD) 
      ;  NewWasted is Wasted + 1, 
         write('fitfuzzy: Increasing wasted space to '), write(NewWasted), nl,
         fitfuzzy(DVD,Size,NewWasted)
      ).

    status :-
      movies_count(MoviesLeft),
      movies_size(MoviesSize), 
      write('Movies left: '), write(MoviesLeft), nl,
      write('Size left  : '), write(MoviesSize), nl.

    burnloop :-
     movies_count(C), C>0,
     fitfuzzy(DVD),
     status,
     write('DVD = '), print(DVD),nl, nl,
     burnloop.

    % movies.db contains a list of movie(Name,Size). statements. It also
    % must have :- dynamic(movie/2). on top for retract to work.
    go :-
     ['movies.db'],
     burnloop.

Answer 1

Просто общий комментарий: вместо отслеживания обработанных фильмов, я считаю гораздо более естественным сначала получить (например, через findall / 3) список фильмов, которые все еще нужны обработать, а затем просто отработать этот список. Таким образом, в качестве первого аргумента у вас есть burn_dvd(List0, DVD, List), который принимает список фильмов (возможно, в сочетании с их размерами, скажем, в виде вида movie_size(Name, Size)), создает один DVD (выбирая столько фильмов из List0, сколько нужно. на одном DVD, например, после сортировки списка по размеру и т. д.), а третий аргумент - это список оставшихся фильмов. Затем у вас есть естественное расширение burn_dvds (Список, DVD), которое просто создает DVD, пока не останется больше фильмов:

burn_dvds([], []) :- !.
burn_dvds(Movies0, [DVD|DVDs]) :-
    burn_dvd(Movies0, DVD, Movies),
    burn_dvds(Movies, DVDs).

Для этого не требуется assert / 1 или retract / 1. Множество решений возможно, если burn_dvd / 3 недетерминированно создает один DVD, что вам и нужно, а также кажется естественным.

Использование if-then-else совершенно нормально, однако все, что может быть выражено сопоставлением с образцом, должно быть выражено сопоставлением с образцом, поскольку обычно он дает более общий, а также более эффективный код.

format / 2 может также помочь вам с выводом: вместо:

write('Movies left: '), write(MoviesLeft), nl

Вы можете написать:

format("Movies left: ~w\n", [MoviesLeft])

Как правило, ручной вывод необходим редко, так как вы всегда можете предложить решения для печати на высшем уровне. В нашем случае burn_dvds / 2, естественно, выдает список DVD-дисков в качестве ответа при запросе.

Answer 2

Мой предыдущий ответ был «быстрый и грязный», и вскоре показывает его ограничения по мере роста количества фильмов. Вот лучший способ найти лучшее соответствие и сравнение с предыдущим ответом (переформулировано в соответствии с требованиями теста).

Ключ для оптимизации предлагается тегом рюкзак , который справедливо использовал Аксель при публикации вопроса. Я искал в CLP (FD) поддержку подходящего способа решения проблемы, вот она:

:- [library(clpfd)].

%%  use CLP(FD) to find best fit
%
burn_knapsack(Best, Wasted) :-
    dvdsize(Max),
    findall(Title - Size, movie(Title, Size), Movies),
    knaps(Movies, Max, Best, Wasted).

knaps(Movies, Max, Best, Wasted) :-
    findall([Flag, Title, Size],
        (Flag in 0..1, member(Title - Size, Movies)), AllMovies),
    transpose(AllMovies, [ToBurn, Titles, Sizes]),

    Actual #=< Max,
    scalar_product(Sizes, ToBurn, #=, Actual),
    labeling([max(Actual)], [Actual|ToBurn]),
    findall(Title, (nth1(I, ToBurn, 1),
            nth1(I, Titles, Title)), Best),
    Wasted is Max - Actual.

%%  compute all combinations of movies that fit on a dvd
%   it's a poor man clpfd:scalar_product/4
%
burn_naive(Best, Wasted) :-
    dvdsize(Max),
    findall(Title - Size, movie(Title, Size), Movies),
    naive(Movies, Max, Best, Wasted).

naive(Movies, Max, Best, Wasted) :-
    setof(Wasted-Sequence, fitmax(Movies, Max, Wasted, Sequence), [Wasted-Best|_]).

fitmax(L, AvailableRoom, WastedSpace, [Title|Others]) :-
    select(Title - MovieSize, L, R),
    MovieSize =< AvailableRoom,
    RoomAfterMovie is AvailableRoom - MovieSize,
    fitmax(R, RoomAfterMovie, WastedSpace, Others).
fitmax(_, WastedSpace, WastedSpace, []).

%%  run test with random generated list
%
%   From,To are num.of.movies
%   SzMin, SzMax min/max+1 of each movie size
%
test_performance(From, To, DvdSize, SzMin, SzMax) :-
    forall((between(From, To, NumMovies),
        gen_movies(NumMovies, SzMin, SzMax, Movies)
           ),
           (   (   NumMovies < 11
           ->  test(naive, Movies, DvdSize)
           ;   true
           ),
           test(knaps, Movies, DvdSize)
           )).
test(Method, Movies, DvdSize) :-
    time(once(call(Method, Movies, DvdSize, Best, Wasted))),
    writeln((Method, Best, Wasted)).

gen_movies(NumMovies, SzMin, SzMax, Movies) :-
    findall(Title-Size,
        (   between(1, NumMovies, Title),
            random(SzMin, SzMax, Size)
        ), Movies).

Я ограничил тест для наивный менее чем 11 фильмами, чтобы избежать переполнения стека

?- test_performance(8,20, 30, 3,7).
% 93,155 inferences, 0,140 CPU in 0,140 seconds (100% CPU, 665697 Lips)
naive,[1,2,3,5,6],0
% 235,027 inferences, 0,159 CPU in 0,159 seconds (100% CPU, 1481504 Lips)
knaps,[2,3,5,6,8],0
% 521,369 inferences, 0,782 CPU in 0,783 seconds (100% CPU, 666694 Lips)
naive,[1,2,3,4,5,6],0
% 163,858 inferences, 0,130 CPU in 0,131 seconds (100% CPU, 1255878 Lips)
knaps,[3,4,5,6,7,9],0
% 1,607,675 inferences, 2,338 CPU in 2,341 seconds (100% CPU, 687669 Lips)
naive,[1,2,3,4,7,8],0
% 184,056 inferences, 0,179 CPU in 0,180 seconds (100% CPU, 1027411 Lips)
knaps,[5,6,7,8,9,10],0
% 227,510 inferences, 0,156 CPU in 0,156 seconds (100% CPU, 1462548 Lips)
knaps,[5,6,8,9,10,11],0
% 224,621 inferences, 0,155 CPU in 0,155 seconds (100% CPU, 1451470 Lips)
knaps,[6,7,8,9,10,11,12],0
% 227,591 inferences, 0,159 CPU in 0,159 seconds (100% CPU, 1434836 Lips)
knaps,[5,7,9,10,11,12,13],0
% 389,764 inferences, 0,263 CPU in 0,263 seconds (100% CPU, 1482017 Lips)
knaps,[5,8,9,10,12,13,14],0
% 285,944 inferences, 0,197 CPU in 0,198 seconds (100% CPU, 1448888 Lips)
knaps,[8,9,10,12,13,14,15],0
% 312,936 inferences, 0,217 CPU in 0,217 seconds (100% CPU, 1443891 Lips)
knaps,[10,11,12,14,15,16],0
% 343,612 inferences, 0,238 CPU in 0,238 seconds (100% CPU, 1445670 Lips)
knaps,[12,13,14,15,16,17],0
% 403,782 inferences, 0,277 CPU in 0,278 seconds (100% CPU, 1456345 Lips)
knaps,[11,12,13,15,16,17],0
% 433,078 inferences, 0,298 CPU in 0,298 seconds (100% CPU, 1455607 Lips)
knaps,[14,15,16,17,18,19],0
% 473,792 inferences, 0,326 CPU in 0,327 seconds (100% CPU, 1451672 Lips)
knaps,[14,15,16,17,18,19,20],0
true.

Answer 3

«Правило передовой практики» Пролога гласит, что следует избегать assert / retract, за исключением случаев, когда требуется абсолютно (т. Е. Когда нет декларативного подхода).

Здесь программаиспользуя select / 3 для генерации всех комбинаций

movie(a, 10).
movie(b, 3).
movie(c, 5).
movie(d, 6).
movie(e, 10).

dvdsize(20).

burn(Best) :-
    findall(N-S, movie(N,S), L),
    dvdsize(Max),
    setof(Wasted-Sequence, fitmax(L, Max, Wasted, Sequence), All),
    All = [Best|_],
    maplist(writeln, All).

fitmax(L, AvailableRoom, WastedSpace, [Title|Others]) :-
    select(Title - MovieSize, L, R),
    MovieSize =< AvailableRoom,
    RoomAfterMovie is AvailableRoom - MovieSize,
    fitmax(R, RoomAfterMovie, WastedSpace, Others).

fitmax(_, WastedSpace, WastedSpace, []).

output:

?- burn(X).
0-[a,e]
0-[e,a]
1-[a,b,d]
1-[a,d,b]
1-[b,a,d]
1-[b,d,a]
1-[b,d,e]
1-[b,e,d]
1-[d,a,b]
1-[d,b,a]
1-[d,b,e]
1-[d,e,b]
1-[e,b,d]
1-[e,d,b]
2-[a,b,c]
2-[a,c,b]
2-[b,a,c]
2-[b,c,a]
2-[b,c,e]
2-[b,e,c]
2-[c,a,b]
2-[c,b,a]
2-[c,b,e]
2-[c,e,b]
2-[e,b,c]
2-[e,c,b]
4-[a,d]
4-[d,a]
4-[d,e]
4-[e,d]
5-[a,c]
5-[c,a]
5-[c,e]
5-[e,c]
6-[b,c,d]
6-[b,d,c]
6-[c,b,d]
6-[c,d,b]
6-[d,b,c]
6-[d,c,b]
7-[a,b]
7-[b,a]
7-[b,e]
7-[e,b]
9-[c,d]
9-[d,c]
10-[a]
10-[e]
11-[b,d]
11-[d,b]
12-[b,c]
12-[c,b]
14-[d]
15-[c]
17-[b]
20-[]
X = 0-[a, e].

Answer 4

1. Если вы хотите, чтобы вещи вели себя так, как будто вы продолжали просить другое решение после того, как каждое из них предоставлено, но собираете их все в список, findall - это то, что вам нужно.

2. Если все это происходит в одном запросе, вы можете передать список использованных фильмов.Например, цикл записи возьмёт в качестве аргумента список фильмов, используемых до сих пор;fitfuzzy возьмет этот список и заполнит новую версию фильмами для этого добавленного DVD, и вы передадите этот новый список в burnloop.Или, поскольку на DVD есть новые фильмы, запишите новый предикат, чтобы добавить фильмы на DVD в старый список, чтобы создать новый.

3. Что если вы позволите fitexact продолжать работу так, как онв настоящее время, но также сохраняет список фильмов, которые были ближе всего к размеру DVD, так что вместо того, чтобы потерпеть неудачу, когда не заполняет DVD точно, он возвращает этот список?