代码日局域网派对的到来

第 23 天：局域网派对

Github 存储库 - 解决方案

今天的挑战相当激烈，而且有些简单（或者至少第 1 部分是这样）。

第 1 部分：

收集三重奏中的所有连接，其中任何三角形计算机都以 t 开头。其实很简单，然后数一下三角形的数量。

为了实现这一点，我们创建一个节点映射 -> 连接（邻居），所以我们的连接对象看起来类似于：

connections = {
    'kh': {'tc', 'dr'},
    'tc': {'kh', 'dr', 'zx'},
    'dr': {'kh', 'tc', 'xy'},
    'zx': {'tc'},
    'xy': {'dr', 'tz'},
    'tz': {'xy'}
}

为了获得三重奏，我们可以迭代连接，并检索它们的邻居 - 请记住，在 Python 中，连接中的节点将循环遍历键，而不返回值。要访问这些值，我们需要使用键（节点）通过索引连接[节点]来访问它们。

对于每对邻居节点，它都会生成组合。例如：

如果节点 = 'kh' 并且邻居 = {'tc', 'dr'}，则这些对是 ('tc', 'dr')。它检查两个邻居（neighbor1 和 neighbor2）是否也相互连接（通过connections[neighbor1]）。

如果它们相连，则节点、neighbor1 和 neighbor2 之间存在三角形。
三角形已排序并添加到集合中以避免重复。

然后使用
查找任何节点以 t 开头的所有连接

triangles_with_t = [triangle for triangle in triangles if any(
    node.startswith('t') for node in triangle)]

第2部分

在第 2 部分中，我们需要找到最大的互连计算机集。当使用像设置这样的图形时，互连的节点我们称为团。

让我们使用 Bron-Kerbosch 算法来分解它。 Bron-Kerbosch 算法用于查找图中最大的组（称为派系）。在这种情况下，图只是由边（连接）连接的节点（如计算机）的集合。以下是该算法的工作原理以及它与解决我们的难题的关系。

什么是派系？

派系是一组节点，其中每个节点都直接连接到其他每个节点。

想象一下您正在参加一个聚会，每个人都认识小组中的其他人。如果连一个人都不认识其他人，那就不是一个小团体。

在我们的谜题中，目标是找到 LAN 方最大的互连计算机组。这个团体是最大的派系。

什么是子集？

子集是较大组中的较小部分，例如：

如果最大的集团是 (A,B,C,D)，那么较小的子集可能是 A,B,CorB C D`，它们都连接在一起。 这些子集仍然是派系，因为子集中的所有节点都是连接的。

为什么使用 Bron-Kerbosch 算法？

对于大输入来说，通过蛮力找到最大的派系（尝试每个可能的组）是很慢的。例如，如果有 3,000 台计算机，则有数十亿个可能的组需要检查。

Bron-Kerbosch 算法通过以下方式加快此过程：

• 从较小的群体（子集）开始并扩大它们。

• 当一个群体无法发展成更大的派系时就尽早停止。

• 避免重复检查相同的子集。

它是如何运作的？

Bron-Kerbosch 算法递归地工作，这意味着它不断调用自身来逐步建立派系。其工作原理如下：

输入：
R：一组可能形成团伙的节点（从空开始）。
P：仍然可以加入派系的节点列表（从所有节点开始）。
X：我们已经检查过的节点列表（从空开始）。

步骤：
如果 P 和 X 都为空：
R 是一个最大团（你不能向其中添加更多节点）。将 R 保存为结果。

否则：
从 P 中选取一个节点并将其添加到 R 中。
更新 ？和 ？仅包含连接新 R 的节点。

使用新的 R、P 和
再次调用算法 X.

完成后，将节点从 P 移动到 X（已处理）。

重复此操作，直到处理完所有节点，确保找到所有派别而无需进行冗余检查。

这是如何解决这个难题的？

输入：假设我们有一个计算机连接列表，例如：

蟒蛇
A-B
A-C
B-C
B-D
C-D

这些连接代表一个图，其中节点（计算机）通过边（电线）连接。

目标：找到最大的计算机组，其中每台计算机都直接连接到其他每台计算机。

流程：

该算法从较小的群体（子集）开始，并尝试将它们发展成派系。
如果一个群体无法进一步发展（最大派系），它就会停止。

在所有派系中，它确定了最大的派系。

输出：
例如，最大的派系是
{B、C、D}。

子集呢？
在谜题的背景下：

派系的子集（例如 {B,C,D} 中的 {B,C}）并不有趣，因为它们比最大的派系小。

该算法通过跟踪已处理的节点 (X) 来避免子集的冗余检查。

回顾：

Clique：一个组，其中每个节点都连接到每个其他节点。

子集：取自较大派系的较小群体。

布朗-克博什：
查找图表中的所有派系。
专注于最大的派系，而不是在较小的子集上浪费时间。

谜题解决方案：
使用该算法找到 LAN 方最大的互连计算机组。

我希望这可以帮助您理解解决方案，了解 Bron-Kerbosch 算法，并了解有关 Python 语法的新知识。

一如既往，请随时关注我，或在 Twitter 上联系我。

结果是最大的派系，这就是谜题的答案。

其他有用的 Python 要点：

Bron-Kerbosch 递归调用，传入一些修改后的属性 r |节点、p 和连接[节点]。

Python 中

r |节点 - 使用我们正在构建的团 (r) 中当前节点集中的所有节点以及我们正在添加的另一个节点创建一个新集。

p &connections[node] - 这将创建一个新集，其中仅包含以下节点：

• 都在 p（仍然可以作为团的一部分的节点集）中。

• 也在connectionsnode中。

说明：
& 是集合的交集运算符。
connections[node] 是直接连接到节点的节点集合。

p &connections[node] 的意思是“找到 p 和 Connections[node] 之间的公共节点。”

以上是代码日局域网派对的到来的详细内容。更多信息请关注PHP中文网其他相关文章！