圣诞老人的最短加权路径

引言：圣诞老人的最短加权路径

HO！HO！HO！今晚是平安夜，圣诞老人正驾驶着他的雪橇环游世界。他喜欢为每个孩子送上最好的礼物，让他们快乐。孩子们从天黑开始就等着他。他们待在壁炉边或窗户附近，仰望夜空，用他们睁得大大的眼睛试图捕捉到任何驯鹿飞行的迹象。他们一个接一个地听着家门口传来的铃声，然后一个新的礼物突然出现在圣诞树下，仿佛魔法降临。当圣诞老人不赶时间时，他甚至可以敲响他们家门，在送礼物之前与兴奋的孩子们面对面交流。

圣诞老人现在正飞越罗马的上空。他非常高兴，因为他刚刚送完了城里的所有礼物，正准备前往下一个城市。但是，等等！不，他刚刚意识到他忘记了三个孩子，亚历西奥、丹尼拉和多明尼克！他该怎样弥补这个疏忽？快点，圣诞老人！快点！让我们在他们睡觉前把礼物送到他们手中，以免他们睡着了，太晚了！！但该怎么做呢？动动你的脑筋，圣诞老人！是的，尤里卡！他想到了！不到片刻，他就将罗马的地图建模成一个图：他认为节点可以是两条或多条街道之间的交叉路口，而道路则是连接每个交叉路口的边。关系可以作为属性携带他需要从一个节点到另一个节点行驶该街道段的时间距离。将此模型存储在 Neo4j 这样的图数据库中，找到到达每个孩子之前最短的加权路线，以确保成功，毫无疑问！

reindeers pulling santas sled or sleigh 0521 1009 1013 0121 SMU

地图图模型

将街道地图表示为图是一个常见的用例场景。这可以通过多种方式实现。例如，我可以看到三种拓扑结构。

您可以将街区建模为节点，并在相邻街区之间绘制关系。

或者顶点可以表示道路，并且每对交叉的街道都是一条边。

第三种模型将道路交叉口视为节点。当两个或多个交叉口由一段车道直接连接且没有其他交叉口时，就会创建一条边。等等。这三个例子都是正确的：您只需要选择最适合您目的的那个。

今晚，圣诞老人将使用第三种表示方法。节点有两个标签：**孩子**和**路口**。前者表示等待圣诞老人送礼物的孩子，以及他们的姓名和就寝时间。为简单起见，就寝时间表示从圣诞老人完全意识到自己遗漏了礼物并开始新的城市遍历到孩子睡着的时间的分钟数。后者是两条或多条街道的交叉口，由其 ID 唯一定义。一个节点可以同时具有这两个标签。实际上，只有一种关系类型：**CONNECTED_TO**。它带有属性距离，表示圣诞老人的雪橇需要多长时间才能穿过该街道段。虽然它是有向边，但它将双向遍历，假设从一侧到另一侧以及反向的时间完全相同。

它描绘了圣诞老人应该找到最快路线的街道地图。每个交叉口都由一个 ID 标识，每个街道段都有一个距离值。三个孩子住在 ID 为 1、2、3 的路口。圣诞老人从节点 0 开始遍历。

Neo4j中的模型设置

让我们看看如何将这个用例场景转换为 Neo4j 上的图。总共有 22 个路口节点。其中三个也表示孩子。他们的名字分别是亚历西奥、丹尼拉和多明尼克，他们的就寝时间分别是 100、50 和 30 分钟。

