Minimierung der gesamten Pfadkosten mit Hindernissen und räumlichen Einschränkungen

Question

Ich habe ein Netzwerk von Knoten auf einem 2D Grid angeordnet. Ich möchte Paare von Knoten mit Verbindungen verbinden, die dann physischen Raum auf dem 2D-Gitter belegen. Die Verbindungen sind jetzt selbst Hindernisse und zukünftige Verbindungen müssen einen Weg nehmen, der sie nicht schneidet.

Ich benutze derzeit die A* algorithm und schrittweise Aufbau der Verbindung. Während es den kürzesten Pfad vom Start- zum Endknoten findet, berücksichtigt es nicht die anderen Verbindungen, die vorgenommen werden müssen, so dass die Gesamtwegkosten nach dem Verbinden aller Paare nicht optimal sind.

Weiß jemand, ob es einen Algorithmus gibt, der das lösen kann, oder ist das ein NP-vollständiges Problem? Jede Richtung auf verwandtem Material würde ebenfalls geschätzt werden.

Answer 1

Es scheint, dass Sie versuchen, minimum genus graph embedding, zu finden, wo Ihre Knoten die Graphscheitelpunkte sind und die erforderlichen Verbindungen seine Kanten sind. Minimale Gattung in Ihrem Fall kann als minimale Anzahl von Kantenübergängen interpretiert werden. Auf der Suche nach Verbindungen der minimalen Längen macht es noch schwieriger (oder tut es?)

Minimum Graph Gattung selbst ist NP-vollständig (insbesondere seine Entscheidung Version - ob ein Graph kann in einer Oberfläche der Gattung weniger als eingebettet werden k). Daher wäre Ihr Problem, wenn die Aufgabe wäre, einen solchen Pfad mit einer minimalen Anzahl von Kreuzungen zu finden, auch NP-schwer.

Wenn Sie jedoch nur planare Graphen betrachten, kann die planare Einbettung in linearer Zeit erfolgen.