Algorithmen und Datenstrukturen · Senior · Frage 25 von 75
Ein Interviewer beschreibt ein Problem, das sich auf das Problem des Handlungsreisenden zurückführen lässt. Was ist eine sinnvolle Reaktion?
- 1Sagen, dass es unlösbar ist und keine Antwort existiert
- 2Einen O(n log n)-Algorithmus mit Sortieren nach Entfernung versprechen
- 3Sagen, dass es NP-schwer ist; Heuristiken oder exakte DP für kleines n
Antwort zeigen
Richtige Antwort: Sagen, dass es NP-schwer ist; Heuristiken oder exakte DP für kleines n
Erklärung
Kein polynomieller Algorithmus ist bekannt. Exakte Bitmasken-DP ist O(n² × 2ⁿ), in Ordnung bis etwa 20 Städte. Für echte Routen nutzt man Heuristiken wie Nearest Neighbor plus 2-opt oder einen Solver und akzeptiert eine nahezu optimale Antwort.