Neo4J - 여행 세일즈맨

Question

그래프 데이터베이스를 사용하여 증강 된 TSP 문제를 풀려고하고 있지만 고생하고 있습니다. SQL은 훌륭하지만 사이퍼의 멍청한 놈입니다. 도시 (노드)와 항공편 (관계)으로 간단한 그래프를 만들었습니다.

설정 : 가장 적은 총 비행 비용으로 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

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

을 = 어디 항공편을 얻을로

누구든지 도와 줄 수 있습니까?

추신 - 나는 이것을 해결하기 위해 그래프 DB를 사용하지 않고 결혼에 대해 읽었을 뿐이며 시도해보기에 적합 할뿐만 아니라 나와 함께 일할 이유가 있다고 생각했지만 지금까지, 나는 (또는 어떤) 성공을 많이 가지고 있지 않다.

Answer 1

neo4j는 훌륭한 소프트웨어 일지 모르지만이 NP 어려운 문제를 해결하는 데 많은 도움이 될 것으로 기대하지는 않습니다. 대신, 정수형 프로그램 솔버 (this one, 아마도,하지만 그것을 보증 할 수는 없습니다)를 지적하고이 문제를 다음과 같이 정수 프로그램으로 공식화하는 것이 좋습니다.

각 비행 f에 대해 인 0-1 변수를 만듭니다. 비행 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 

우리는 한 번에 하나의 장소에있을 수 있습니다, 그래서 우리는 주 i을 위해 도시 v로 비행하는 경우, 우리는 주 i+1을 위해 도시 v에서 비행. 우리는이 제약을 이상하지만 그러나 관용적 인 선형 방정식으로 표현합니다.

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 

우리는 최대 한 번 각 도시로 날아 갈 수 있습니다. 한 번에 각 도시에서 비행기를 탈 수 있습니다. 이것이 우리가 한 번만 방문하는 제약을 강요하는 방법입니다.

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에 도착하지 않은 모든 항공편을 삭제하십시오. 그러나 정수 프로그래밍의 유연성은 다른 방법을 사용하는 것이 쉽다는 것을 의미합니다.

Answer 2

아마도 키퍼 쿼리는 몇 가지 아이디어를 제공합니다.

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이 예를 들어) 노드의 수와 동일한 사용 가능한 경로의 모든 순열을 수행 모든 경로의 길이를 계산하고 가장 짧은 하나를 반환합니다.