ich habe mir mal das Problem des Handlungsreisenden vorgenommen. Falls eine dieses nicht kennen, hier die Erklärung:
Ein Handlungsreisender muß Kunden in einer Reihe von Städten besuchen und zwar in jeder Stadt genau einen. Da er möglichst wenig unterwegs sein möchte, will er die kürzest mögliche Route für seine Tour zusammenstellen. Er kennt die kürzesten Entfernungen zwischen je zwei Städten.
Ich hab mir die verschiedenen Staedte in ein Koordinatensystem modulliert, jedoch in meinem Script willkürlich hinzugefügt, um die Wegberechnung mit der mathemathischen Längenberechnung von Punkt zu Punkt zu berechnen.
Code: Alles auswählen
weglaenge = math.sqrt(pow((stadt2[0] - stadt[0]),2) + pow((stadt2[1] - stadt[1]),2))
Code: Alles auswählen
staedte=[(1,2), (4,7), (3,4), (4,6), (5,9)]
Grenzwert ist der Wert, der vom Benutzer eingegeben werden kann, den der Handlungsreisende als insgesamte Weglänge nicht überschreiten möchte.
Loesungen verwaltet die verschiedenen Route der "stadtliste".
Aufgerufen wird das Script durch Start. Hier muss der Grenzwert übergeben werden, die Städte sind schon vorgegeben, können jedoch geändert werden.
Ausgegeben wird eine nach der Weglänge geordnete Liste von Loesungen die durch die Methode "sortieren" sortiert wird.
Hier das script.
http://www.space.eiserne-front.com/xnx/script.rar
oder
http://home.arcor.de/xon1x/script.rar
Kritik und Verbesserungvorschläge und Fragen sind erwünscht.