Neo4J - Коммивояжер

Я пытаюсь решить проблему с расширенным TSP с помощью графической базы данных, но у меня возникают трудности. Я отлично разбираюсь в SQL, но я полный новичок в шифровании. Я создал простой граф с городами (узлами) и рейсами (отношениями).

УСТАНОВКА: Путешествуйте в 8 разных городов (1 город в неделю, без дубликатов) с самой низкой общей стоимостью перелета. Я пытаюсь найти оптимальный путь, чтобы минимизировать стоимость перелетов, которая меняется каждую неделю.

Вот файл на pastebin, содержащий мои узлы и отношения. Просто запустите его с Neo4JShell, чтобы вставить данные.

Я начал использовать эту статью в качестве основы, но она не обрабатывать изменяющиеся расстояния (или, в моем случае, расходы на перелет)

Я знаю, что это синтаксически ужасно / невыполнимо, но вот что я сделал до сих пор, чтобы получить всего два полета;

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

Кто-нибудь может помочь?

PS - Я не женат на использовании графической БД для решения этой проблемы, я только что прочитал о них и подумал, что это было бы хорошо подходит, чтобы попробовать, плюс дал мне повод поработать с ними, но пока что я У меня нет большого (или какого-либо) успеха.


neo4j algorithm cypher traveling-salesman
person NumericOverflow    schedule 04.09.2014    source источник
comment
Я отметил ответ Дэвида как принятое решение. Я надеялся использовать Neo4J, но похоже, что вместо этого мне нужно изучить IP-решатель. После дополнительных исследований Neo4J может лучше моделировать этот тип проблемы взаимоотношений, но он все еще недостаточно хорош с вычислительной точки зрения, чтобы решить NP-сложную задачу лучше, чем грубая сила.   -  person NumericOverflow    schedule 09.09.2014

Ответы (2)


arrow_upward
2
arrow_downward

neo4j может быть прекрасной программой, но я бы не ожидал, что она сильно поможет в решении этой NP-сложной проблемы. Вместо этого я бы указал вам на решатель целочисленных программ (возможно, этот, но я не могу за него поручиться) и предлагаем сформулировать эту задачу в виде целочисленной программы следующим образом.

Для каждого полета f мы создаем переменную 0-1 x(f), которая равна 1, если рейс f выполняется, и 0, если рейс f не выполняется. Цель состоит в том, чтобы свести к минимуму общую стоимость полетов (я предполагаю, что каждая покупка - это самостоятельное решение; если нет, то вам нужно еще немного поработать).

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

Мы можем прилететь в каждый город не более одного раза. Мы можем вылететь из каждого города не более одного раза. Таким образом мы устанавливаем ограничение на посещение только один раз.

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. Однако гибкость целочисленного программирования означает, что легко найти другие варианты.

person David Eisenstat    schedule 04.09.2014
comment
Если вы не собираетесь использовать neo4j, учитывая, что их всего 8! = 40320 возможностей, кажется, намного проще просто попробовать их все ... - person Falk Hüffner; 05.09.2014
comment
@ FalkHüffner Учитывая набор данных, похоже, что приложение предназначено для посещения 8 различных городов-хозяев НФЛ из 32, а 32 в падающей степени 8 - это слишком много для удобной грубой силы. - person David Eisenstat; 05.09.2014

arrow_upward
4
arrow_downward

Возможно, этот запрос 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), вычисляет длины всех этих путей и возвращает самый короткий.

person Aistis    schedule 30.05.2015