prolog - 如何确定矩阵的所有给定坐标都已连接？

Question

给定一个网格，我如何确定网格的元素是否全部在单个区域中？在下面的情况下是正确的，因为矩阵中的每个元素都有一个邻居。

范例1：

gridneighbours([[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[4,1],[4,2]]).
true.

但是在我的第二个示例Example2中：

gridneighbours([[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[3,1],[4,1],[4,2]]).
false.

这是错误的，因为[3,1]，[4,1]，[4,2]与前面的元素不相交。
最初，我尝试使用Prolog中的子集通过简单地从X或Y中添加或减去来检查相邻元素之间的现有元素，但这不起作用，因为拆分区域中的元素会彼此相邻。同样，对角线不算作彼此相邻。

更新，添加了代码：
这是我得到的：

%Check right
neighbourcheck([X,Y|_],S) :- X1 is X + 1, subset([[X1,Y]],S).
%Check left
neighbourcheck([X,Y|_],S) :- X1 is X - 1, subset([[X1,Y]],S).
%Check Up
neighbourcheck([X,Y|_],S) :- Y1 is Y + 1, subset([[X,Y1]],S).
%Check Down
neighbourcheck([X,Y|_],S) :- Y1 is Y - 1, subset([[X,Y1]],S).
% Iterate through all sublists and check for neighbours
gridneighbour(S) :- forall(member(X,S), neighbourcheck(X,S)).

之所以不起作用，是因为子集不在乎我们是否与另一个不相交的元素匹配。即[3,1]与[4,1]匹配。
运行此代码并使用上面的示例给出：


范例1：正确
例2：是（显然，这应该是假的，因为[3,1]，[4,1]和[4,2]是分开的）。

Answer 1

可行的简单方法概述如下：


从两组点（列表？）开始：您知道的点属于一个区域Region，其余的点属于Rest。开始时，您可以选择属于Region的任何单个点，而Rest中剩余的所有点。
在Rest中寻找与Region中任意点相邻的点。


如果找到邻居，请将其从Rest移至Region并重复
如果找不到邻居，就停下来

如果结尾的Rest中有点，则这不是区域。


这是定义neighbors/2的更简单方法：

neighbors([X1,Y1], [X2,Y2]) :-
    abs(X1-X2) + abs(Y1-Y2) =:= 1.

您可以通过简单地尝试每种可能的组合来在一个列表中查找与另一个列表中的点相邻的点：

% add_to_region(+Region0, +Rest0, -Region, -Rest)
%% Look in Rest0 for a neighbor to Region0;
%% Region is Region0 with the neighbor,
%% Rest is Rest0 without it
add_to_region(Region, Rest0, [B|Region], Rest) :-
    member(A, Region),
    select(B, Rest0, Rest),
    neighbors(A, B).

对member / 2的调用通过回溯来选择Region到A的每个点。对select / 3的调用将在Rest0到B中选取每个点，并在Rest中选取其余的点。如果两个点是邻居，则将B添加到Region的前面。

如果 Rest中的当前区域没有更多邻居，则此操作将失败，如果存在，则至少成功一次。您可能要使用 once(add_to_region(Region0, Rest0, Region, Rest))进行调用，这样就不会有不必要的选择点。使用您的示例：

?- once(
      add_to_region(
         [[1,1],[1,2],[1,3],[2,1]],
         [[2,2],[2,3],[3,1],[4,1],[4,2]],
         Region, Rest)).
Region = [[2, 2], [1, 1], [1, 2], [1, 3], [2, 1]],
Rest = [[2, 3], [3, 1], [4, 1], [4, 2]].

查看如何从 [2,2]中拾取 Rest并将其添加到 Region。

?- add_to_region(
   [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]],
   [[3,1],[4,1],[4,2]],
   Region, Rest).
false.

之所以失败，是因为 Rest中的任何点都不是 Region中的任何点的邻居。

编辑

正如上面所解释的，绝对是可行的，但是稍加修改，我们就可以拥有一种在Prolog中更容易实现的算法。它是这样的：

set_region_rest(+Set, -Region, -Rest)


按标准术语顺序对点集进行排序；现在您有一个 ordset。
将此集拆分为一个Region和一个不属于它的Rest


为了进行拆分，我们将保留一个额外的列表。我们将其称为Open节点列表：尚未探索的节点。首先，输入列表的第一个元素是唯一的打开节点。
其余元素按原样传递。
最后两个参数Region和Rest是输出参数。

open_set_closed_rest(Open, Set, Closed, Rest)


如果开放集为空，则其余封闭集（现在为Region）也为空；剩下的集合就是剩下的。
除此以外：


从“打开”列表中获取第一对坐标；立即将其放在“封闭”坐标的前面。
尝试在座标集中找到这对第一对的任何邻居；如果找到任何内容，请将其附加到Open set的前面；删除邻居后，其余Set是新的Set。
使用新的开放集，其余的封闭集，其余的集和其余部分再试一次。



为此，在Prolog中，我将首先清理坐标表示。
它们出现在两个列表中有点令人讨厌：如果我们使用例如一对代替 [X,Y] ---> X-Y，则写作要少得多。为此，我添加以下谓词：

xy(XY) :-
        coordinates(C),
        maplist([[X,Y], X-Y]>>true, C, XY).
xy([1-1,1-3,1-2]).
xy([1-2,2-1,2-2]).
xy([1-1, 1-2, 1-3, 1-4, 1-5,
    2-1,                2-5,
    3-1,                3-5,
    4-1,                4-5,
    5-1, 5-2, 5-3, 5-4, 5-5]).
xy([1-1, 1-2, 1-3, 1-4, 1-5,
    2-1,                2-5,
    3-1,      3-3,      3-5,
    4-1,                4-5,
    5-1, 5-2, 5-3, 5-4, 5-5]).

coordinates([[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[4,1],[4,2]]).
coordinates([[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[3,1],[4,1],[4,2]]).

（我还放置了4个额外的测试集！）

因此，我得到：

?- xy(XY).
XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, ... - ...] [write] % press 'w' here
XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, 4-2] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 3-1, 4-1, 4-2] ;
XY = [1-1, 1-3, 1-2] ;
XY = [1-2, 2-1, 2-2] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-3, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5].

