Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03637.jsonl.gz/611

Die Lösungsmethode eines Informatikers muss nicht nur ein richtiges Resultat liefern, sie sollte auch schnell und effizient sein.
Allerdings gibt es eine Reihe von komplexen Problemen, für die bis heute nur ineffiziente Lösungsmethoden bekannt sind: Bereits bei relativ kleinem Problemumfang ist ihr Rechenaufwand so gross, dass er auch auf den schnellsten Computern mehrere Jahre dauern würde. Komplexität ist in der Informatik ein Mass dafür, wie stark der Rechenaufwand im Verhältnis zum Problemumfang wächst.
Das Problem des Handelsreisenden
Als Handelsreisender musst du alle auf dem Boden markierten Quadrate besuchen. Finde die kürzeste Rundreise, die bei einem der Quadrate startet und endet und bei der alle anderen Quadrate genau einmal besucht werden. Die Distanz zwischen zwei Quadraten ist jeweils angegeben.
Das minimale Schienennetz
Als Eisenbahningenieur musst du die Quadrate so verbinden, dass man per Bahn von jedem Quadrat in alle anderen Quadrate gelangen kann. Die gesamte Gleisstrecke soll dabei möglichst kurz sein.