Problem des Handlungsreisenden.

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Antworten
runge
User
Beiträge: 8
Registriert: Sonntag 9. Dezember 2007, 12:10
Wohnort: Berlin

Guten Tag,

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))
Dieser Städte verwalte ich in der Liste "staedte"

Code: Alles auswählen

staedte=[(1,2), (4,7), (3,4), (4,6), (5,9)]
Die Liste "stadtliste" verwaltet die Route zwischen den Staedten, sowie den zurueckgelegten Weg.
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.
BlackJack

Es sollten weniger Datenstrukturen auf Modulebene definiert werden. Am besten nur Konstanten, Funktionen und Klassen. Das betrifft `staedte` und `Loesungen`.

Wenn man bei Funktionen bei jedem Aufruf leere Listen übergeben muss, die gefüllt werden, hat man einen Initialisierungsteil, der eigentlich *in* die Funktion gehört, nach aussen verlagert. Das betrifft die Argumente `stadtliste` und `Loesungen` bei `einfuegen()`.

Die Rekursion würde ich dort in eine innere Funktion verlegen und das Ergebnisse dann per ``return`` von `einfuegen()` zurück geben.

Da die Wegestrecke zwischen je zwei Städten mehrfach gebraucht wird, macht es Sinn diese einmal am Anfang zu berechnen und sich zu merken.

Man kann, und sollte, in Python direkt über Elemente einer Liste iterieren. Damit kann man sich den Namen `aktuell` sparen und die ganzen ``staedte[aktuell]`` durch einen kürzeren Namen, wie zum Beispiel `stadt` ersetzen.

Mischen von verschiedenartigen Informationen wie in der `stadtliste` ist verwirrend. Die Weglänge sollte nicht das erste Element sein, während alle anderen Elemente Städte sind.

Mit den Städtekoordinaten werden, wenn ich das richtig sehe, zu viele neue Tupel erstellt, wo man einfach das bereits bestehende referenzieren kann.

Von der Laufzeit her könnte es günstiger sein nicht so viele Kopien von den Teilwegen zu erstellen, sondern eine Liste eine Ebene höher mit dem aktuellen Weg zu verwalten und Städte beim rekursiven Abstieg dort hinzu zu fügen und beim Aufstieg wieder zu entfernen. Dann braucht man nur von Lösungen eine Kopie an zu fertigen.

Das `key`-Argument beim sortieren ist im Grunde überflüssig wenn das wichtigste Kriterium sowieso an erster Stelle in den Elementen steht.
Antworten