CREATE
  (a:Kid:RoadJunction {id: 1, name: 'Alessio',  bedtime: 100}),
  (b:Kid:RoadJunction {id: 2, name: 'Daniela',  bedtime: 50}),
  (c:Kid:RoadJunction {id: 3, name: 'Domenico', bedtime: 30}),
  (n0	:RoadJunction	{id:	0	}),
  (n4	:RoadJunction	{id:	4	}),
  (n5	:RoadJunction	{id:	5	}),
  (n6	:RoadJunction	{id:	6	}),
  (n7	:RoadJunction	{id:	7	}),
  (n8	:RoadJunction	{id:	8	}),
  (n9	:RoadJunction	{id:	9	}),
  (n10	:RoadJunction	{id:	10	}),
  (n11	:RoadJunction	{id:	11	}),
  (n12	:RoadJunction	{id:	12	}),
  (n13	:RoadJunction	{id:	13	}),
  (n14	:RoadJunction	{id:	14	}),
  (n15	:RoadJunction	{id:	15	}),
  (n16	:RoadJunction	{id:	16	}),
  (n17	:RoadJunction	{id:	17	}),
  (n18	:RoadJunction	{id:	18	}),
  (n19	:RoadJunction	{id:	19	}),
  (n20	:RoadJunction	{id:	20	}),
  (n21	:RoadJunction	{id:	21	}),
  (a)-[:CONNECTED_TO {distance : 4 }]->(n21),
  (a)-[:CONNECTED_TO {distance : 4 }]->(n7),
  (a)-[:CONNECTED_TO {distance : 4 }]->(n4),
  (b)-[:CONNECTED_TO {distance : 2 }]->(n10),
  (b)-[:CONNECTED_TO {distance : 8 }]->(n17),
  (b)-[:CONNECTED_TO {distance : 1 }]->(n11),
  (b)-[:CONNECTED_TO {distance : 4}]->(n12),
  (c)-[:CONNECTED_TO {distance : 2.5 }]->(n13),
  (c)-[:CONNECTED_TO {distance : 2 }]->(n15),
  (c)-[:CONNECTED_TO {distance : 6 }]->(n17),
  (c)-[:CONNECTED_TO {distance : 5 }]->(n19),
  (n16)-[:CONNECTED_TO {distance : 4 }]->(n21),
  (n16)-[:CONNECTED_TO {distance : 8 }]->(n14),
  (n4)-[:CONNECTED_TO {distance : 4 }]->(n14),
  (n0)-[:CONNECTED_TO {distance : 8 }]->(n21),
  (n0)-[:CONNECTED_TO {distance : 5.5 }]->(n7),
  (n0)-[:CONNECTED_TO {distance : 4 }]->(n8),
  (n7)-[:CONNECTED_TO {distance : 4 }]->(n6),
  (n7)-[:CONNECTED_TO {distance : 4 }]->(n8),
  (n9)-[:CONNECTED_TO {distance : 4 }]->(n8),
  (n9)-[:CONNECTED_TO {distance : 4 }]->(n6),
  (n9)-[:CONNECTED_TO {distance : 9 }]->(n10),
  (n5)-[:CONNECTED_TO {distance : 1 }]->(n6),
  (n5)-[:CONNECTED_TO {distance : 3 }]->(n4),
  (n1)-[:CONNECTED_TO {distance : 6 }]->(n12),
  (n14)-[:CONNECTED_TO {distance : 7.5 }]->(n20),
  (n13)-[:CONNECTED_TO {distance : 5 }]->(n20),
  (n13)-[:CONNECTED_TO {distance : 3 }]->(n15),
  (n12)-[:CONNECTED_TO {distance : 2 }]->(n13),
  (n12)-[:CONNECTED_TO {distance : 3.5 }]->(n11),
  (n15)-[:CONNECTED_TO {distance : 1.5 }]->(n11),
  (n20)-[:CONNECTED_TO {distance : 2.5 }]->(n19),
  (n18)-[:CONNECTED_TO {distance : 6 }]->(n19),
  (n18)-[:CONNECTED_TO {distance : 5 }]->(n17);

为了在查找特定路口 ID 时加快查询速度，圣诞老人决定在此节点属性上创建索引。在这个小图中，您无法真正理解它，但在更大的图中，它是必不可少的。

CREATE INDEX ON :RoadJunction(id)

在这里您可以看到刚刚建模的图。

MATCH (s)-[p]->(o) RETURN s,p,o;

圣诞老人的算法

圣诞老人在路口 {id:0} 顶点时意识到自己的遗漏。这将是他路线的起点。他希望寻找满足以下要求的最佳路径

礼物在**孩子们睡觉前**送到他们手中
从起点（ID 为 0 的节点）到最后一个被访问的孩子遍历地图的旅行时间必须**最小化**。平安夜还没有结束，其他城镇还有很多孩子在等待他们的礼物！您不希望他们错过礼物，对吧？

乍一看，圣诞老人可能会认为使用已经实现的allShortestPaths可能是一个聪明的主意。但是，此函数没有考虑每种关系的权重，该权重由距离属性表征：实际上，较短的路径（指关系最少的路径）可能比较长但较轻的路径具有更高的总距离。圣诞老人需要从头开始开发一个新的查询。圣诞老人的最短加权路径算法如下

