TSP programmieren



  • Hallo zusammen,

    nach langem kann ich mich mal wieder diesem Forum widmen. Abistress 🙂

    Nunja. Ich beschäftige mich gerade mit NP Vollständigkeit und mit dem Problem des Handlungsreisenden (TSP). Ich möchte nun ein Programm entwickeln, dass dieses Problem implementiert. Ich bin noch ein absoluter Neuling und weiß, dass es nur sehr ineffiziente Lösungen gibt, da das Problem ja sonst nicht zur NP Klasse gehören würde. Ich versuche gerade alles zu verstehen, doch bei doppelten Sigmas kann ich nicht mehr alles nachvollziehen. Kann mir jemand einen Tipp geben, wo ich mich darüber noch informieren kann, damit ich schließlich ein Programm in C++ darüber schreiben kann?

    Vielen Dank
    lg, freakC++

    PS.: Warum waren die Foren eben gesperrt?



  • Hallo Freak -)

    ich habe dir mal ein paar Links rausgesucht:
    http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo40.php
    http://opus.kobv.de/zib/volltexte/2005/890/pdf/ZR-05-57.pdf
    http://www.thi.uni-hannover.de/fileadmin/forschung/arbeiten/noehring-ba.pdf

    Ich habe vor 10 Jahren auch mal ein Programm dafür (mit dem Borland Builder) geschrieben, inkl. "Nearest Neighbour Heuristic" (für 10 Städte berechnet es auch noch den optimalen Weg - heutige Rechner müssten auch 11 oder 12 Städte in wenigen Sekunden bzw. Minuten schaffen -)

    Ich könnte dir den Sourcecode des Programms mal hochladen...

    Edit: Die Sourcen gibt es unter: http://www.bitel.net/dghm1164/downloads/NP-Sources.zip
    (ist noch mit dem BCB3 erstellt, aber verwendet nur Standard-VCL-Komponenten und sollte daher mit jeder BCB-Version laufen.)

    P.S. Wegen Forumssperre siehe "Forentechnik": http://www.c-plusplus.net/forum/p1975654?sid=f21c1f059d3b34ea3e57db428de24fb4#1975654



  • Hallo Th69,

    schön, von dir zu hören. Herzlichen Dank für die Links. Die Seite der RWTH hatte ich bereits gefunden und finde diese sehr hilfreich. Kannst Du oder jemand anderes mir sagen, wie die bei ihren Tabellen auf eine Zeitmessung in Sekunden kommen? Das ist doch systemabhängig und man müsste wissen, wie viele Operationen der PC pro Sekunde berechnen kann.

    Danke für die Dateien. Ich habe gerade noch schnell einen Blick draufgeworfen, doch da ich auf die Schnelle das nicht durchblickt habe (mein Builder kompiliert das übrigens nicht, aber der Sourcecode ist ja entscheidend), mache ich das morgen.

    Ich habe mich entschieden, zunächst ein Programm zu schreiben, das mittels Brute Force an das Problem geht (wie beim Artikel der RWTH zuerst beschrieben).
    Leider habe ich keine richtige Idee, wie ich dem PC beibringen kann, alle möglichen Zahlenkombinationen zu generieren. Ich habe das mal exemplarisch mit der Reihenfolge 1234 gemacht:

    1234
    1243
    1324
    1342
    1423
    1432

    Ich weiß nun folgendes nicht:

    1.) Wie soll ich die Ziffern behandeln? Wahrscheinlich geht es mit Strings einfacher, da ich dann direkt darauf zugreifen kann, doch professionell ist das sicher nicht 😃 .

    2.) Könnt ihr mir einen Gedanken geben, wie der PC alle möglichen Zahlenkombinationen erstellt, wenn die erste Zahl stehen bleibt (so, wie oben gezeigt?) Das wäre dann Brute Force. Ich gebe also 1234 ein und das Programm soll die obigen Zeilen ausgeben. Das sollte dann für jede beliebige Zahlenkombination gehen - egal wie ineffizient das ist.

    Danke für die weiteren Links, die ich mir morgen auf den Weg zu SatMorPhy anschauen werde 😉

    Vielen Dank und
    lg, freakC++



  • freakC++ schrieb:

    Leider habe ich keine richtige Idee, wie ich dem PC beibringen kann, alle möglichen Zahlenkombinationen zu generieren.

    Suche "C++ Permutationen".
    Es gibt zwei wichtige Richtungen: std::next_permutation und die per Hand geschriebene rekursive Variante. Ich würde hier die rekursive Variante empfehlen. Aber das hängt weniger vom Problem ab als davon, wie Du so programmierst.



  • Ok, danke! Das werde ich mache. Ich möchte das selbst programmieren - also per Hand :D.

    Ich melde mich dann morgen wieder.

    Gute Nacht
    lg, freakC++



  • freakC++ schrieb:

    Ok, danke! Das werde ich mache. Ich möchte das selbst programmieren - also per Hand :D.

    Das ist nett. Dann kannst Du die Weglänge als Returnwert der rekursiven

    //Nur geraten! Fühlt sich total doof an. Vermutlich Thema verfehlt. 
    double search(point* begin,point* end)
    {
       if(begin==end) return 0;
       for(...
          swap(...
          rest=search(begin+1,end)
          if(...
          swap(...
    

    machen und innerhalb von search im for, was eh über die Kinder laufen muß noch die Minimums-also-Returnwert-Aktualisierung reinspleißen, vermute ich. Weiß ich aber nicht, hab's noch nicht gemacht. Fühlt sich nur so an für mich.





  • Danke für die zahlreichen Infos.

    @volkard: Ich hätte das anders gelöst, wobei dein Vorschlag einfach noch in der Rekursion einen Schritt beinhaltet, den ich außerhalb gemacht hätte. Ich werde alle Permutationen in einem Array speichern und dann die Wegstrecke für jedes Element errechnen und diese wieder in einem Array ablegen. Mit einem Sortieralgorithmus werde ich dann das kleinste Element raussuchen.

    @knivil: Werde ich mir anschauen. Danke :p

    Zwei Fragen, die mir wichtig sind:

    1.) Ich bin gerade am Googlen nach "C++ Permutation". Ich hätte die einzelnen Ziffern als Chars behandelt, da es damit wesentlich einfacher geht. Ich weiß aber nicht, ob das wirklich professionell ist. Alle bis jetzt gefundenen Code Schnipsel machen das jedoch auch so. Ihr auch?

    2.) Wie kommen die auf der RWTH Seite

    http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo40.php

    auf diese Zeitmessung. Das ist doch systemabhängig, wenn man das in Sekunden angibt?!

    Vielen Dank
    lg, freakC++



  • Könnt ihr mir bitte nochmal helfen?

    Wie kommen die auf der RWTH Seite (unter "Die Holzhammer-Methode") bei der Brute Force Methode

    http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo40.php

    auf diese Zeitmessung? Das ist doch systemabhängig, wenn man das in Sekunden angibt?!

    Wenn ich 16 Städte habe, dann muss ich bei Brute Force alle Kombinationen aufschreiben, die mit 16 Ziffern gemacht werden können. Es gibt 16! Stück. Dann muss ich für jede Kombination die Streckenlänge ausrechnen. Mein Computer braucht dafür aber nicht 20 Jahre, sondern etwa 20 Sekunden!!!

    Was verstehe ich da falsch?

    Vielen Dank
    lg, freakC++



  • Steht doch sogar im Text:

    Dabei wird angenommen, dass die Bearbeitung einer einzigen Rundreise etwa eine Millisekunde Zeit benötigt.

    Die Zeit zur Bearbeitung einer Rundreise ist natürlich Systemabhängig. Und wenn es weniger als 1 ms für eine Rundreise dauert, dann ist die Gesamtzeit natürlich auch geringer. Es verdeutlicht nur wie stark die Zeit ansteigt, wenn man von 1 ms auf 20 Jahre kommt indem man nur ein paar Städte dazu nimmt.



  • Tatsächlich. Das habe ich einfach überlesen. Danke für den Hinweis. Dann wird mir alles klar!

    Bis bald
    lg, freakC++



  • Der Beitrag ist zwar schon was älter, aber da mein Thema auch das TSP Problem ist schreibe ich hier rein. Ich hoffe mal, das ist okay.

    Eines noch vorab: Ich bin KEIN erfahrener Programmierer (was man auch gleich am Code sieht 😞 ). Und deshalb bin ich auch hier. Damit ich hier lernen kann. Ich habe zwar immer wieder mal (unregelmäßig) programmiert, aber nur so, dass es auch funktioniert. Ich habe nie wirklich auf Effizienz etc. geachtet. Deshalb hoffe ich, dass ihr mich nicht sofort in der Luft zerreißt...ehrlich gesagt ist es mir sogar ein wenig peinlich meinen Code hier zu posten...aber so what.

    Der folgende Codeschnipsel ist im Grunde nur ein Test und berechnet vom Startpunkt aus (x=0, y=0) die kürzeste Strecke zum nächsten Punkt. Nicht mehr. Nur das. Mein Problem ist einfach, dass ich das Gefühl habe, dass der Code für so eine einfache Sache viel zu lang ist und ich zuviele Variablen brauche. (Funktionieren tut der Code. Bis jetzt). Ich hoffe ihr könnt einfach mal drüberschauen und mir eventuell einige Tipps geben. Aber bitte ohne mich zu zerstückeln! 🙂

    #include <iostream>
    #include <math.h>
    
    using namespace std;
    
    //Funktion zum Berechnen der kürzesten Strecke
    float init(int a);
    
    //Das sind die x & y Werte. x1=1, y1=2 ; x2=3, y2=4 usw.
    float num[100]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}; 
    
    int main()
    {
       int wert=20;                      //Anzahl der x & y Werte im Array
       cout<<init(wert)<<endl;    
       return 0;
    }
    

    Das ist erstmal der main Code.

    Und hier kommt die Funktion:

    float init(int a)
    {
        float *p1, *p2;
        float ergebnis[20]={0};
        float start_x=0;
        float start_y=0;
        int i=0;
        float buffer=0;
    
        //Alle Wegstrecken berechnen
        for(int count=0;count<=a-1;count++)
        {
            p1=&num[count];
            p2=&num[count+1];
            ergebnis[i]= sqrt((pow((start_x-*p1),2)) + (pow((start_y-*p2),2)));
            count++;
            cout<<ergebnis[i]<<endl;
            i++;
        }
    
        //kürzeste Strecke auswählen und zurückgeben
        i=0;
        buffer=ergebnis[i];
    
        do
        {
            if(buffer<ergebnis[i+1])
            {
                buffer=buffer;
            }
            else
            {
                buffer=ergebnis[i+1];
            }
            i++;
        }
        while(ergebnis[i+1]!=0);
        return buffer;
    
    }
    

    Wie gesagt, bis jetzt funktioniert es. Dennoch würde ich es gerne irgendwie schöner schreiben. Natürlich muss ich später noch alle anderen Punkte berechnen und vielleicht sollte ich erst schauen, dass alles funktioniert, aber dennoch würde es vielleicht helfen, wenn es irgendwie schöner (und damit übersichtlicher) wäre. Und hier hoffe ich ein wenig auf eure Hilfe bzw. Tipps.

    Ich hoffe, ihr könnte diese Zumutung irgendwie verarbeiten und eure eventuellen Aggressionen auf meinen Code an etwas anderem auslassen 😃 Auch für grobe und dumme Fehler entschuldige ich mich!

    Trotzdem bedanke ich mich schonmal für eure Hilfe!



  • Kann mir da wirklich niemand ein Tipp geben? 😞



  • Was du da machst ist nicht wirklich gut, nicht fehlerfrei und eigentlich auch kein wirkliches TSP.

    Das fängt an bei
    - globale Variable (nichtmals const)
    - C-Array statt std::vector oder std::array
    - mehr als schlechte Variablenbenennung (wenn du nicht dazu sagst, es sei das TSP, würde das niemand erkennen/glauben)
    bis hinzu semantischen Fehlern:
    - du rechnest die Entfernung aller Punkte (10 müssten das an der Zahl sein) zum Nullpunkt aus
    - und suchst danach die kleinste Entfernung daraus (quasi der "minimale Ortsvektorbetrag" :D)



  • Aus Spaß an der Freude hab ich mich grad mal kurz hingesetzt und ein TSP geschrieben:

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <string>
    #include <iterator>
    #include <numeric>
    #include <chrono>
    #include <cmath>
    #include <ctime>
    
    struct Location
    {
    	double x;
    	double y;
    	std::string name;
    
    	Location(double x, double y, std::string const& name)
    		: x(x), y(y), name(name)
    	{}
    
    	double distanceTo(Location const& rhs) const
    	{
    		double x = rhs.x - this->x;
    		double y = rhs.y - this->y;
    
    		return std::sqrt(x*x + y*y);
    	}
    };
    
    typedef std::vector<Location> LocationList;
    typedef std::vector<std::size_t> IndexList;
    
    LocationList createLocations(std::size_t n)
    {
    	LocationList tmp;
    
    	while (n-- > 0)
    	{
    		double x = rand() % 1000;
    		double y = rand() % 1000;
    		std::string name = "Loc" + std::to_string(n);
    		tmp.emplace_back(x, y, name);
    	}
    
    	return tmp;
    }
    
    IndexList createIndexList(LocationList const& locs)
    {
    	IndexList il(locs.size());
    	std::iota(std::begin(il), std::end(il), 0);
    	return il;
    }
    
    double computerTravelDistance(LocationList const& locs, IndexList const& indices)
    {
    	double sum = 0.0;
    	for (std::size_t i = 0; i < indices.size() - 1; ++i)
    		sum += locs[indices[i]].distanceTo(locs[indices[i + 1]]);
    
    	return sum;
    }
    
    const std::size_t N = 5;
    
    int main(int argc, char * argv[])
    {
    	//srand(time(nullptr));
    	auto const places = createLocations(N);
    
    	auto indexList = createIndexList(places);
    
    	double smallestDistance = std::numeric_limits<double>::max();
    	decltype(indexList) smallestTravelRound;
    
    	auto t1 = std::chrono::high_resolution_clock::now();
    
    	do {
    		double tmpDistance = computerTravelDistance(places, indexList);
    
    		if (tmpDistance < smallestDistance)
    		{
    			smallestDistance = tmpDistance;
    			smallestTravelRound = indexList;
    		}
    	} while (std::next_permutation(std::begin(indexList), std::end(indexList)));
    
    	auto t2 = std::chrono::high_resolution_clock::now();
    
    	std::cout << "Distance: " << smallestDistance << std::endl;
    	std::cout << "Way: ";
    	for (auto i : smallestTravelRound)
    		std::cout << "\t" << places[i].name << std::endl;
    
    	std::cout << std::endl << "Time: " << std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1).count() << "s" << std::endl;
    
    	return 0x0;
    }
    

    Gibt zwar noch besseren Code (syntaktisch), aber das hier ist shconmal nicht ganz so mies. Falls du mehr oder weniger Städte haben willst, änder das N über der main-Funktion.

    (Unter MSVC 2013 im Release Modus dauert N = 12 schon etwas, N = 10 geht in 0.2 Sekunden....., N = 13 dauert nur ~994 Sekunden :D)



  • Das es nicht wirklich gut war, habe ich mir schon gedacht 🙂 deswegen hab ich ja gefragt.

    Das war ja aber auch nur ein Codeausschnitt, deswegen auch die globale Variable.
    Zu der Variablenbenennung: Naja…wir brauchen keine Städte. Eigentlich haben wir zu 3 ein Projekt und es sind quasi Punkte auf einem Blech, die optimal angefahren werden müssen. Oder sollten es zumindest. Aber ja, trotzdem ist die Benennung mies muss ich leider eingestehen.

    Der Grund, weshalb ich C Arrays benutzt habe war, weil ich es einfach nicht besser wusste 😞 . Bin halt von C zu C++ und joa.

    Trotzdem vielen Dank, dass du dich bemüht hast und mir geantwortet hast. Ich hatte eigentlich nicht damit gerechnet, dass du mir das gesamte Programm schreibst, aber trotzdem werde ich es wohl nicht so benutzen. Ich will das selber verstehen und benutze es höchstens als Referenz 🙂

    Edit: Wir werden wahrscheinlich doch eine Heuristik benutzen.



  • Dass mein Programm nicht an Städte gebunden solltest du ganz schnell selbst sehen. Sogar für n-dimensionale Koordinaten lässt das mit wenigen Änderungen so benutzen (nur beim Initialisieren und bei der Distanzberechnung). D.h. auch für Anfahrtswege auf einem Blech (was ja nichts anderes als ein Handlungsreisender ist) ist das Programm geeignet.

    Dann: Dass das optimale Ergebnis eines TSPs NP-hard ist solltest du wissen, das heisst es dauert auch schweinelange für größe Anzahl an Orten. (Wie du unten in meinem Post liest geht das mit 11 Positionen noch in wenigen Sekunden, für 12 in 1-2 Minuten und für 13 schon in 15 Minuten Bereich, für N = 14 schätze ich was bei ner Stunde noch was und danach hast du nicht mehr die Zeit dafür). D.h. du musst selbst wissen wie genau dein Ergebnis sein soll.
    Es gibt sicherlich noch etwas bessere Wege das Optimum zu finden, aber auch da wird nur ein konstanter Faktor runtergespielt. Die Krux (dass es für größere Eingabewerte stark länger dauert als für kleine Werte) bleibt auch dabei.

    Klar, heuristische Ansätze hab ich nicht bedacht, aber das hab ich mir auch nicht zur Aufgabe gemacht.

    Und wenn du noch weitere Fragen hast, grad zu heuristischen Ansätzen, mach einen neuen Thread auf.
    Die ersten anderthalb Seiten Thread hier haben mit dem TSP zu tun, aber deine Frage hatte damit quasi nichts zu tun.



  • Ja, du hast Recht. Das was ich wohl versucht habe ist wohl eher die Nearest Neighbor Heuristic. Tut mir Leid, aber ich hatte gedacht, dass es im großen und ganzen doch unter TSP fällt. Naja, falls ich noch Fragen habe, mach ich eben einen neuen Thread auf. Trotzdem vielen Dank für deine Zeit.



  • Ja, aber es ist schon ok, wenn du dafür einen neuen Thread aufmachst.

    Umgekehrt ist meine vorherige Kritik dann auch ungerecht gewesen, da ich nicht von irgendwelchen heuristischen Ansätzen ausgegangen bin, sie auch nicht kenne und daher nicht bewerten kann wie gut oder schlecht dein Code (semantisch/logisch) war.



  • Ich werde demnächst einen neuen Thread aufmachen. Du konntest ja nicht wissen, dass ich nach einem heuristischen Ansatz programmiert habe, denn schließlich habe ich ja auch nichts gesagt. Das war mein Fehler. Aber dennoch hast du mir einige sehr gute Hilfen gegeben, die ich versuchen werde in meinem Programm einzubauen und zu beherzigen. Egal ob es sich nun um TSP oder eine andere Methode handelt. Daher war mein Dank schon ernst gemeint 🙂


Log in to reply