Кратчайший непересекающийся путь для графа, вложенного в евклидову плоскость (2D)

Какой алгоритм вы бы использовали, чтобы найти кратчайший путь графа, который вложен в евклидову плоскость, чтобы путь не содержал каких-либо самопересечений (во вложении)?

Например, на графике ниже вы хотите перейти от . Обычно такой алгоритм, как алгоритм Дейкстры, выдает такую ​​последовательность:$(0,0) \rightarrow (-3,2)$

Полный график:

Кратчайший путь:

Кратчайший непересекающийся путь:

Однако этот путь пересекается на евклидовой плоскости, поэтому я хочу алгоритм, который дал бы мне самую короткую непересекающуюся последовательность, в этом случае:

Этот путь длиннее самого короткого пути, но это самый короткий непересекающийся путь.

Есть ли (эффективный) алгоритм, который может это сделать?

Источники TikZ

• Полный график .
• Кратчайший путь .
• Кратчайший непересекающийся путь .

Это NP-полный, чтобы даже решить, существует ли какой-либо путь.

Очевидно, что любой указанный путь является допустимым путем в данном графе. Таким образом, задача с ограниченной длиной находится в NP, как и ее подмножество, задача произвольного пути.

Теперь, чтобы доказать NP-трудность проблемы произвольного пути (и, следовательно, проблемы ограниченной длины), давайте сведем SAT-CNF к этой проблеме:

Глобальная структура - это сетка кусочков проволоки, к которой примыкает столбец кусочков предложения. Логическая формула выполнима тогда и только тогда, когда существует непересекающийся путь через граф.

Невозможно пересечь две части пути, но необходимо пересечь два логических провода. Скорее, путь прохождения строго задан: точка соединения задается двумя узлами. Последовательность точек проводов, через которые проходит путь, вызвана сокращением. Логика представлена ​​тем, какой узел выбран. Любой путь можно выбрать, если он проходит через все точки проводов.

На этой диаграмме путь представлен красной кривой, а логический поток представлен черными проводами:

Теперь давайте создадим каждый компонент.

В проводке используются три элемента: пересечение, точка разветвления и вертикальный провод. Давайте начнем с самого сложного:

Основная идея, лежащая в основе пересечения, состоит в том, чтобы подготовить путь для каждой пары точек проводов и изогнуть возможные пути так, чтобы все пары, кроме тех, которые кодируют одну и ту же логику (совместимые пути), пересекались друг с другом. Конечно, мы не можем просто сказать, что два параллельных ребра пересекаются, но мы можем ввести дополнительные узлы порядка 2, чтобы два пути пересекались.

Предположим, что пути идут с севера на запад и с юга на восток, мы можем: собрать каждую линию с севера с ее совместимым путем с востока на линию (некоторые несовместимые пути будут пересекаться друг с другом); скрестите каждую пару друг с другом, изменив порядок пар; распределите пути к их южным и западным конечным точкам. Это лучше всего объяснить диаграммой. Здесь каждая пара узлов представляет точку соединения. Пути с одинаковым цветовым кодом (несущие одинаковую логику) не пересекаются, пути с другим цветовым кодом:

Точка ветвления и вертикальный провод работают одинаково, но существует меньше путей для корреляции:

$\neg A \vee \neg B$

Это обобщение можно обобщить для кодирования произвольного дерева вентилей AND и OR, разветвляя провод чтения другим способом. В частности, как SAT-CNF, так и SAT-DNF могут быть сведены к проблеме непересекающихся путей способом, описанным выше.

проблема, кажется, датирована Тураном в 1944 году. Это похоже на хороший обзор теории и алгоритмов, «Пересекающееся число графов: теория и вычисления», выполненные Мутцелем. Википедия имеет некоторую информацию при пересечении количества графиков