algorithm - Neo4J - 旅行推销员

Question

我正在尝试使用图形数据库解决增强的 TSP 问题，但我很吃力。我非常擅长 SQL，但我对 cypher 完全一窍不通。我创建了一个包含城市(节点)和航类(关系)的简单图表。

设置:以最低的总飞行成本前往 8 个不同的城市(每周 1 个城市，无重复)。我正在尝试解决一个最佳路径，以最大限度地减少每周变化的航类成本。

Here is a file on pastebin包含我的节点和关系。只需针对 Neo4JShell 运行它即可插入数据。

我开始使用 this article作为基础，但它不处理不断变化的距离(或者在我的情况下是飞行成本)

我知道这在语法上很糟糕/不可执行，但这是我到目前为止所做的，只获得了两次航类；

匹配 (a:CITY)-[F1:FLIGHT{week:1}]->(b:CITY) -[F2:FLIGHT{week:2}]->(c:CITY)
返回 a,b,c;

但这并没有运行。

接下来，我想我会尝试从第一周开始查找所有城市和航类，但它也无法正常工作，因为我得到了第 <> 1 周和 =1 的航类

匹配 (n) WHERE (n)-[:FLIGHT { week:1 }]->() RETURN n

有人能帮忙吗？

PS - 我不喜欢使用图形数据库来解决这个问题，我刚刚读到它们，并认为尝试它很合适，而且给了我一个与它们一起工作的理由，但是到目前为止，我没有取得太大(或任何)成功。

Answer 1

也许这个 Cypher 查询会给你一些想法。

MATCH (from:Node {name: "Source node" })
MATCH path = (from)-[:CONNECTED_TO*6]->()
WHERE ALL(n in nodes(path) WHERE 1 = length(filter(m in nodes(path) WHERE m = n)))
AND length(nodes(path)) = 7
RETURN path,
    reduce(distance = 0, edge in relationships(path) | distance + edge.distance)
    AS totalDistance
ORDER BY totalDistance ASC
LIMIT 1

它对等于节点数(本例中为 7)的可用路由进行所有排列，计算所有这些路径的长度并返回最短的路径。