MATCH (kid:Kid)
WITH count(kid) as numberOfKids
MATCH path = ((startingRoadJunction)-[:CONNECTED_TO*1..20]-(lastKid:Kid))
WHERE startingRoadJunction.id = 0 and  size(filter(x in nodes(path) WHERE (x:Kid))) >= numberOfKids
WITH  path, [x IN nodes(path) WHERE (x:Kid) | x] as kidsList, numberOfKids
UNWIND kidsList as kidInPath
WITH path, collect(distinct kidInPath) as kidsInPath, numberOfKids
WHERE  size(kidsInPath) = numberOfKids
WITH path,  REDUCE(dist = 0, rel in rels(path) | dist + rel.distance) AS pathLength, kidsInPath,
 [i in range(0,size(nodes(path))) where (nodes(path)[i]):Kid | i] as kidPositions, numberOfKids
 WHERE
  ALL (i in range (0,size(kidPositions)-1) WHERE
 reduce(dist = 0, rel in rels(path)[0..kidPositions[i]] | dist + rel.distance) < (kidsInPath[i]).bedtime)
RETURN path, pathLength
ORDER BY pathLength ASC
LIMIT 1

这里逐行解释算法。请注意，您可能需要在您自己的 Neo4j 图实例中创建数据集以避免org.neo4j.kernel.guard.GuardOperationsCountException异常，该异常不幸地可能会在 graphgist 平台上发生。

1,2)圣诞老人首先想知道他应该为多少个孩子送礼物。查询很简单，可以通过以下方式单独执行

MATCH (kid:Kid)
RETURN count(kid) as numberOfKids

然后，结果（在本例中为 3）通过 WITH 子句（而不是 RETURN）传递到最终查询的其他部分。

3) 您正在寻找与以下模式匹配的子图

节点 lastKid 是一个孩子节点（Kid）
连接节点 startingRoadJunction 和 lastKid 之间至少有 1 条，最多有 20 条跳跃。这些关系的类型为 CONNECTEDTO。尤其是在硬件资源有限且图很大的情况下，设置路径的下限和上限始终是一个明智的做法。在本例中，20 跳足以找到路线。
只要路径的最后一个节点是 lastKid，该模式就是无向的。因此，关系会双向遍历。

每个与该模式匹配的路径都存储到变量 path 中。

4) 在 WHERE 条件中，设置了路径的第一个节点的 ID 必须等于 0 的约束。此外

size(filter(x in nodes(path) WHERE (x:Kid))) >= numberOfKids

表示路径中孩子的数量必须等于或大于之前获得的变量 numberOfKids 的值。此条件将有助于搜索最优解，并从后续查询步骤和计算中删除那些肯定不包含每个孩子的路径。filter 函数迭代 path 的所有节点，返回仅包含标记为 Kid 的节点的数组。

5) WITH 子句允许将变量 path、numberOfKids 变量以及包含在相应路径中找到的所有孩子节点的数组（通过 filter-extract 函数）传递到下一个算法步骤。

6,7) 一条路径可能多次遍历一个孩子节点。这两行的目的是解开每个路径的 kidsList 数组并重新收集它，以便从中删除重复项。因此，结果集合是路径中包含的孩子节点的集合。

8) 对孩子节点集合应用的额外 where 条件。它从结果中删除了那些没有经过所有孩子的路径。由于存在重复项，第 4 行中找到的那个条件不足以确保此要求。例如，具有 kidsList [1,2,2] 的路径排除了 ID 为 3 的孩子节点，即使大小实际上为 3，也应该相应地进行剪枝。

9,10) 在这一点上，算法正在进行两个重要的计算，存储在变量 pathLength 和 kidPositions 中。前者是圣诞老人从起点到终点需要行驶的总时间距离。它是通过 reduce 集合函数获得的。

REDUCE(dist = 0, rel in rels(path) | dist + rel.distance)

它迭代路径中的关系，将总距离累积到初始化为 0 的 dist 变量中。

后者利用了结合了 extract 和 filter 的集合函数。它返回一个数组，其中包含孩子节点在路径所有节点中的位置。例如，假设 [1,4,3,4,6,2] 是 nodes(path) 的结果数组，而 1、2、3 是孩子节点。此函数将返回 [0,2,4]，即孩子节点在数组中的索引。range 函数生成一个从 0 到路径中节点总数的数组。

[i in range(0,size(nodes(path))) where (nodes(path)[i]):Kid | i]

将此 Cypher 代码片段编写为命令式编程伪代码，其表达方式如下

result = [];
for(int i = 0; i < nodes(path).length; i++){
  if(nodes(path)[i] is a kid)
  then result = result + i;
}
return result;

11,12,13) 此 where 条件利用了 ALL 集合谓词：所有元素都必须满足条件。这可能是整个算法中最棘手的步骤。圣诞老人花了很长时间思考这个问题！

ALL (i in range (0,size(kidPositions)-1) WHERE
reduce(dist = 0, rel in rels(path)[0..kidPositions[i]] | dist + rel.distance) < (kidsInPath[i]).bedtime)

