Script zur Berechnung einer Strecke

[suchende3876]

Script

Hallo liebes Forum!

Da ich hier schon einmal super Hilfe zu meinen komplizierten Rätseleien bekommen habe, wende ich ich mich gerne wieder an euch und hoffe ihr könnt mir auch diesmal helfen..

Diesmal konnte ich mich nur leider nicht so gut vorbereiten, wie beim letzten Mal, da ich quasi einfach nur Bahnhof verstehe..

Es geht um folgendes:

...


Vielen Dank schonmal für die hoffentlich zahlreichen Helfenden

whizzel

PS: am liebsten in Deutsch

 

[simpsonsfan]

Also Traveling Salesman umgekehrt.

Beherrscht du denn irgendeine Programmier- oder Skriptsprache? Sowas sollte sich eigentlich mit den meisten machen lassen. Falls du also schon irgendeine Sprache beherrscht, dann schreib was in dieser.

Bei deinen 14 Punkten ist das ja auch noch überschaubar. Es gibt dann ja immerhin nur 12! (479.001.600) verschiedene Wege, das Skript selbst wird da nachher schon nicht so ewig brauchen zum durchlaufen.

 

[-Razzer-]

Schau dir mal den Dijkstra-Algorithmus an.
Bei dir ist es aber so, dass du jeweils die größte Strecke benutzt und alle Knoten miteinander verbunden sind.
Ausgangspunkt -> größte Entfernung -> springe weiter -> größte übriger Entfernung -> springe weiter

Stimmt das so?

 

[DJND]

Uhm... per Stift, Zettel und selbstgewachsenem Gehirnschmalz wird es sicherlich ein wenig länger dauern, sämtliche möglichen Kombinationen der 14 Punkte getrennt auszurechnen und anschließend die längste Strecke auszuwählen.

Deswegen wohl auch der Ratschlag, das ganze einmal formal in ein Skript zu schreiben und dies dann vom Rechner auf sämtliche möglichen Kombinationen anwenden zu lassen. Da dies doch enorm nach einer Hausaufgabe klingt und wohl nie in der Form in der realen Welt benötigt wird mußt du das Skript wohl selbst schreiben. Anleitungen gibts zur Entwicklung in allen denkbaren Skriptsprachen genug im Internet. Die sind natürlich selbst einzeln betrachtet in der Regel länger als 12 Seiten. ;-)

Ah.. aber zur Beruhigung: Selbst das ineffizienteste Skript sollte die Aufgabe innerhalb weniger Sekunden, höchstens jedoch Minuten, gelöst haben. Start -> 12 Punkte -> Ende mit fester Kettenlänge ist ja nun wirklich keine große Herausforderung. Drum mußt du dir auch keine so großen Gedanken zur Optimierung machen.

Die Entwicklung deines Skriptes mußt du dann allerdings selbst leisten. Ich zumindest habe nicht vor, dir diese Motivation zum Lernen von etwas neuem zu nehmen. Viel Erfolg!

BTW: Was hat das ganze mit Text und Office zu tun? Wär das nicht eher was für die Programmierecke?

 

[Raijin]

Erster Ansatz könnte sein, vom Startpunkt aus den entferntesten Punkt zu suchen. Von diesem geht man dann wiederum zum entferntesten Punkt (ohne die bereits besuchten Punkte) und so weiter.

Andersherum ist das Problem als "Travelling salesman problem" bekannt. Dort sucht man die kürzeste Route. Es gibt aber keinen effizienten Algorithmus für dieses Problem und man kommt der tatsächlichen Lösung nur per Holzhammermethode auf die Schliche. Du könntest obigen Ansatz zb von verschiedenen Startpunkten testen und vergleichen.

 

[simpsonsfan]

Raijin
Bei 12 variablen Punkten, kann man, glaube ich, ruhig noch auf die "Holzhammermethode" setzen, also alle Kombinationen ausrechnen und davon die Längste behalten.
Solange es ihm natürlich nur um diese eine Aufgabe geht.

 

[Raijin]

12 Punkte = 11! / 2 mögliche Rundreisen. Mal eben 19.958.400 rundreisen

Ist jetzt nicht so wenig, aber geht natürlich schon. Auf jeden Fall sollte man den Algorithmus so oder so rekursiv anlegen. Oder man nutzt Naherungen wie mein beschriebener (beliebig umgebaut) Ansatz. Aber wie wollen ja nicht alles vorkauen

