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

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)).

这不起作用的原因是因为 subset 不关心我们是否与另一个脱节的元素匹配。即 [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的调用通过回溯将区域中的每个点选取到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]].

查看如何从 Rest 中挑选出 [2,2] 并添加到 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 中的 none 个点与 Region 中的任何点相邻。

编辑

如上所述绝对可行，但稍微修改一下，我们可以得到一个更容易在 Prolog 中实现的算法。它是这样的：

set_region_rest(+Set, -Region, -Rest)

按照术语的标准顺序对点集进行排序；现在你有一个 ordset.
将这个集合拆分成一个 Region 和一个不属于它的 Rest

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

open_set_closed_rest(Open, Set, Closed, Rest)

如果开放集是空的，那么封闭集的其余部分（现在是区域）也是空的；剩下的 Set 就是 Rest。
否则：
- 从Open列表中取出第一对坐标；立马放在Closed坐标前面
- 尝试在坐标集中找到第一对的任何邻居；如果找到任何，将它们附加到开放集的前面；移除邻居后剩下的 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，然后是输出参数。

现在，要将 Set 拆分为一个 Region 和一个 Rest，只要我们在 Open 集中有坐标对，我们就需要继续增长 Region。如果Open set为空，说明我们的Region是完整的，剩下的Set就是Rest:

:- use_module(library(clpfd)).

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

为了找出一个坐标的哪些邻居在 Set 中，我们使用 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]].

Answer 2

这个问题可以看作是union find algorithms的一个实例。这样的算法通常使用一种特殊的数据结构，它基本上服务于以下两个目的：

1) For a point p, find a representant p* 
   in the data structure
2) For two representants p1* and p2* extend 
   the data structure by connecting both

Here 是一个使用线程本地事实的 Prolog 实现 linked/2 作为联合查找数据结构。这是第二个示例运行网格问题：

?- regions(L).
L = [(1, 6),  (4, 2)].

技术说明：Prolog 统一还有一个内置的联合查找组件，如果你提到一个变量 X，它将被取消引用，这是步骤 1)。如果你执行统一 X=Y 并且 X 和 Y 已经取消引用，一个变量将 link 到另一个变量，这是步骤 2).

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

how can I determine that all given coordinates of matrix are connected?

prolog

clpfd

编辑