1

我试图通过解决 Advent Of Code 难题来学习 Prolog，但最终被困在一个我认为应该很简单的任务上。有问题的谜题就是这个。该任务要求我找到连接到程序 ID 0 的所有程序 ID（整数）。连接是对称且可传递的，因此如果来自不同连接组的程序之间存在连接，则给定组中的所有程序都相互连接.

我目前的情况是，我已将拼图中的整数排序为子列表，每个子列表都代表它们所属的组。

例如：[[0, 2], [1, 1], [2, 0, 3, 4], [3, 2, 4], [4, 2, 3, 6], [5, 6], [6, 4, 5]]

我需要获取所有以某种方式连接到 0 的程序。在此示例中，这将是除 ID 为 1 的程序之外的所有程序。

因此，我正在寻找的逻辑是设法检查给定整数是否存在于包含 0 的扩展组和我的递归谓词连接的组当前正在查看的组中。我意识到这种方法最终可能会忽略与之前在递归中查看的组的新连接，但这是一个单独的问题。

像上面那样将程序排序到子列表中不是问题，所以我从目前的内容中省略了这部分。

main(R) :-
  Groups = [[0, 2], [1, 1], [2, 0, 3, 4], [3, 2, 4], [4, 2, 3, 6], [5, 6], [6, 4, 5]],
  connected(Groups, [0], R). 

connected([H|T], X, R) :-
  member(Y, H), member(Y, X) -> flatten([H|X], X1), connected(T, X1, R) ; R = X.

我得到的结果很简单：[0,2,0]
我期望的结果是：[0,2,0,2,0,3,4,3,2,4,4,2,3,6,5,6,6,4,5]

我已经意识到该元素[1,1]可能过早停止递归，所以我尝试将上面的最后一行更改为以下内容：
member(Y, H), member(Y, X) -> flatten([H|X], X1), connected(T, X1, R) ; connected(T, X, R).

但是，这只会导致 main(R)。出于某种原因评估为假。同样，如果我只是[1,1]从组中删除而不更改最后一行，它会返回 false。

我假设我忽略了一些非常简单的事情，并且会感谢任何输入。

4

1 回答 1

2

假设您的组具有正确的结构，您可以保留“未访问”组的列表，并在每个递归步骤中获取未访问的项目并添加其仍未访问的邻居。

IE：

main(R) :-
  Groups = [[0, 2], [1, 1], [2, 0, 3, 4], [3, 2, 4], [4, 2, 3, 6], [5, 6], [6, 4, 5]],
  connected([0], [], Groups, R).

connected([], _, _, []).
connected([P|Tail], Visited, Groups, [P|R]):-
  select([P|Ps], Groups, NGroups), % Get the item's neighours
  subtract(Ps, [P|Visited], NPs),  % subtract from it the visited ones
  union(Tail, NPs, NTail),         % and add these neighours to the unvisited list
  connected(NTail, [P|Visited], NGroups, R).

这将获得一组没有重复的“连接”程序：

?- main(R).
R = [0, 2, 3, 4, 6, 5]
于 2017-12-22T14:28:01.900 回答