Neo4J - 旅行推销员 [英] Neo4J - Traveling Salesman

问题描述

我正在尝试使用图形数据库解决增强型 TSP 问题，但我很挣扎.我对 SQL 很在行，但对密码完全是个菜鸟.我创建了一个包含城市(节点)和航班(关系)的简单图表.

I'm trying to solve an augmented TSP problem using a graph database, but I'm struggling. I'm great with SQL, but am a total noob on cypher. I've created a simple graph with cities (nodes) and flights (relationships).

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

THE SETUP: Travel to 8 different cities (1 city per week, no duplicates) with the lowest total flight cost. I'm trying to solve an optimal path to minimize the cost of the flights, which changes each week.

这是 pastebin 上的一个文件，其中包含我的节点 &关系.只需针对 Neo4JShell 运行它即可插入数据.

Here is a file on pastebin containing my nodes & relationships. Just run it against Neo4JShell to insert the data.

我开始使用 这篇文章 作为基础，但它不处理不断变化的距离(或在我的情况下飞行成​​本)

I started off using this article as a basis but it doesn't handle the changing distances (or in my case flight costs)

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

I know this is syntactically terrible/non-executable, but here's what I've done so far to get just two flights;

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

但这并没有运行.

接下来，我想我会试着找到所有的城市 &从第一周开始的航班，但它也不能正常工作，因为我得到的航班每周 <> 1 以及 =1

Next, I thought I'd just try to find all the cities & flights from week one, but it's not working right either as I get flights where week <> 1 as well as =1

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

有人可以帮忙吗?

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

PS - I'm not married to using a graph DB to solve this, I've just read about them, and thought it would be well fitted to try it, plus gave me a reason to work with them, but so far, I'm not having much (or any) success.

推荐答案

neo4j 可能是一款不错的软件，但我不认为它对解决这个 NP 难题有多大帮助.相反，我会给你一个整数程序求解器(这个，也许，但我不能保证)并建议您将此问题表述为如下整数程序.

neo4j may be a fine piece of software, but I wouldn't expect it to be of much help in solving this NP-hard problem. Instead, I would point you to an integer program solver (this one, perhaps, but I can't vouch for it) and suggest that you formulate this problem as an integer program as follows.

对于每个航班 f，我们创建一个 0-1 变量 x(f)，如果航班 f 被采取，则为 1，而 0如果没有乘坐 f 航班.目标是最大限度地降低航班的总成本(我将假设每次购买都是一个独立的决定；如果不是，那么您还有更多工作要做).

For each flight f, we create a 0-1 variable x(f) that is 1 if flight f is taken and 0 if flight f is not taken. The objective is to minimize the total cost of the flights (I'm going to assume that each purchase is an independent decision; if not, then you have some more work to do).

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

现在我们需要一些约束.我们每周只购买一次航班.

Now we need some constraints. Each week, we purchase exactly one flight.

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

我们一次只能在一个地方，所以如果我们飞入城市v一周i，那么我们飞出城市v 用于 i+1 周.我们用一个奇怪但惯用的线性方程来表达这个约束.

We can be in only one place at a time, so if we fly into city v for week i, then we fly out of city v for week i+1. We express this constraint with a strange but idiomatic linear equation.

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

我们最多可以飞到每个城市一次.我们最多可以飞出每个城市一次.这就是我们如何强制执行只访问一次的约束.

We can fly into each city at most once. We can fly out of each city at most once. This is how we enforce the constraint of visiting only once.

for all cities v,
  sum_{flights f to city v} x(v) <= 1

for all cities v,
  sum_{flights f from city v} x(v) <= 1

我们快完成了.在这一点上，我将假设旅程开始和结束于一个提前知道的家乡城市u.第一周，删除所有不从 u 起飞的航班.对于上周，删除所有未到达 u 的航班.然而，整数规划的灵活性意味着很容易进行其他安排.

We're almost done. I'm going to assume at this point that the journey begins and ends in a home city u known ahead of time. For the first week, delete all flights not departing from u. For the last week, delete all flights not arriving at u. The flexibility of integer programming, however, means that it's easy to make other arrangements.

这篇关于Neo4J - 旅行推销员的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！