Willkommen auf Planet-Liebe

diskutiere über Liebe, Sex und Leidenschaft und werde Teil einer spannenden Community! :)

jetzt registrieren

problem mit TSP :D

Dieses Thema im Forum "Off-Topic-Location" wurde erstellt von kephamos, 1 Dezember 2002.

  1. kephamos
    kephamos (33)
    Verbringt hier viel Zeit
    473
    103
    1
    nicht angegeben
    hallo

    ich soll für informatik nen referat zu TSP machen, also zu dem travelling sales man problem, aber ich check das irgendwie nicht und soooo viele informationen hab ich auch noch nicht gefunden, also bis jetzt haben wir in informatik 3 lösungs ansätze gemacht

    Neares Neighbour
    simulated annealing
    und brute force

    die sollte ich genauer erklären, bloß hab ich dazu noch keine infos gefunden :frown:
    kann mir vielleicht jemand da weiter helfen ?

    thx
     
    #1
    kephamos, 1 Dezember 2002
  2. Angelique
    Gast
    0
    brute force ist das knachen von passwörtern indem jede mögliche buchstaben und zeichenkombination durchprobiert wird aber die anderen beiden habe uch noch nie gehört :rolleyes2
     
    #2
    Angelique, 1 Dezember 2002
  3. User 5089
    Verbringt hier viel Zeit
    20
    88
    4
    nicht angegeben
    brute force: Jeder mögliche Weg wird in seiner Gesamtlänge berechnet und die kürzeste Variante gewählt. Da TSP NP-vollständig ist, lässt sich dieser Ansatz nur für sehr kleine N (Anzahl der Städte) realisieren. Allerdings liefert er als einziger das garantiert minimale Ergebnis.


    Nearest Neighbour: Vom Startpunkt aus wird immer die am nächsten gelegene Stadt angesteuert. Implementierbar, aber unter Umständen auch viel schlechter als die optimale Lösung.


    simulated annealing: Nachzulesen in "Numerical Recipes in Pascal", S. 366ff., ISBN 0-521-37516-9.
    Dieser Algorithmus wurde von Metropolis et al. 1953 erstmals angewendet. Er basiert auf Erkenntnissen der Thermodynamik: Nach der sogenannten Boltzmann-Verteilung sind die Energiezustände E eines Systems zufällig verteilt.
    Daher kann das System ein lokales Energieminimum verlassen und ein globales Minimum anstreben (die Zufallsverteilung erlaubt das). Die Chance hierfür ist klein, aber signifikant größer Null. Hierzu muss man wissen, dass alle Systeme einen minimalen Energiezustand anstreben, selbst wenn sie dafür kurzfristig in einen höheren übergehen müssen.
    Langsam erkaltende, reale Schmelzen tun genau das.
    Daher auch der Name "simuliertes Ausglühen".

    Für die Implementierung braucht man:
    - Konfiguration: Städe von 1...N nummeriert, und (x,y)-Koordinaten
    - Umschichten: Ein Teil des Pfades wird umgedreht oder die Pfade werden vertauscht
    - Kostenfunktion: Die Weglänge berechnen
    - "Ausglühen": Wir berechnen die "Energiedifferenz" bei verschiedenen "Temperaturen".

    Nähere Details samt Beispielprogramm bitte dem oben genannten Buch entnehmen.

    Insgesamt ist dieser Algorithmus wesentlich schneller und liefert nahezu gleich gute Ergebnisse wie brute force.
     
    #3
    User 5089, 2 Dezember 2002

jetzt kostenlos registrieren und hier antworten
Die Seite wird geladen...

Ähnliche Fragen - problem TSP
Ostwestfale
Off-Topic-Location Forum
8 Oktober 2015
30 Antworten
ACE
Off-Topic-Location Forum
10 Juni 2015
7 Antworten
horor51
Off-Topic-Location Forum
16 Februar 2015
2 Antworten
Test