Я создаю генетический алгоритм для решения проблемы коммивояжера, используя python и networkx. И я добавляю условие сходимости к удовлетворительному решению: путь не должен иметь пересекающихся ребер. Интересно, есть ли в networkx быстрая функция для проверки наличия в графе пересекающихся ребер или, по крайней мере, для того, чтобы узнать, возможно ли их создать.
График создается со списком точек (path
), каждая точка имеет координату в x и координату в y. Последовательность точек указывает путь к туру. Я создал объект nx.Graph()
, как показано ниже:
G = nx.Graph()
for i in range(len(path)):
G.add_node(i, pos=(path[i].x, path[i].y))
for i in range(len(path)-1):
G.add_edge(i, i+1)
G.add_edge(len(path)-1, 0)
Один пример сходящегося не оптимального решения:
распечатать точки с nx.get_node_attributes(G,'pos')
:
{0: (494, 680), 1: (431, 679), 2: (217, 565), 3: (197, 581), 4: (162, 586), 5: (90, 522), 6:(138, 508), 7: (217, 454), 8: (256, 275), 9: (118, 57), 10: (362, 139), 11: (673, 89), 12: (738, 153), 13: (884, 119), 14: (687, 542), 15: (720, 618), 16: (745, 737), 17: (895, 887), 18: (902, 574), 19: (910, 337), 20: (823, 371), 21: (601, 345), 22: (608, 302), 23: (436, 294), 24: (515, 384), 25: (646, 495)}
Вот статья, подтверждающая условие сходимости: http://www.ams.org/publicoutreach/feature-column/fcarc-tsp
Я бы использовал shapely, чтобы найти пересекающиеся линии.
Я не уверен, подходит ли это для вашей задачи, но мне кажется, что это связано с планарностью графа.
Вы можете проверить, является ли граф планарным с помощью:
nx.is_planar(G)
который возвращает True
, если это так. Смотрите документацию.
На самом деле я пробовал это раньше, и он всегда возвращал True, я не знаю, почему.
Мое первое прочтение было таким же, как у @AveragePythonEngineer. Обычно в задаче о коммивояжере и в теории графов нас не слишком заботит положение вершин, а только расстояния между ними. И я подумал, что вы, возможно, путаете рисунок графика с графиком (это всего лишь одна реализация бесконечных возможных рисунков). Таким образом, хотя вы можете нарисовать планарный граф с пересекающимися ребрами, если хотите (как в вашем примере), дело в том, что вы можете нарисовать его на плоскости.
При повторном прочтении вашего вопроса я думаю, что вы фактически вводите «непересекающиеся пути» в качестве ограничения. Другими словами, используя жаргон: путь не должен пересекаться сам с собой. Если это так, то я думаю этот вопрос в GIS Stack Exchange вам поможет. Он использует shapely, очень полезный инструмент для 2D-геометрических вопросов. Из первого ответа:
[Проверить] .is_simple
Возвращает True, если функция не пересекается сама с собой.
from shapely.wkt import loads
l = loads('LINESTRING (9603380.577551289 2719693.31939431, 9602238.01822002 2719133.882441244, 9601011.900844947 2718804.012436028, 9599670.800095448 2718931.680117098, 9599567.204161201 2717889.384686942, 9600852.184025297 2721120.409265322, 9599710.80929024 2720511.270897166, 9602777.832940497 2718125.875545334)')
print(l.is_simple) # False
Если вы хотите решить проблему с нуля, то этот ответ на аналогичный вопрос, но в другой структуре, имеет некоторые интересные наводки, особенно алгоритм Бентли-Оттмана, который может быть полезен.
Спасибо за ответ, согласен с вашей оценкой.
Решение ее с помощью алгоритма Бентли-Оттмана кажется идеальным способом. Я адаптирую график к форме и сравню их. Большое спасибо! Для любопытства мой алгоритм находится на github.com/onofabricio/caixeiroViajante. (Это на португальском языке) Просто запустите скрипт main.py и найдите случайные точки.
Это выглядит как хорошая отправная точка: en.wikipedia.org/wiki/Multiple_line_segment_intersection