我花了很长时间想知道为什么它不能解决一个单一的解决方案,而不查看链接的图片或您的代码,并且没有意识到所有高分都有给定的值。:-|
您的代码last[thompson].
可能应该last(thompson).
表示“汤普森是一个姓氏”,但是如果不构建所有有效姓氏的列表,就很难从中获得任何有用的东西。从那里您也可以将有效的姓氏放入列表中。
我选择了一个复合词bowler(Firstname, Lastname, Highscore, Points)
作为我想看到的输出,所以我列出了Bowlers
其中的五个。然后添加线索信息以解决暴力搜索样式中的值,其工作方式如下:
% Mr. Smith’s high score was three pins higher than that of the bowler with 30 points.
member(bowler(_, smith, Hsmith, _), Bowlers),
member(bowler(_, _, H_30, 30), Bowlers),
Hsmith is H_30 + 3,
说“只有当有一个 Bowlers 的成员匹配 smith 作为他们的姓氏并为 smith 匹配了一些高分,而另一个成员匹配了 30 分并为他们得分,并且两个得分变量相差 3 分时,才能找到解决方案。” 在全:
:- use_module(library(dif)).
solve(Bowlers) :-
% bowler(Firstname, Lastname, Highscore, Points).
Bowlers = [ bowler(frank, L1, H1, P1),
bowler(michael, L2, H2, P2),
bowler(steven, L3, H3, P3),
bowler(craig, L4, H4, P4),
bowler(walter, L5, H5, P5) ],
% everyone has last names from the text
permutation([L1, L2, L3, L4, L5], [smith, stewart, williams, thompson, lewis]),
% apparently the scores are evenly distributed one per person, no dupes.
permutation([P1, P2, P3, P4, P5], [28, 30, 32, 34, 36]),
% the valid high scores, one per person, no dupes.
permutation([H1, H2, H3, H4, H5], [264, 288, 276, 273, 285]),
% Frank, whose last name wasn’t Thompson,
% had the highest score (288) but he didn’t win the tournament (didn't score 36 points).
member(bowler(frank, Lfrank, 288, Pfrank), Bowlers),
dif(Lfrank, thompson),
dif(Pfrank, 36),
% Mr. Smith’s high score was three pins higher than that of the bowler with 30 points.
member(bowler(_, smith, Hsmith, _), Bowlers),
member(bowler(_, _, H_30, 30), Bowlers),
Hsmith is H_30 + 3,
% Steven’s last name wasn’t Stewart
member(bowler(steven, Ssteven, _, _), Bowlers),
dif(Ssteven, stewart),
% The winner of the tournament, who had 36 points, had an odd number for a high score.
member(bowler(_, _, Hwin, 36), Bowlers),
1 is Hwin /\ 1,
% Michael finished the tournament with six points less than Mr. Williams.
member(bowler(michael, _, _, Pmichael), Bowlers),
member(bowler(_, williams, _, Pwilliams), Bowlers),
Pmichael is Pwilliams - 6,
% The bowler with a high score of 273 had two points more than Mr. Smith but two points less than Craig.
member(bowler(_, _, 273, P_273), Bowlers),
member(bowler(_, smith, _, Psmith), Bowlers),
member(bowler(craig, _, _, Pcraig), Bowlers),
P_273 is Psmith + 2,
P_273 is Pcraig - 2,
% Mr. Thompson won fewer points than Walter but more than Steven Lewis.
member(bowler(_, thompson, _, Pthompson), Bowlers),
member(bowler(walter, _, _, Pwalter), Bowlers),
member(bowler(steven, lewis, _, Plewis), Bowlers),
Pthompson < Pwalter,
Pthompson > Plewis.
这感觉很慢,要解决 1000 万个推理,还有 1700 万个要排除任何其他解决方案:
?- time(solve(B)).
10,099,024 inferences, 1.550 CPU in 1.550 seconds (100% CPU, 6517307 Lips)
B = [bowler(frank, williams, 288, 34), bowler(michael, smith, 276, 28), bowler(steven, lewis, 273, 30), bowler(craig, thompson, 264, 32), bowler(walter, stewart, 285, 36)]
1.550 seconds cpu time
17,191,884 inferences, 2.613 CPU in 2.613 seconds (100% CPU, 6579160 Lips)
false
它从代码顶部向下搜索,生成一个名称排列,一个点,一个分数,然后检查frank
没有得到thompson
他的姓氏,回溯并再次尝试,直到它生成一个通过所有检查的解决方案。
通过重新排序子句以更快地失败,从而减少失败前的工作,并从文本中添加更多提示,可以减少工作量。例如,从最后一条线索我们知道一个成员肯定是 Steven Smith,我们知道 Frank 的分数是 288,我们可以直接写“Mr Smiths 的分数比……高 3 针”,得到这个版本:
:- use_module(library(dif)).
solve(Bowlers) :-
% bowler(Firstname, Lastname, Highscore, Points).
Bowlers = [ bowler(frank, L1, 288, P1),
bowler(michael, L2, H2, P2),
bowler(steven, lewis, H3, P3),
bowler(craig, L4, H4, P4),
bowler(walter, L5, H5, P5) ],
dif(L1, thompson), % Frank, whose last name wasn’t Thompson
dif(P1, 36), % didn’t win (didn't score 36 points).
dif(L5, thompson), % Walter isn't Mr Thompson because they scored differently.
dif(L4, smith), % Craig isn't Mr Smith because they scored differently.
dif(L2, williams), % Michael isn't Mr Williams because they scored differently.
% everyone has last names from the text
permutation([L1, L2, L4, L5], [smith, stewart, williams, thompson]),
% scores are evenly distributed one per person, no dupes.
permutation([P1, P2, P3, P4, P5], [28, 30, 32, 34, 36]),
% Michael finished the tournament with six points less than Mr. Williams.
member(bowler(_, williams, _, Pwilliams), Bowlers),
P2 is Pwilliams - 6,
% the valid high scores, one per person, no dupes.
permutation([H2, H3, H4, H5], [264, 276, 273, 285]),
% The winner of the tournament, who had 36 points, had an odd number for a high score.
member(bowler(_, _, Hwin, 36), Bowlers),
1 is rem(Hwin, 2),
% Mr. Smith’s high score was three pins higher than that of the bowler with 30 points.
member(bowler(_, _, H_30, 30), Bowlers),
Hsmith is H_30 + 3,
member(bowler(_, smith, Hsmith, Psmith), Bowlers),
% The bowler with a high score of 273 had two points more than Mr. Smith but two points less than Craig.
P_273 is Psmith + 2,
member(bowler(_, _, 273, P_273), Bowlers),
Pcraig is P_273 + 2,
member(bowler(craig, _, _, Pcraig), Bowlers),
% Mr. Thompson won fewer points than Walter but more than Steven Lewis.
member(bowler(_, thompson, _, Pthompson), Bowlers),
member(bowler(walter, _, _, Pwalter), Bowlers),
Pthompson < Pwalter,
member(bowler(steven, lewis, _, Plewis), Bowlers),
Pthompson > Plewis.
这个版本可以:
?- time(solve(B)).
34,664 inferences, 0.007 CPU in 0.007 seconds (100% CPU, 5150062 Lips)
B = [bowler(frank, williams, 288, 34), bowler(michael, smith, 276, 28), bowler(steven, lewis, 273, 30), bowler(craig, thompson, 264, 32), bowler(walter, stewart, 285, 36)]
26,321 inferences, 0.011 CPU in 0.011 seconds (100% CPU, 2397565 Lips)
false
快了近 300 倍。