2

我的目标是在 Prolog 中实现一个简单的聚类算法。

假设您有一定数量的位置。每个位置都有一个特定的 ID，它们看起来像“位置（X，Y，ID）”。

我有以下想法：基本上，您获取第一个 ID 及其位置，然后将此 ID 添加到列表中。然后，将此 ID 的位置与所有其他可能的位置进行比较。然后，每个位置与原始位置在一定距离内的 ID 也会添加到列表中。下一步是对已添加到列表中的所有新 ID 执行完全相同的操作。然后对上一步中添加的 ID 执行相同的操作，等等。

在没有更多可能性之后，您将拥有一个形成集群的 ID 列表。例如 1、2、3、6 和 8。

对于您从 ID 1 开始的第一个集群。通常，您将从 ID 2 开始并检查该集群是哪个集群。但它已经在第一个集群中，没有理由再看这个。就像我们也不必查看值 3、6 和 8 一样。因为我们只知道查看这些 ID 会给出完全相同的集群。

所以我如何想象有一个谓词返回列表列表，基本上是所有集群。该谓词使用另一个实际生成单个集群的谓词。

我已经尝试了一些东西，但它并没有真正起作用。

可能的位置列表：

position(1,1,1)
position(3,2,2)
position(2,4,3)
position(4,6,4)
position(5,4,5)
position(10,3,6)
position(12,2,7)
position(13,6,8)
position(16,2,9)

假设距离为 3，则应该有四个集群。1、2、3、4和5；6和7；8个；9.

首先是一个简单的谓词，它检查两个 ID 是否在一定距离内：

checkDistance(ID1,ID2,Distance) :-
    position(X1,Y1,ID1),
    position(X2,Y2,ID2),
    abs(X2 - X1) =< Distance,
    abs(Y2 - Y1) =< Distance.

以下代码创建一个接近初始 ID 的 ID 列表：

compareAllPos(ID,Val,[],Distance) :- 
    \+ checkDistance(ID,Val,Distance).

compareAllPos(ID,Val,[Val|LS],Distance) :-
    checkDistance(ID,Val,Distance),
    Val2 is Val+1,
    compareAllPos(ID,Val2,LS,Distance).

它提供以下输出：

?- compareAllPos(1,1,List,3).
List = [1, 2, 3] ;

这仅解决了第一部分。现在我必须检查添加到列表中的每个值。我通过添加另一个 compareAllPos 来做到这一点：

compareAllPos(ID,Val,[Val|LS],Distance) :-
    checkDistance(ID,Val,Distance),
    Val2 is Val+1,
    append(LS1,LS2,LS),
    compareAllPos(Val,1,LS1,Distance),
    compareAllPos(ID,Val2,LS2,Distance).

下一个问题是程序现在陷入无限循环，因此需要检查以确保尚未看到 ID。

我有以下想法：

compareAllPos2(ID,Val,_,[],Distance) :- 
    \+ checkDistance(ID,Val,Distance).

compareAllPos2(ID,_,Visited,[],_) :-
    member(ID,Visited).

compareAllPos2(ID,Val,Visited,[Val|LS],Distance) :-
    checkDistance(ID,Val,Distance),
    Val2 is Val+1,
    append(LS1,LS2,LS),
    append(ID,Visited,Visited1),
    compareAllPos2(Val,1,Visited1,LS1,Distance),
    append([],Visited1,Visited2),
    compareAllPos2(ID,Val2,Visited2,LS2,Distance).

我会使用以下行来调用它：

compareAllPos2(1,1,[],List,3).

这就是我卡住的地方。上面的代码不能正常工作，我还没有找到解决这个问题的正确方法。如果该代码有效，它应该返回一个基于 ID 的单个集群。最后一步是查看其他可能的集群。

4

1 回答 1

2

添加最后一个 compareAllPos/4 后，你会得到

?- compareAllPos(1,1,List,3).
List = [1, 2, 3] ;
List = [1, 2, 3, 1, 2, 3, 4, 5] ;
List = [1, 2, 3, 1, 2, 3, 4, 5] ;
List = [1, 2, 3, 1, 2, 3, 4, 5] ;
List = [1, 2, 3, 1, 2, 3, 4, 5] ;
List = [1, 2, 3, 1, 2, 1, 2, 3, 3|...] ;
List = [1, 2, 3, 1, 2, 1, 2, 3, 3|...] ;
...

我认为可能是循环的原因，你应该让它更简单。我会写

checkDistance(ID1,ID2,Distance) :-
    position(X1,Y1,ID1),
    position(X2,Y2,ID2),
    ID1 \= ID2,
    abs(X2 - X1) =< Distance,
    abs(Y2 - Y1) =< Distance.

clusters(Distance, Cs) :-
    once(position(_,_,First)),
    clusters(Distance, First, [], Cs).

clusters(Distance, Pivot, SoFar, Cs) :-
    findall(Tentative,
        (   pos_not_clustered(SoFar, Tentative),
            checkDistance(Pivot, Tentative, Distance)
        ),
        Cluster),
    Updated = [[Pivot|Cluster]|SoFar],
    (   pos_not_clustered(Updated, NextPivot)
    ->  clusters(Distance, NextPivot, Updated, Cs)
    ;   Cs = Updated
    ).

pos_not_clustered(Clusters, ID) :-
    position(_,_,ID),
    maplist(not_member(ID), Clusters).

not_member(E, L) :- \+ memberchk(E, L).

因为它产生

?- clusters(3,C).
C = [[9], [6, 7, 8], [4, 5], [1, 2, 3]].

编辑抱歉有错误的代码，我已经改成了这个

clusters(Distance, Cs) :-
    once(position(_,_,First)),
    clusters(Distance, [[First]], Cs).

clusters(Distance, SoFar, Cs) :-
    (   pos_not_clustered(SoFar, Tentative),
        add_to_cluster(SoFar, Tentative, Distance, Updated)
    ->  clusters(Distance, Updated, Cs)
    ;   Cs = SoFar
    ).

pos_not_clustered(Clusters, ID) :-
    position(_,_,ID),
    maplist(not_member(ID), Clusters).

not_member(E, L) :- \+ memberchk(E, L).

add_to_cluster([C|Cs], Tentative, Distance, Updated) :-
    member(Id, C),
    checkDistance(Id, Tentative, Distance), !,
    Updated = [[Tentative|C]|Cs].
add_to_cluster([C|Cs], Tentative, Distance, [C|Rs]) :-
    add_to_cluster(Cs, Tentative, Distance, Rs).
add_to_cluster([], Tentative, _Distance, [[Tentative]]).

现在我明白了

?- clusters(3,C).
C = [[5, 4, 3, 2, 1], [8, 7, 6], [9]].
于 2013-04-16T10:09:44.927 回答