在一个列表的列表中查找形状

Question

在一个列表的列表中查找形状

5

程序描述

程序目的

我的程序旨在计算20X15大小平面上形状的位置。我有一个形状列表，其中包含形状类型、其ID、其半径或高度以及其在平面上的潜在[X，Y]位置。我有一个不同的二进制操作列表，仅包含形状类型、其ID以及其与另一个形状的位置关系。根据操作列表中的信息，我应该计算出形状的[X，Y]位置。以下是这两个列表的描述：

形状列表

我有一个形状列表：每个形状都是以下形式的列表：

[[形状，ID]，高度/半径，[X，Y]]

当Prolog打印出这样的一组形状时，其列表可能如下所示：

[[[diamond,1],4,[_7948,_7954]],[[circle,3],6,[_7894,_7900]],[[square,1],4,[_7840,_7846]],[[circle,1],5,[_7786,_7792]]|_7800]

操作列表

应对形状执行的操作列表，每个操作的格式如下：

[[[circle,1],below,[square,1]]]

这意味着圆形1应该出现在X,Y平面上方形1的下方。

当Prolog打印出这样的列表时，它看起来像以下内容：

[[[circle,1],below,[square,1]]|_8016]

程序

我有一个名为 computeShapeLocations/2 的程序。它的第一个参数是一个操作列表，第二个参数是一个形状列表。它递归地遍历操作列表，获取操作两侧的形状 ID。例如 circle 1 - below - sqaure 1，并将这两个形状发送到正确的函数中，使用 CLPFD 计算位置。对于相对定位为“below”的两个形状，我使用 computeShapesBelow/2，它接受两个形状，每个形状的形式为 [[shape, id],height/radius, [X,Y]]。

computeShapeLocations/2 中的步骤： 1. 从操作列表中获取形如 [[[circle,1],below,[square,1]]] 的操作 2. 获取第一个 ID（circle 1），然后是关系类型（below），最后是第二个 ID（square 1） 3. 从形状列表（ShapesOut）中获取形状 4. 将形状发送到 computeShapesBelow/2。这只是使用 CLPFD 比较半径或高度以及我的 X、Y 平面的尺寸。

:- use_module(library(clpfd)).
computeShapeLocations([],_ShapesOut).
computeShapeLocations([Operation|Rest],ShapesOut) :- writeln(ShapesOut),                                                                             
                                      writeln([Operation|Rest]),                                                                             
                                      nth0(0,Operation,Subject1),                                                                            
                                      nth0(1,Operation,below),                                                                           
                                     nth0(2,Operation,Subject2),                                                                             
                                     Shape1 = [Subject1,H,Loc],                                                                          
                                     Shape2 = [Subject2,H2,Loc2],                                                                        
                                     member(Shape1,ShapesOut),
                                     member(Shape2,ShapesOut),                                                                  
                                     writeln(Shape1),                                                                            
                                     writeln(Shape2),                                                            
                                     writeln(Subject1),                                                                          
                                      writeln(Subject2),
                                     computeShapeBelow(Shape1,Shape2),                                       
                                  computeShapeLocations(Rest,ShapesOut).
computeShapeBelow(Shape1,Shape2) :- nth0(2,Shape1,Location1),                                    
                                    nth0(2,Shape2,Location2),                                                                            
                                    writeln(Shape1),                                                                             
                                    writeln(Shape2),                                                                             
                                   nth0(1,Shape1,Dim1),                                                                          
                                   nth0(1,Shape2,Dim2),                                                                          
                                   nth0(0,Location1,Xcord1),                                                                             
                                   nth0(0,Location2,Xcord2),                                                                          
                                  nth0(1,Location1,Ycord1),                                                                          
                                  nth0(1,Location2,Ycord2),                                                                       
                                  Ycord1 #> Dim1, Ycord1 #< 15-Dim1,                                                                          
                                  Xcord1 #> Dim1, Xcord1 #< 20-Dim1,                                                                          
                                  Ycord2 #> Dim2, Ycord2 #<  15-Dim2,                                                                         
                                  Xcord2 #> Dim2, Xcord2 #<  20-Dim2,                                                                         
                                  Ycord2 #> Ycord1+Dim2+Dim1.

问题： 在computeShapeLocations/2中，我的查找方式非常奇怪（请参见上述步骤三中的computeShapeLocations/2步骤）。我使用member(ShapeId, ListOFshapesList)根据id从listofshapes中获取形状[shape,id]。然后我打印出结果（writeln(Shape1), writeln(Shape2)），下面的图像显示了行为错误的情况。对于第一个形状（圆形，1），结果是好的，computeShapesBelow/2甚至能够得出其X、Y位置的正确限制（6..14和6..9）。对于第二个形状（Shape2或正方形1），它的行为不符合预期，clpfd限制导致较低的无穷大。

