1

我正在尝试在 Prolog 中运行以下程序。

mama_mia1(A,M,LI,HI,LO,HO,AA) :-
   p1(A,M,LI,HI,LO,HO,PROGS),
   reverse(PROGS,PROG),
   atom_chars(AA,PROG),
   !.

p1(_,_,LO,LO,LO,_,[]).
p1(_,_,HO,HO,_,HO,[]).
p1(_,_,LO,HO,LO,HO,[]).
p1(_,_,X,LO,LO,HO,[]) :- X>LO,X<HO.
p1(_,_,X,HO,LO,HO,[]) :- X>LO,X<HO.
p1(_,_,LO,Y,LO,HO,[]) :- Y>LO,Y<HO.
p1(_,_,HO,Y,LO,HO,[]) :- Y>LO,Y<HO.
p1(_,_,X,Y,LO,HO,[]) :- X>LO,X<HO,Y>LO,Y<HO.
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X1 is X+A,  H1 is HO+1, X1<H1, Y1 is Y+A,  Y1<H1 )
   -> append(PROG1,['A'],PROG),
      p1(A,M,X1,Y1,LO,HO,PROG1)
   ;  false).
p1(A,M,X,Y,LO,HO,PROG) :-
   (  (X2 is X * M,  H1 is HO+1, X2<H1, Y2 is Y * M,  Y2<H1)
   -> append(PROG2,['M'],PROG),
      p1(A,M,X2,Y2,LO,HO,PROG2)
   ;  false).

程序应计算从 li 和 hi 之间的每个数字到 lo 和 ho 之间的结果的适当的加法和乘法路径。加法对应字母 A，乘法对应 M。在程序结束时，我们应该得到对应于我们找到的路径的 As 和 Ms 字符串。

该程序运行良好，但在尝试测试用例时：

mama_mia1(70000,17,2,5,89000,89900,P)

我收到“错误：超出全局堆栈”消息。

任何想法代码有什么问题？

4

2 回答 2

1

该程序运行良好，但...

真的吗？让我们尝试一个最小的案例：

?- p1(1,3,1,1,1,2,P).
   P = []
;  P = "A"
;  *LOOPS*

也就是说，即使在这种非常简单的情况下，您的程序也会循环。然而，它恰好找到了两个答案！第二个答案library(double_quotes)用于打印"A"代替['A'].

在 Prolog 中，你不会只得到一个答案，你可能会得到其中的几个......

直接检测此类非终止问题的简单方法是false在查询中添加目标：

?- p1(1,3,1,1,1,2,P),假的。
   *循环*

我们可以将更多此类目标添加false到您的计划中。严格来说，这只有在您的程序是纯粹的、单调的程序时才有可能。您正在使用 cut 和 if-then-else 在一般情况下它们都会破坏这些属性。但是，在您的情况下，它们可以在以下

p1(_,_,LO,LO,LO,_,[]) :-假。
p1(_,_,HO,HO,_,HO,[]) :-假。
p1(_,_,LO,HO,LO,HO,[]) :-假。
p1(_,_,X,LO,LO,HO,[]) :- false , X>LO,X<HO。
p1(_,_,X,HO,LO,HO,[]) :- false , X>LO,X<HO。
p1(_,_,LO,Y,LO,HO,[]) :- false , Y>LO,Y<HO。
p1(_,_,HO,Y,LO,HO,[]) :- false , Y>LO,Y<HO。
p1(_,_,X,Y,LO,HO,[]) :- false , X>LO,X<HO,Y>LO,Y<HO。
p1（A，M，X，Y，LO，HO，PROG）：-
   （（X1 是 X+A，H1 是 HO+1，X1<H1，Y1 是 Y+A，Y1<H1）
   -> 附加（PROG1，['A']，PROG），假，
       p1（A，M，X1，Y1，LO，HO，PROG1）
   ; 错误的 ）。
p1(A,M,X,Y,LO,HO,PROG) :- false ,
    ( (X2 是 X * M, H1 是 HO+1, X2<H1, Y2 是 Y * M, Y2<H1) 
   ->附加（PROG2，['M']，PROG），
       p1（A，M，X2，Y2，LO，HO，PROG2）
   ；假）。

考虑这个目标append(PROG1,['A'],PROG)。该变量PROG1第一次出现在这里，因此它永远不会被实例化。也PROG没有实例化。因此，这个目标将循环。

替换append(PROG1,['A'],PROG)为PROG = ['A'|PROG1]。现在元素以相反的方向出现，因此不需要反转。

查询mama_mia1(70000,17,2,5,89000,89900,P)现在就像false做的那样简单地失败了。

于 2019-02-12T21:41:23.373 回答
0

这

错误：超出全局堆栈

消息意味着您的程序需要更多内存。要么它卡在某个消耗所有内存的无限循环中，要么它没有任何问题并且输入太大，因此需要更多内存。

考虑到您的输入看起来很大并且假设您已经测试了较小的输入并且没有发生问题，我会说您只需要更多内存

您可以扩展堆栈的大小，或者您可以尝试使用更少的内存。

当然，如果这是在某处提交以进行检查的某种练习，那么您可以获得多少内存可能会受到限制：b

于 2011-07-21T18:07:07.613 回答