如何确定矩阵的所有给定坐标都已连接? [英] how can I determine that all given coordinates of matrix are connected?
问题描述
给定一个网格，我如何确定网格的元素是否都在一个区域中.在下面的情况下是正确的，因为矩阵中的每个元素都有一个邻居.
Given a grid how can I determine if elements of a grid are all in a single region. In the below case is true because each element in the matrix has a neighbor.
示例 1:
gridneighbours([[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[4,1],[4,2]]).
true.
但是在我的第二个示例中，示例 2:
However in my second example, 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 中添加或减去来检查另一个相邻的现有元素，但是这不起作用，因为分割区域的元素将彼此相邻.对角线也不算是彼此相邻.
This is false because [3,1],[4,1],[4,2] are disjoint to the previous elements. Initially I tried using subset from Prolog to check for an existing element next to another by simply adding or subtracting from X or Y, however this doesn't work because elements of a split region would be next to each other. Also diagonals don't count as being next to each other.
更新，添加代码:这是我得到的:
Updated, added code: Here is what I got:
%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] 匹配.运行此代码并使用上面的示例给出:
The reason why this doesn't work is because subset doesn't care if we have a match up with another element that is disjointed. i.e. [3,1] matches up with [4,1]. Running this code and using the examples above give:
- 示例 1:正确
- 示例 2:真(显然这应该是假的，因为 [3,1]、[4,1] 和 [4,2] 是分开的).
推荐答案
一个简单有效的方法可以概括如下:
A naive approach that works can be outlined as follows:
- 从两组(列表?)点开始:您知道属于一个区域的那些，
Region，其余的，Rest.一开始，你可以选择任何一个点属于Region，剩下的在Rest. - 在
Rest中查找与Region中任意点相邻的点.- 如果你找到一个邻居，把它从
Rest移到Region并重复 - 如果你找不到邻居，就停下来
- Start with two sets (lists?) of points: those that you know belong to a region,
Regionand the rest,Rest. At the beginning, you can pick any single point to belong toRegion, and whatever remains is inRest. - Look in
Restfor a point that is a neighbor to any point inRegion.- if you find a neighbor, move it from
ResttoRegionand repeat - if you don't find a neighbor, stop
这里有一个更简单的定义
neighbors/2的方法:Here is a simpler way to define
neighbors/2:neighbors([X1,Y1], [X2,Y2]) :- abs(X1-X2) + abs(Y1-Y2) =:= 1.您可以通过简单地尝试每种可能的组合来查找一个列表中与另一个列表中的点相邻的点:
You can look for a point in one list that is a neighbor of a point in another list by simply trying out every possible combination:
% 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 的前面.
The call to member/2 picks each point in Region to A, by backtracking. The call to select/3 picks each point in Rest0 to B, with rest of the points in Rest. If the two points are neighbors, B is added to front of Region.
如果
Rest中当前区域没有更多邻居，这将失败，如果有，则至少成功一次.您可能希望使用once(add_to_region(Region0, Rest0, Region, Rest))调用它，这样您就没有不必要的选择点.使用您的示例:This will fail if there is no more neighbors to the current region in
Rest, and succeed at least once if there are. You might want to call this withonce(add_to_region(Region0, Rest0, Region, Rest))so that you don't have unnecessary choice points. Using your examples:?- 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.See how
[2,2]was picked fromRestand added toRegion.?- 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中任何点的邻居.This fails because none of the points in
Restis a neighbor to any of the points inRegion.如上所述绝对可行，但稍加修改，我们就可以拥有一个更容易在 Prolog 中实现的算法.它是这样的:
As explained above is definitely doable, but with a slight modification, we can have an algorithm that is much easier to implement in Prolog. It goes like this:
set_region_rest(+Set, -Region, -Rest)- 按照术语的标准顺序对点集进行排序；现在你有一个
ordset. - 将此集合拆分为一个 Region 和一个不属于它的 Rest
为了进行拆分，我们将维护一个额外的列表.我们将其称为开放节点列表:我们尚未探索的节点.一开始，我们输入列表的第一个元素是唯一的开放节点.其余元素按原样传递.最后两个参数 Region 和 Rest 是输出参数.
To do the splitting, we will maintain one extra list. We will call it a list of Open nodes: nodes that we haven't explored yet. At the beginning, the first element of our input list is the only open node. The rest of the elements are passed as they are. The last two arguments, the Region, and the Rest, are the output arguments.
open_set_closed_rest(Open, Set, Closed, Rest)- 如果开集是空的，那么闭集的其余部分也是空的(现在是区域)；剩下的 Set 是 Rest.
- 否则:
- 从打开列表中获取第一对坐标；立即将其放在 Closed 坐标的前面.
- 尝试在坐标集中找到第一对的任何邻居；如果你找到任何，将它们附加到 Open set 的前面；移除邻居后剩下的 Set 就是新的 Set.
- 使用新的开放集、封闭集的其余部分、剩余的集和其余部分再试一次.
要在 Prolog 中执行此操作，我将首先清理坐标表示.它们出现在两个列表中有点烦人:如果我们使用例如一对来代替:
[X,Y] --->X-Y.为此，我添加了以下谓词:To do this in Prolog, I will first clean up the coordinate representation. It is a bit annoying that they come in lists of two: it is far less writing if we used for example a pair instead:
[X,Y] ---> X-Y. To do this, I add this predicate: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 个额外的测试集！)
(I also put 4 additional test sets!)
因此，我得到:
?- 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].以下是尝试在代码中编写上述算法的方法:
Here is how one could try to write the above algorithms in code:
set_region_rest([A|As], Region, Rest) :- sort([A|As], [B|Bs]), open_set_closed_rest([B], Bs, Region, Rest).这只是对输入 Set 进行排序并从中分离出第一个元素.第一个元素是 Open 集中的第一个坐标对，其余是 Set，然后是输出参数.
This just sorted the input Set and split off the first element from it. The first element is the first coordinate pair in the Open set, the rest is the Set, then the output arguments.
现在，要将 Set 拆分为一个 Region 和一个 Rest，只要我们在 Open set 中有坐标对，我们就需要继续增长 Region.如果 Open set 是空的，这意味着我们的 Region 是完整的，剩下的 Set 就是 Rest:
Now, to split the Set into a Region and a Rest, we need to keep on growing the Region as long as we have coordinate pairs in the Open set. If the Open set is empty, this means our Region is complete, and the remaining Set is the Rest:
:- use_module(library(clpfd)). open_set_closed_rest([], Rest, [], Rest).为了找出坐标的哪些邻居在集合中，我们使用
ord_intersection/4，它同时为我们提供了 Set 中的邻居和 Set 的其余部分.To find out which neighbors of a coordinate are in the Set, we use
ord_intersection/4, which gives us the neighbors in Set and the rest of Set at the same time.注意:4个相邻坐标按顺序排列！
NB: The 4 neighbor coordinates are listed sorted!
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 个解决方案:
This is it. With this, I get the following 6 solutions:
?- 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作为构建块，我们可以轻松地将一组坐标拆分为多个区域:By the way, using
set_region_rest/3as a building block, we can easily split a set of coordinates into regions: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]].这篇关于如何确定矩阵的所有给定坐标都已连接?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
- if you find a neighbor, move it from
- 如果你找到一个邻居，把它从