Edit:
Es sind ja sogar 14 Punkte. Dann sind wir schon im Bereich von Milliarden ;-)

Edit 2:
Muss mich korrigieren. 14 Punkte, Start und Ziel vorgegeben also keine Rundreise im eigentlichen Sinne. Dann landen wir nach meiner Rechnung bei 12! Routen. Das sind knapp 480 Millionen Routen.

 

[suchende3876]

Vielen Dank für die vielen Antworten!

Das hätte ich vielleicht mit schreiben sollen..

Die Variante mit Punkt 1 - weiteste Strecke, Punkt 2 - weiteste Strecke usw habe ich natürlich per Hand vorher schon probiert.. Durch ein bisschen weiterrechnen und ausprobieren kam ich dann allerdings auf eine längere Strecke (diese Strecke war willkürlich gewählt).. Daher eben die Erkenntnis, dass das ganze falsch ist.. und weil mein Ergebnis nicht durch den Checker ging..

Auch habe ich mich vom Start und vom Ziel mit der längsten Strecke jeweils genähert und ich habe versucht zu mitteln, in der Hoffnung das dies die längste Strecke ergibt.. Doch auch da kein Erfolg..

Eben - so viele Punkte von Hand ausrechnen ist ein bisschen viel.. und auch Excel schafft das nicht wirklich..

Es handelt sich übrigens nicht um eine Hausaufgabe, sondern um ein Rätsel aus meinem Hobby..
Wäre es eine Hausaufgabe, würde ich wahrscheinlich in der Branche arbeiten und hätte zumindest irgendeine Ahnung davon, wie man das angeht -.- Aber die hab ich nicht..

Vor einiger Zeit hab ich mal Websites gebaut.. nur privat, nichts großes.. es ging nur darum das Prinzip mit den Befehlen usw zu verstehen.. hilft mir das?

Ergänzung (18. November 2013)

Nach ein bisschen Stöbern habe ich zwar ein paar Anleitungen gefunden, finde diese jedoch ziemlich kompliziert, weil sie einfach irgendwo einsteigen..

Batch, PHP, Java, Shell, CMD.. Was ist denn nun das einfachste bzw was könnt ihr mir empfehlen?
Und ein zugehöriges Programm?
Woher bekomme ich dann noch die zugehörigen Befehle?
Gibt es da Übersichten?
Ich finde zwar welche, aber nur die zum Umbenennen von Dateien oder sonstwas da sind..

Ist das ganze doch komplizierter als gedacht oder denke ich nur zu kompliziert?

 

[Raijin]

Bitte nicht mit Batch. Das geht zwar prinzipiell, aber (Windows) Batchprogrammierung ist für den Laien zu .. .. umständlich.

Du könntest dir einfach VisualStudio Express runterladen. Welche Version ist egal. Damit kannst du dann in .Netz programmieren (zb C#).

Bei der Holzhammermethode musst du dann einfach der Reihe nach alle Möglichkeiten durchspielen und jeweils checken ob die aktuell berechnete länger ist als die vorherige.

Ergänzung (18. November 2013)

Beim Algorithmus bietet sich eine Rekursion an. Das ist quasi eine Funktion, die sich selbst aufruft und so immer tiefer einsteigt. So programmierst du in der rekursiven Funktion gewissermaßen nur die Navigation zum nächsten Punkt aus (Inkl Auswahl wo du schon warst) und wenn du keinen freien Punkt mehr hast, ist die Route vorbei und du kannst die Länge bewerten. Das läuft dann schlanke 480 Millionen Mal komplett durch und du hast dein Ergebnis.
Gefühlt sind das 1-2 A4 Seiten Code.

 

[simpsonsfan]

Daher auch meine Frage, ob du schon irgend eine Programmiersprache beherrscht. Von den von dir aufgeführten würde ich am ehesten mal PHP oder Java probieren. Da musst du dich aber natürlich auch einlesen.
Mit Batch würde das bestimmt sehr kompliziert, da hat Raijin recht. Am besten irgendwas, wo du dir die Punkte als Typ definieren kannst und eine schöne Abstandsfunktion schreiben kannst.
Aber am Anfang erfordert das immer Einarbeitungszeit.