这是尝试用代码编写以上算法的方法：

set_region_rest([A|As], Region, Rest) :-
        sort([A|As], [B|Bs]),
        open_set_closed_rest([B], Bs, Region, Rest).

这只是对输入Set进行排序，并从中分离出第一个元素。
第一个元素是Open集中的第一个坐标对，其余元素是Set，然后是输出参数。

现在，要将集合分为一个区域和一个休息区，只要在开放集中具有坐标对，就需要继续扩大区域。如果“开放集”为空，则表示我们的“区域”是完整的，其余集合为“其余”：

:- use_module(library(clpfd)).

open_set_closed_rest([], Rest, [], Rest).

为了找出坐标集中的哪些邻居，我们使用 ord_intersection/4，它同时为我们提供了Set中的邻居以及Set的其余部分。

注意：列出的4个邻居坐标已排序！

open_set_closed_rest([X-Y|As], Set, [X-Y|Closed0], Rest) :-
        X0 #= X-1, X1 #= X + 1,
        Y0 #= Y-1, Y1 #= Y + 1,
        ord_intersection([X0-Y,X-Y0,X-Y1,X1-Y], Set, New, Set0),
        append(New, As, Open),
        open_set_closed_rest(Open, Set0, Closed0, Rest).

就是这个。这样，我得到以下6个解决方案：

?- xy(XY), set_region_rest(XY, Region, Rest).
XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, 4-2],
Region = [1-1, 1-2, 1-3, 2-3, 2-2, 2-1, 3-1, 4-1, 4-2],
Rest = [] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 3-1, 4-1, 4-2],
Region = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6],
Rest = [3-1, 4-1, 4-2] ;
XY = [1-1, 1-3, 1-2],
Region = [1-1, 1-2, 1-3],
Rest = [] ;
XY = [1-2, 2-1, 2-2],
Region = [1-2, 2-2, 2-1],
Rest = [] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5],
Region = [1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5, 5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1],
Rest = [] ;
XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-3, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5],
Region = [1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5, 5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1],
Rest = [3-3].

顺便说一句，使用 set_region_rest/3作为构建基块，我们可以轻松地将一组坐标拆分为多个区域：

set_regions([], []).
set_regions([X|Xs], [R|Rs]) :-
        set_region_rest([X|Xs], R, Rest),
        set_regions(Rest, Rs).

所以现在：

?- set_regions([1-1, 1-2, 1-3, 1-4, 1-5,      1-7,
                2-1,                2-5,      2-7,
                3-1,      3-3,      3-5,      3-7,
                4-1,                4-5,
                5-1, 5-2, 5-3, 5-4, 5-5,      5-7], R).
R = [[1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5,
      5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1],
     [1-7, 2-7, 3-7],
     [3-3],
     [5-7]].