Chemin le plus court sans intersection pour un graphe intégré dans un plan euclidien (2D)

Quel algorithme utiliseriez-vous pour trouver le chemin le plus court d'un graphe, qui est intégré dans un plan euclidien, de telle sorte que le chemin ne contienne aucune auto-intersection (dans l'incorporation)?

Par exemple, dans le graphique ci-dessous, vous souhaitez passer de . Normalement, un algorithme comme l'algorithme de Dijkstra produirait une séquence comme:$(0,0) \rightarrow (-3,2)$

Graphique complet:

Le plus court chemin:

Chemin le plus court sans intersection:

Cependant, ce chemin se croise sur le plan euclidien, donc je veux un algorithme qui me donnerait la séquence sans intersection la plus courte, dans ce cas:

Ce chemin est plus long que le chemin le plus court, mais c'est le chemin le plus court sans intersection.

Existe-t-il un algorithme (efficace) qui peut le faire?

Sources TikZ

• Graphique complet .
• Chemin le plus court .
• Chemin le plus court sans intersection .

Il est NP-complet de décider même s'il existe un chemin.

Il est clairement possible de vérifier qu'un chemin donné est un chemin valide dans le graphique donné. Ainsi, le problème de longueur limitée est dans NP, tout comme son sous-ensemble, le problème de tout chemin.

Maintenant, pour prouver la dureté NP du problème de tout chemin (et donc du problème de longueur limitée), réduisons SAT-CNF à ce problème:

La structure globale est une grille de morceaux de fil contiguës à une colonne de morceaux de clause. La formule logique est satisfiable si il existe un chemin sans intersection à travers le graphique.

Il est impossible de croiser deux parties du chemin, mais il est nécessaire de croiser deux fils logiques. Au contraire, le flux du chemin est strictement donné: un point de fil est donné par deux nœuds. La séquence des points de fil à travers lesquels passe le chemin est forcée par la réduction. La logique est représentée par le nœud choisi. N'importe quel chemin peut être choisi tant qu'il passe par tous les points de fil.

Dans ce diagramme, le chemin est représenté par la courbe rouge et le flux logique est représenté par les fils noirs:

Maintenant, construisons chaque composant.

Le câblage utilise trois tuiles: le croisement, le point de branchement et le fil vertical. Commençons par le plus difficile:

L'idée de base derrière la traversée est de préparer un chemin pour chaque paire de points de fil et de plier suffisamment les chemins possibles pour que toutes les paires, sauf celles qui codent la même logique (chemins compatibles), se croisent. Bien sûr, nous ne pouvons pas simplement dire que deux arêtes parallèles se croisent, mais nous pouvons introduire des nœuds d'ordre 2 supplémentaires pour que deux chemins se croisent.

En supposant que les chemins viennent du nord à l'ouest et du sud à l'est, nous pouvons: collecter chaque chemin du nord avec son chemin compatible d'est sur une ligne (certains chemins incompatibles se croiseront); croiser chaque paire entre elles en inversant l'ordre des paires; répartissez les chemins vers leurs extrémités sud et ouest. Ceci est mieux expliqué par un diagramme. Ici, chaque paire de nœuds représente un point de fil. Les chemins avec le même code couleur (portant la même logique) ne se croisent pas, les chemins avec un code couleur différent:

Le point de branchement et le fil vertical fonctionnent de la même manière, mais il y a moins de chemins à corréler:

$\neg A \vee \neg B$

Il est possible de généraliser cette réduction pour coder un arbre arbitraire de portes ET et OU en ramifiant le fil de lecture de manière différente. En particulier, SAT-CNF et SAT-DNF sont tous les deux possibles à réduire au problème de chemin sans intersection de la manière décrite ci-dessus.

le problème semble dater de Turan 1944. cela ressemble à un bon aperçu de la théorie et des algorithmes, le nombre croisé de graphiques: théorie et calcul par Mutzel. wikipedia a quelques informations sous le nombre de graphiques croisés