我怎样才能计算递归规则的递归次数？(How could I calculate the number of recursions that a recursive rule does?)

编程入门行业动态更新时间:2024-10-28 18:24:22

我处理一个问题; 我想计算一下我的代码递归规则的递归次数。

我的程序检查对象是否是计算机硬件的组件（通过组件（X，Y）谓词）.Eg组件（计算机，主板） - > true。

它甚至检查了一个对象不是直接组件而是另一个组件的子组件的情况。例如子组件（计算机，ram） - > true。（因为ram是主板的组件，主板是计算机的组件）

因为我的代码超过了400行，所以我将只给出表单组件（X，Y）和规则子组件（X，Y）的一些谓词。

所以，一些谓词如下：

component(computer,case). component(computer,power_supply). component(computer,motherboard). component(computer,storage_devices). component(computer,expansion_cards). component(case,buttons). component(case,fans). component(case,ribbon_cables). component(case,cables). component(motherboard,cpu). component(motherboard,chipset). component(motherboard,ram). component(motherboard,rom). component(motherboard,heat_sink). component(cpu,chip_carrier). component(cpu,signal_pins). component(cpu,control_pins). component(cpu,voltage_pins). component(cpu,capacitors). component(cpu,resistors).

等等....

我的规则是：

subcomponent(X,Z):- component(X,Z). subcomponent(X,Z):- component(X,Y),subcomponent(Y,Z).

好吧，为了计算给定组件Y给定组件Y的组件数量 - 即递归规则子组件（X，Y）的递归次数，我做了一些失败的尝试。但是，我在下面介绍它们：

一世）

number_of_components(X,Y,N,T):- T is N+1, subcomponent(X,Y). number_of_components(X,Y,N,T):- M is N+1, subcomponent(X,Z), number_of_components(Z,Y,M,T).

在这种情况下，我收到此错误：“错误：是/ 2：参数未充分实例化”。

II）

number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L), length(L,N), write(N).

在这种情况下，我得到的结果是1或11，并且在此数字之后为真，这就是全部。完全没有逻辑！

三）

count_elems_acc([], Total, Total). count_elems_acc([Head|Tail], Sum, Total) :- Count is Sum + 1, count_elems_acc(Tail, Count, Total). number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L), count_elems_acc(L,0,Total), write(Total).

在这种情况下，我得到的结果数字根据我的知识基础不正确。（或者我误解了它们 - 因为这种方式似乎有一些逻辑）

那么，我做错了什么，我该怎么写呢？

我期待着阅读你的答案！

I deal with a problem; I want to calculate how many recursions a recursive rule of my code does.

My program examines whether an object is component of a computer hardware or not(through component(X,Y) predicate).E.g component(computer,motherboard) -> true.

It does even examine the case an object is not directly component but subcomponent of another component. E.g. subcomponent(computer,ram) -> true. (as ram is component of motherboard and motherboard is component of computer)

Because my code is over 400 lines I will present you just some predicates of the form component(X,Y) and the rule subcomponent(X,Y).

So, some predicates are below:

and so on....

My rule is:

subcomponent(X,Z):- component(X,Z). subcomponent(X,Z):- component(X,Y),subcomponent(Y,Z).

Well, in order to calculate the number of components that a given component X to a given component Y has-that is the number of recursions that the recursive rule subcomponents(X,Y), I have made some attempts that failed. However, I present them below:

number_of_components(X,Y,N,T):- T is N+1, subcomponent(X,Y). number_of_components(X,Y,N,T):- M is N+1, subcomponent(X,Z), number_of_components(Z,Y,M,T).

In this case I get this error: "ERROR: is/2: Arguments are not sufficiently instantiated".

ii)

number_of_components(X,Y):- bagof(Y,subcomponent(X,Y),L), length(L,N), write(N).

In this case I get as a result either 1 or 11 and after this number true and that's all. No logic at all!

iii)

In this case I get as results numbers which are not right according to my knowledge base.(or I mistranslate them-because this way seems to have some logic)

So, what am I doing wrong and what should I write instead?

I am looking forward to reading your answers!

最满意答案

您可以做的一件事是使用call_with_depth_limit/3迭代加深。您调用谓词（在本例中为subcomponent/2 ）。在获得结果之前增加限制，如果得到结果，则限制是使用的最深递归级别。您可以看到相关文档。

但是，您可以更轻松地完成任务。您的数据库可以表示为未加权，有向，非循环图。因此，将整个数据库粘贴在有向图中，如在库（ugraphs）中实现的那样，并找到它的传递闭包。在传递闭包中，组件的邻居都是其子组件。完成！

制作图表：

findall(C-S, component(C, S), Es), vertices_edges_to_ugraph([], Es, Graph)

要找到传递闭包：

transitive_closure(Graph, Closure)

并找到子组件：

neighbours(Component, Closure, Subcomponents)

Subcomponents将是一个列表，您可以获得长度为length/2 。

编辑

一些随机的想法：在你的情况下，你的数据库似乎描述了一个定义既定向又非循环的图形（组件 - 子组件关系严格按照一种方式，对吧？）。这就是没有必要在图表中定义自己的步骤，例如在这个伟大的问题和答案中很好地证明了这一点。因此，您不需要定义自己的递归subcomponent谓词等。

将数据库表示为使用它时的术语而不是将其保持为平面表是一件好事，就是编写操纵它的谓词变得微不足道：你可以免费获得Prolog的回溯。而且，由于库（ugraph）使用的图形的S表示非常适合Prolog，因此您最有可能最终获得更高效的程序。

One thing you could do is iterative deepening with call_with_depth_limit/3. You call your predicate (in this case, subcomponent/2). You increase the limit until you get a result, and if you get a result, the limit is the deepest recursion level used. You can see the documentation for this.

However, there is something easier you can do. Your database can be represented as an unweighted, directed, acyclic graph. So, stick your whole database in a directed graph, as implemented in library(ugraphs), and find its transitive closure. In the transitive closure, the neighbours of a component are all its subcomponents. Done!

To make the graph:

findall(C-S, component(C, S), Es), vertices_edges_to_ugraph([], Es, Graph)

To find the transitive closure:

transitive_closure(Graph, Closure)

And to find subcomponents:

neighbours(Component, Closure, Subcomponents)

The Subcomponents will be a list, and you can just get its length with length/2.

EDIT

Some random thoughts: in your case, your database seems to describe a graph that is by definition both directed and acyclic (the component-subcomponent relationship goes strictly one way, right?). This is what makes it unnecessary to define your own walk through the graph, as for example nicely demonstrated in this great question and answers. So, you don't need to define your own recursive subcomponent predicate, etc.

One great thing about representing the database as a term when working with it, instead of keeping it as a flat table, is that it becomes trivial to write predicates that manipulate it: you get Prolog's backtracking for free. And since the S-representation of a graph that library(ugraph) uses is well-suited for Prolog, you most probably end up with a more efficient program, too.

更多推荐

本文发布于:2023-07-27 14:03:00，感谢您对本站的认可！

本文链接:https://www.elefans.com/category/jswz/34/1291469.html