2

我制作了一个 prolog 程序,向我展示了在 dvd 上安装内容的最佳方式。问题在代码的注释中以供参考,我将在下面粘贴,但归结为:

  1. 是否有一种倒切运算符可以让它搜索更多,尽管它已经匹配?参见 fitexact,类似于 fitexact(Size,Sum,L,L):-Sum

  2. 跟踪已处理电影的最佳方式是什么?我收回它们,但想知道没有它怎么做。

  3. fitfuzzy 使用一个if then构造。我不知道该怎么想他们,在序言中感觉很奇怪。然而,试图使其递归让我非常困惑:)

    % 给出电影和大小的列表,尝试将它们全部放入 dvd
    % 尽可能少地浪费空间。

    % 设置 DVD 大小
    DVD尺寸(4812)。

    数据库中所有电影的百分比总和
    电影大小(大小):- findall(S,电影(_,S),LS),sum_list(LS,大小)。

    数据库中所有电影的百分比
    电影计数(计数):- findall(S,电影(_,S),LS),长度(LS,计数)。

    % 看看哪些完全适合
    %这是我遇到麻烦的地方,最初的想法是
    % 它喜欢下面的模糊搜索,但我不明白我怎么能
    % express '当没有更多适合的电影时,
    % 并且总和小于 dvdsize 列表也可以。
    fitexact(电影):- dvdsize(大小),fitexact(大小,0,[],电影)。

    % 完美契合时停止
    % 所以我在这里尝试了 Size,Sum 和 Sum<Size 。那显然
    % 不起作用,因为它立即匹配。
    fitexact(大小,大小,电影,电影)。
    % 因为否则相同的电影会出现在不同的 DVD 上
    % 认为最好在安装后删除它们。
    %如果我不想这样做,那么确保一次的最佳方法是什么
    % 电影已处理,它不会再次出现?它应该有一个额外的
    % flag like processes(movie(name,size,processed) 或者我应该断言
    % 完成了 dvd,看看它们是否已经在其中?我想知道这个多久
    % all 会采取,因为它已经很慢了。
    %%:-
    %% forall(成员(电影,电影),收回(电影(电影,_)))。%%, !.

    % 否则继续填充
    fitexact(大小、总和、累积、电影):-
      电影(电影,电影大小),
      \+ 成员(电影,Acc),% 没有双打!
      NewSum 是 Sum + MovieSize,
      NewSum =< 大小,
      fitexact(大小,NewSum,[电影|Acc],电影)。

    删除vd(DVD):-
      forall(成员(电影,DVD),撤回(电影(电影,_)))。

    % 做一个模糊拟合,当尺寸减小时尝试精确拟合
    % 没有精确的拟合。
    fitfuzzy(DVD) :- dvdsize(Size), fitfuzzy(DVD,Size,0)。
    fitfuzzy(_,Size,Size) :- movies_size(Size), !.
    fitfuzzy(_,Size,Size) :- dvdsize(Size), !.
    fitfuzzy(DVD,大小,浪费):-
      CheckSize 是大小 - 浪费,
    %这感觉像是一种可怕的方式来做到这一点。我非常喜欢建议
    % 关于如何使其递归或总体上更好。
      ( fitexact(CheckSize, 0, [], DVD)
      -> 删除vd(DVD)
      ; NewWasted 已浪费 + 1,
         write('fitfuzzy: 增加浪费的空间到'), write(NewWasted), nl,
         fitfuzzy(DVD,Size,NewWasted)
      )。

    地位 :-
      电影计数(电影左),
      电影尺寸(电影尺寸),
      write('剩下的电影:'), write(MoviesLeft), nl,
      write('左尺寸:'), write(MoviesSize), nl.

    燃烧循环:-
     电影计数(C),C>0,
     fitfuzzy(DVD),
     地位,
     写('DVD ='),打印(DVD),nl,nl,
     烧环。

    % movies.db 包含一个电影列表(名称,大小)。陈述。它也是
    % 必须有 :- 动态(电影/2)。在顶部缩回工作。
    去 :-
     ['movies.db'],
     烧环。

4

4 回答 4

2

只是一般性评论:我发现不是跟踪处理过的电影,而是首先获取(例如,通过 findall/3)仍然需要处理的电影列表,然后简单地处理这个列表更自然。所以你有burn_dvd(List0, DVD, List),它将一个电影列表(可能结合它们的大小,比如形式的术语movie_size(Name, Size))作为它的第一个参数,构造一个单一的 DVD(通过从 List0 中选择尽可能多的电影放在一张 DVD 上,对于例如在按大小等对列表进行排序后),第三个参数是剩余电影的列表。然后你有一个自然的扩展 burn_dvds(List, DVDs) ,它简单地构造 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 列表作为其答案。

于 2012-04-03T20:28:04.840 回答
1

Prolog 的“最佳实践规则”说,除非绝对需要(即没有声明性方法),否则应避免断言/撤回。

这是一个使用 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, []).

输出:

?- 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].
于 2012-04-03T21:57:35.233 回答
1
  1. 如果您希望事情表现得好像在提供每个解决方案后一直要求另一个解决方案,但是将它们全部收集到一个列表中,findall这就是您想要的。

  2. 如果这一切都发生在一个查询中,您可以传递一个使用过的电影列表。例如,burn loop 会将目前使用的电影列表作为参数;fitfuzzy 将获取该列表并在新版本中添加该 DVD 的电影,然后您将该新列表传递给 burnloop。或者,由于 DVD 中有新电影,因此编写一个新谓词将 DVD 中的电影添加到旧列表中以制作新电影。

  3. 如果您让 fitexact 像现在一样继续进行,但同时保留最接近 DVD 大小的电影列表,这样当 DVD 没有完全填满时,它不会失败,而是生成该列表?

于 2012-04-03T19:54:04.873 回答
1

我之前的回答是“又快又脏”,随着电影数量的增加,很快就会显示出它的局限性。这是找到最佳拟合的更好方法,并与以前的答案进行比较(根据测试要求重新制定)。

标签knapsack建议了优化的关键,Axel 在发布问题时正确使用了该标签。我在 CLP(FD) support 中搜索了解决问题的适当方法,这里是:

:- [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.
于 2012-04-04T16:58:27.237 回答