由于第二次搜索[square,1]忽略了列表中的一个条目[[square, 1], 4, [_2166, _2172]]，而是不知何故添加了额外的[[square, 1], _2250, [_2262|...]]，这导致了我的结果混乱。

- Gakuo

由于我正在查找形状列表中的形状，每个形状的格式为[[circle, id]，半径，[X坐标，Y坐标]]，我想匹配部分[circle，id]，如果该部分匹配，则要获取整个形状结构 –> –[[circle，id]，半径，[X坐标，Y坐标]]。 - Gakuo

我已经仔细阅读了您的问题几遍。涉及到“ShapesIn”和“ShapesOut”的查询具体是什么意思还不太清楚。您并没有说出“shape_lookup/3”实际行为的期望。为什么它有三个参数？如果我在形状列表“Shapes”中查找一个形状“S”，那么只需要使用“shape_lookup(S, Shapes)”，除非您希望第三个参数代表其他内容。 - lurker

我已经彻底解释了问题并附上了输出。 - Gakuo

Prolog因为你使用了列表内部表示并依赖于nth0/3而对你进行惩罚。 - Daniel Lyons

嗯，我该怎么改写它呢？ - Gakuo

显示剩余10条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Lyons · Accepted Answer

我认为，你的问题源于两个简单的问题。我没有你的所有代码，也不知道你想做什么，所以我只能讲述我看到的并说明我会如何继续。

第一个问题是你没有有效地使用统一。例如，你可以用以下方式替换：

nth0(0,Operation,Subject1),
nth0(1,Operation,below),
nth0(2,Operation,Subject2),

使用这个：

[Subject1,below,Subject2] = Operation,

而且，你实际上不需要单独使用Operation，所以你可以将它移到从句的头部：

computeShapeLocations([[Subject1,below,Subject2]|Rest],ShapesOut) :-

当您开始进行这些更改时，您的代码将会变得更加简洁，只需通过代码就可以轻松地看出发生了什么。如果使用较少的列表表示形式，将会使理解变得更加容易。例如，在此命令列表中，我更容易理解正在发生的情况：

[below(circle(1), square(1)), below(circle(2), square(1)), ...]

甚至可以通过添加:- op声明来实现这一点：

[circle(1) below square(1), circle(2) below square(1), ...]

然后您的模式匹配将变得更加简单，例如：

compute(Shape1 below Shape2) :- ...

同样地，对于您的形状，如果您有更多的结构，那么理解正在发生的事情会更容易一些：

shape(circle(1), 4, X@Y)

比起其他内容，对我来说这个略显明显。

[[circle,1], 4, [X,Y]]

我觉得在输入列表中有未绑定的变量有点奇怪。我猜你希望它们后面会获得值。我想这种方法没有问题，但是我很惊讶地看到了一个混合了ground和nonground作为输入的列表。

你的第二个问题是你混合了几种不同的过程。我很确定你正在进行DCG解析步骤。通过解析成这种弱的列表表示形式，你迫使自己在这些方法内部做更多的工作，去分解你的列表并获取它们的含义。考虑一下：

command([Shape1,below,Shape2]) --> shape(Shape1), "below", shape(Shape2).

对比

command(Shape1 below Shape2) --> shape(Shape1), "below", shape(2).

或者，

shape_type(circle) --> "circle".  shape_type(square) --> "square".
shape_name(shape(Name, Size, X@Y)) --> 
    shape_type(T), integer(ID), 
    integer(Size), 
    integer(X), integer(Y), 
    { Name =.. [T, ID] }.

与你现在拥有的相比。

也就是说，在解析期间创建结构将简化处理过程。同样，进行大量看起来像调试I/O的操作会使处理过程更加复杂。

find_shape(ShapeId, Shapes, Shape) :-
    Shape = shape(ShapeId, _, _),
    member(Shape, Shapes).

computeShapeLocations([], _).
computeShapeLocations([ShapeId1 below ShapeId2|Rest], Shapes) :-
    find_shape(ShapeId1, Shapes, Shape1),
    find_shape(ShapeId2, Shapes, Shape2),
    computeShapeBelow(Shape1, Shape2),
    computeShapeLocations(Rest, Shapes).

computeShapeBelow(shape(_, D1, X1@Y1), shape(_, D2, X2@Y2)) :-
    Y1 #> D1, Y1 #< 15 - D1,
    X1 #> D1, X1 #< 20 - D1,
    Y2 #> D2, Y2 #< 15 - D2,
    X2 #> D2, X2 #< 20 - D2,
    Y2 #> Y1 + D2 + D1.

我认为如果我盯着这个看，调试会更容易一些。