它迭代包含孩子节点位置的数组。在每个步骤中，它检查从路径开始到第 i 个孩子的距离是否小于第 i 个孩子的就寝时间。如果路径不满足此要求，则查询将将其丢弃。每个子路径的距离由类似于上一行的 reduce 函数确定。不同之处在于，它不考虑所有路径关系集合，而只考虑其切片 0..i

将此 Cypher 代码片段编写为命令式编程伪代码，其表达方式如下

result = true;
for(int i = 0; i < size(kidPositions); i++){
    distance = 0;
    for(int j = 0; j < kidPositions[i]; j++){
        distance += rels(path)[j];
    }
    if(distance >= kidsInPath[i].bedtime){
        result = false;
    }
}

此 ALL 谓词条件施加的约束很强，圣诞老人在选择路线时应将其考虑在内。

例如，让我们考虑以下路径，其节点 ID 为 [0, 7, 1, 4, 5, 6, 9, 10, 2, 11, 15, 3]，其中孩子节点用粗体表示。其距离为 37 分钟，并在图遍历期间到达了所有三个孩子节点。但是，礼物是在多明尼克（id：3，就寝时间：30）入睡后送达的，不满足所有问题要求。

算法返回的最佳路径为 [0, 8, 9, 10, 2, 11, 15, 3, 19, 20, 14, 4, 1]。其总距离为 46.5，大于前一条路径，需要更多连接；但是，孩子节点的遍历顺序允许所有孩子在收到圣诞礼物时都完全清醒。您应该注意，最靠近起点的孩子亚历山大实际上是最后见到圣诞老人的。

结论和未来工作

在此 GraphGist 中，开发了一个将街道地图建模为图的用例场景，并在 Neo4j 上实现。在其之上，使用 Cypher 构建了一个具有节点约束的最短加权路径搜索算法；它利用了大多数内置的集合函数（extract、filter 和 reduce），以及 UNWIND、range 和 ALL 集合谓词。为了帮助读者更好地理解查询的工作原理，示例保持简单。但是，此处介绍的原理可以轻松扩展到更大的场景。

在更大的图上测试它时，我意识到一些调整可能有助于提高性能，尤其是在没有适当硬件资源的情况下。例如，您可以在每对节点之间创建双向关系，从而更改 (startingRoadJunction)-[:CONNECTED_TO*1..20]→(lastKid:Kid) 中的 MATCH 模式语句。一方面，这将扩展数据库的物理大小；另一方面，它可能会在执行查询时提高整体性能。使用 allShortestPathstartingRoadJunction)-[:CONNECTED_TO*1..20]→(lastKid:Kid 可以肯定地加快算法速度，但它可能会剪枝一些最优解，尤其是在路径较长但较轻的情况下。此外，当遍历更大的数据集时，应肯定修改 20 跳的硬编码上限。总之，即使算法结果令人鼓舞，圣诞老人和孩子们也因此感到高兴，但始终有改进的空间，尤其是在性能发挥关键作用的生产环境中。

我将为您提供两个最后的代码片段，以生成您的随机数据集并使用查询。

可以使用以下两个查询随机创建节点。

WITH ['Alessio', 'Daniela', 'Domenico', 'Elsa', 'Antonella', 'Alessandro',
 'Luciano', 'Susanna', 'Federica', 'Valerio', 'Fabio', 'Marta', 'Mario', 'Giustino'] as names
FOREACH (i IN range(0,100) | CREATE (kid:Kid:StreetNode {id: i, name:names[i % size(names)] + " " + i, bedtime:round(rand()*1000)}));

FOREACH (i IN range(100,1000000) | CREATE (streetNode:StreetNode {id: i}));

相反，可以使用此查询创建边。请注意，在此查询中，每个 RoadJunction 将连接最多四个街道片段。这种假设在真实地图中也很可能发生。

WITH range(0, 1000000) as streetNodeIds
unwind streetNodeIds as streetNodeId
with streetNodeId, extract(x in range(0, toInt(round(rand()*3))) | round(rand()*10000)) as coll
unwind coll as nearStreetNodeId
match (streetNode:StreetNode {id:streetNodeId}), (nearStreetNode:StreetNode {id: nearStreetNodeId})
where streetNodeId <> nearStreetNodeId
merge (streetNode)-[r:CONNECTED_TO {distance: round(rand()*100+1)}]-(nearStreetNode)
return streetNode, nearStreetNode

感谢您阅读至此！希望您喜欢！

祝一切顺利，

亚历山大和圣诞老人

此页面是否有帮助？