Neo4J - 旅行推销员

我试图解决使用图形数据库的增强TSP问题，但我很挣扎。我对SQL很好，但是对于密码学家来说，我是一个不错的选择。我创建了一个包含城市（节点）和航班（关系）的简单图。Neo4J - 旅行推销员

设置：前往8个不同的城市（每周1个城市，没有重复），总飞行成本最低。我试图解决一个最佳路径，以最大限度地减少每周更改的航班成本。

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

我开始了使用this article为基础，但它不处理不断变化的距离（或在我的情况下飞行费用）

我知道这是可怕的语法/不可执行的，但在这里就是我到目前为止只得到两班航班;

MATCH (a:CITY)-[F1:FLIGHT{week:1}]->(b:CITY) -[F2:FLIGHT{week:2}]->(c:CITY) RETURN a,b,c;

但是，这并不运行。

接下来，我想我只是试图找到所有的城市从一周&航班，但它不工作的权利无论是作为我获得航班，其中每周<> 1以及= 1

任何人都可以帮忙吗？

PS - 我还没有结婚使用图形数据库来解决这个问题，我刚刚阅读了他们，并认为它会适合尝试它，再加上给我一个理由与他们合作，但到目前为止，我没有太多（或任何）成功。

来源

2014-09-04 NumericOverflow

我已将David的答案标记为可接受的解决方案。我希望能使用Neo4J，但听起来我需要看看IP解决方案。经过更多的研究，Neo4J可能会更好地模拟这种类型的关系问题，但它在计算上还不足以解决NP难题，而不是蛮力。 – NumericOverflow 2014-09-08 20:22:01

neo4j可能是一个很好的软件，但我不希望它在解决这个NP难题上有很大的帮助。相反，我会指给你一个整数程序求解器（可能是this one，但我不能担保它），并建议你将此问题作为一个整数程序制定如下。

对于每个航班f，我们创建一个0-1变量x(f)，如果乘坐f，则为1，如果不乘坐f，则为0。我们的目标是最大限度地降低航班的总成本（我假定每次购买都是独立的决定;否则，你有更多的工作要做）。

minimize sum_{flights f} cost(f) x(f)

现在我们需要一些约束。每周我们都会购买一个航班。

for all weeks i, sum_{flights f in week i} x(f) = 1

我们可以在只有一次一个地方，所以如果我们飞入城市v为i周，那么我们就飞出去城市v为i+1周。我们用一个奇怪而惯用的线性方程来表达这个约束。

for all weeks i, for all cities v, 
    sum_{flights f in week i to city v} x(f) - 
    sum_{flights f in week i+1 from city v} x(f) = 0

我们最多可以飞入每个城市一次。我们最多可以从每个城市飞出一次。这就是我们如何强制访问一次的约束。我们差不多完成了。在这一点上，我将假设旅程开始和结束于提前知道的本地城市u。在第一周内，请删除所有不脱离u的航班。在上周，删除所有未到达u的航班。但是，整数编程的灵活性意味着很容易做出其他安排。

来源

2014-09-04 20:01:56

如果你不打算使用neo4j，因为只有8！ = 40320个可能性，看起来要简单得多，试一试... – 2014-09-05 08:52:06

@FalkHüffner鉴于数据集，它看起来好像应用程序访问32个32位和8个不同的NFL主机城市8是对于方便的蛮力来说有点太大了。 – 2014-09-05 14:25:39

也许这个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）可用路由的所有排列，计算所有这些路径的长度，并返回最短的一个。

来源

2015-05-30 11:24:26 Aistis

Neo4J - 旅行推销员

回答

相关问题