Ich habe offene geometrische Linien in 3D. die auf der Grundlage der Kriterien für die minimale Länge zusätzlicher Linien zwischen den Endpunkten der Linien in eine einzige Linie zusammengefügt werden müssen. Bitte schlagen Sie einen Algorithmus vor, der eine minimale Komplexität aufweist.Algorithmus zum Verbinden von geometrischen Linien
Ein am besten bekannter Algorithmus läuft in O (2 n) Zeit. Wie Andrew Said in seinem Kommentar sagt, ist dies eine allgemeinere Version des Problems mit reisenden Verkäufern. Wenn Sie einen besseren Algorithmus finden, erhalten Sie einen $ 1000000 Preis.
Sie sollten stattdessen näherungsweise Lösungen versuchen, siehe wikipedia.
Nun, fragen Sie hier ist ein erster Schuss –
Können Sie bitte auf eine bestimmte Lösung zeigen? – surana4u
@ surana4u Ja, der wikipedia-Artikel, auf den ich hingewiesen habe, hat eine große Liste von genauen und nicht genauen Lösungen. – ybungalobill
Ich könnte falsch liegen, aber das klingt für mich ein bisschen wie das Problem mit dem Travelling Salesman. –
Ja, sicher klingt es –
In diesem Fall, bevor Sie das lösen, müssen Sie das Travelling Futureman Problem lösen, um die Lösung aus der Zukunft zu bekommen. –