Foren-Programmierwettbewerb



  • Hallo,

    hier hat es seit Ewigkeiten keinen Programmierwettbewerb mehr gegeben. Ich hoffe, mit dieser kleinen Aufgabe wieder ein paar dafür begeistern zu können.

    In einer schwer verschneiten Landschaft möchte der Weihnachtsmann Geschenke an verschiedene Einsiedlerhöfe ausliefern. Zwischen manchen dieser Höfe gibt es Straßen, aber es ist sehr anstrengend, sich mit dem Schlitten einen Weg durch den hohen Schnee zu bahnen. Daher möchte der Weihnachtsmann so wenige verschiedene Straßen wie möglich benutzen. Nun gibt es aber das Problem, dass in allen Höfen sehr ungeduldige Kinder auf den Weihnachtsmann warten. Wenn so ein Kind sieht, dass der Weihnachtsmann bei einem benachbarten Hof (d.h. es gibt eine Straße zwischen den beiden Höfen) ist und von dort zu einem Hof zurückfährt, bei dem er bereits war, wird es wütend. Verständnis hat das Kind hingegen, wenn der Weihnachtsmann zu einem anderen bisher unbesuchten Hof fährt.

    Wichtige Änderung: Wenn der Weihnachtsmann zu einem Hof kommt, der keine unbesuchten Nachbarn mehr hat, so darf dieser Hof nicht zum Starthof benachbart sein, es sei denn der Weihnachtsmann ist einen Hamiltonpfad gelaufen, d.h. jeder Hof wurde genau einmal besucht.

    Die Aufgabe: Hilf dem Weihnachtsmann, ein Streckennetz aus möglichst wenigen verschiedenen Straßen zu finden, sodass alle Höfe angefahren werden können, ohne ein Kind wütend zu machen. Technisch:

    struct Street
    {
    	size_t startId;
    	size_t endId;
    };
    
    std::vector<Street> helpSanta(size_t numberOfHouses, const std::vector<Street>& streets);
    

    numberOfHouses bezeichnet die Anzahl der Höfe und streets ist die Liste aller verfügbaren Straßen zwischen Höfen (ungerichtete Kanten), wobei die Höfe von 0 bis numberOfHouses - 1 durchnummeriert sind. Wenn es keine Lösung gibt, soll ein leerer std::vector<Street> zurückgegeben werden. Es gibt keine Einschränkungen an den übergebenen Graphen, außer dass er keine Mehrfachkanten und keine Schleifen (also eine Kante von einem Hof zu sich selbst) enthält. Es sind ausdrücklich auch nicht-zusammenhängende und nicht-planare Graphen erlaubt.

    Nochmal in Mathematisch (nicht abschrecken lassen hiervon, im Zweifel einfach überlesen): Gegeben sei ein einfacher Graph. Finde einen Subgraphen H mit derselben Knotenmenge und minimaler Kantenzahl, sodass H ein Pfad ist oder ein geschlossener Kantenzug P=(p_1,...,p_k) auf H existiert, der jeden Knoten enthält, sodass p_i{p_1,,pi1}p\_i \notin \{p\_1,\ldots,p_{i-1}\} oder N(pi1){p_1,,p_i1}{p1}N(p_{i-1}) \subseteq \{p\_1,\ldots,p\_{i-1}\} \setminus \{p_1\} für jedes i, wobei N(v) die Menge aller Nachbarn von v bezeichnet.

    Bewertet wird die Laufzeit eurer Funktion. Abgabeschluss ist Montag, der 16. März 2015, um 00:00 Uhr (also in der Nacht von Sonntag auf Montag). Einsendungen an <edit>entfernt</edit> mit Betreff "Programmierwettbewerb".

    Viele Grüße
    Michael E.



  • Zwei Fragen:

    1. Darf ich die Startposition beliebig auswählen?
    2. Dir ist hoffentlich bewusst, dass das Problem NP-vollständig ist (TSP lässt sich auf helpSanta reduzieren). Ist mit Laufzeit die asymptotische Laufzeit im Worst-Case gemeint oder die Anzahl Sekunden auf deinem Computer mit deinen Testdaten?


  • kläri fei schrieb:

    Zwei Fragen:

    1. Darf ich die Startposition beliebig auswählen?

    Ja.

    2. Dir ist hoffentlich bewusst, dass das Problem NP-vollständig ist (TSP lässt sich auf helpSanta reduzieren). Ist mit Laufzeit die asymptotische Laufzeit im Worst-Case gemeint oder die Anzahl Sekunden auf deinem Computer mit deinen Testdaten?

    Das Problem ist nicht NP-vollständig, sondern lässt sich recht flott lösen. Beachte, dass die Anzahl verschiedener Straßen minimal sein soll, nicht die Tourlänge. Gewertet wird die praktische Laufzeit auf meinem Computer.


  • Mod

    Auf welchen Sprachstandard darf man sich verlassen? Darf ich die GPU nutzen? Falls ja: Welche API?

    Gewertet wird die praktische Laufzeit auf meinem Computer.

    Und das wäre? Schließlich muss ich mindestens die Anzahl der Threads optimieren. Oder zählt die CPU-Zeit*?

    Mit wie vielen Stationen und Straßen darf/muss man ungefähr kalkulieren? Dutzende? Tausende? Milliarden?

    *: Fände ich nicht gut, wenn das so wäre. Parallelisierung gehört heute dazu. Auch wenn's hier trivial sein dürfte.



  • Stimmt, ist nicht NP-vollständig. Ich dachte irgendwie, man könne die Strassen gewichten (bin schon müde).



  • SeppJ schrieb:

    Auf welchen Sprachstandard darf man sich verlassen? Darf ich die GPU nutzen? Falls ja: Welche API?

    Gewertet wird die praktische Laufzeit auf meinem Computer.

    Und das wäre? Schließlich muss ich mindestens die Anzahl der Threads optimieren. Oder zählt die CPU-Zeit*?

    Puh, bin gerade nicht beim Testrechner. Ist glaube ich ein i7-2600 mit 8 GB RAM. Mit gcc 4.9 wird ein 64-Bit-Windowsprogramm erstellt. Es dürfen alle Dinge des C++14-Standards benutzt werden, die vom Compiler unterstützt werden. Es zählt die real abgelaufene Zeit.

    Mit wie vielen Stationen und Straßen darf/muss man ungefähr kalkulieren? Dutzende? Tausende? Milliarden?

    So viele, wie in den Speicher passen.



  • Michael E. schrieb:

    Mit wie vielen Stationen und Straßen darf/muss man ungefähr kalkulieren? Dutzende? Tausende? Milliarden?

    So viele, wie in den Speicher passen.

    Das ist doch ne sinnfreie Vorgabe, oder? Damit bliebe genau kein Platz mehr für irgendwelche Datenstrukturen - ausser dem undefinierten Platz den man auf dem Stack hat.



  • hustbaer schrieb:

    Michael E. schrieb:

    Mit wie vielen Stationen und Straßen darf/muss man ungefähr kalkulieren? Dutzende? Tausende? Milliarden?

    So viele, wie in den Speicher passen.

    Das ist doch ne sinnfreie Vorgabe, oder? Damit bliebe genau kein Platz mehr für irgendwelche Datenstrukturen - ausser dem undefinierten Platz den man auf dem Stack hat.

    Das soll nur eine Größenordnung angeben. Ich könnte natürlich auch konkreter sagen: Die übergebene Instanz ist maximal 1 GB groß. Aber wenn ich dann merke, dass mehrere Abgaben ungefähr gleich gut sind und alle nur wenig zusätzlichen Speicher brauchen, könnte ich auch 2 GB große Instanzen generieren. Also sagen wir mal so: Ich sorge dafür, dass alles in den RAM passt, solange du nicht Unmengen Speicher benötigst (in diesem Fall wärst du sowieso wahrscheinlich der Langsamste).



  • OK 🙂

    Ich glaub eh nicht dass ich mitmache. Bin nicht so der Algorithmen-Tüftler, und auf Anhieb hab ich mal keinen Plan wie man das schnell lösen können sollte.


  • Mod

    Kannst du irgendwelche graphentheoretischen Angaben über das Straßennetz machen? Insbesondere würde mich interessieren, ob ich die crossing-number als 0 annehmen kann (d.h. keine zwei Straßen schneiden sich, wenn man das Straßennetz zweidimensional zeichnet)?

    Kann man Angaben machen, wie viele Straßen typischerweise von einem Hof ausgehen? Dies wäre insbesondere dann interessant, wenn sich Straßen schneiden dürfen.



  • SeppJ schrieb:

    Kannst du irgendwelche graphentheoretischen Angaben über das Straßennetz machen? Insbesondere würde mich interessieren, ob ich die crossing-number als 0 annehmen kann (d.h. keine zwei Straßen schneiden sich, wenn man das Straßennetz zweidimensional zeichnet)?

    Kann man Angaben machen, wie viele Straßen typischerweise von einem Hof ausgehen? Dies wäre insbesondere dann interessant, wenn sich Straßen schneiden dürfen.

    Sehr gute Frage. ich habe die Antwort soeben in die Aufgabenstellung eingefügt:

    Michael E. schrieb:

    Es gibt keine Einschränkungen an den übergebenen Graphen, außer dass er keine Mehrfachkanten und keine Schleifen (also keine Kante von einem Hof zu sich selbst) enthält. Es sind ausdrücklich auch nicht-zusammenhängende und nicht-planare Graphen erlaubt.

    Das macht zum einen die Aufgabenstellung etwas interessanter, weil der Knotengrad nicht durch 5 beschränkt ist und es deutlich mehr Kanten als Knoten geben kann (und niemand muss sich mit Planaritätstheorie rumschlagen), zum anderen macht es mir aber auch das Erstellen von Testinstanzen leichter. Ich werde im Laufe des Tages einen Instanzgenerator posten, wahrscheinlich Erdős–Rényi-Graphen. Das heißt aber nicht, dass ihr spezielle Eigenschaften von Erdős–Rényi-Graphen ausnutzen sollt 😉



  • Michael E. schrieb:

    Es sind ausdrücklich auch nicht-zusammenhängende [...] Graphen erlaubt.

    So. Jetzt hast mich verloren. Wenn ein Kind schon wütend wird wenn der Weihnachtsmann einen kleinen Umweg macht ... wie ist es dann erst drauf wenn es weit und breit nichtmal eine Straße sieht? Amoklauf?



  • Swordfish schrieb:

    Michael E. schrieb:

    Es sind ausdrücklich auch nicht-zusammenhängende [...] Graphen erlaubt.

    So. Jetzt hast mich verloren. Wenn ein Kind schon wütend wird wenn der Weihnachtsmann einen kleinen Umweg macht ... wie ist es dann erst drauf wenn es weit und breit nichtmal eine Straße sieht? Amoklauf?

    Ja 😉 In diesem Fall soll ein leerer Vektor zurückgegeben werden.



  • Michael E. schrieb:

    Ich werde im Laufe des Tages einen Instanzgenerator posten, wahrscheinlich Erdős–Rényi-Graphen.

    Hier der versprochene Instanzgenerator:

    #include <iostream>
    #include <random>
    #include <vector>
    #include <chrono>
    #include <cmath>
    using namespace std;
    
    struct Street
    {
        size_t startId;
        size_t endId;
    };
    
    /* Generiert wird ein Graph mit n Knoten. Jede Kante ist unabhängig von den
       anderen Kanten mit Wahrscheinlichkeit p im Graphen enthalten. */
    vector<Street> generateErdosRenyiGraph(size_t n, double p, mt19937& generator)
    {
        --n;
        vector<Street> adjacencyList;
        geometric_distribution<size_t> distribution(p);
        size_t pos = -1;
        while((pos += distribution(generator) + 1) < n * (n+1) / 2)
        {
            size_t endId = floor(sqrt(2*pos + 0.25) - 0.5);
            size_t startId = pos - endId * (endId + 1) / 2;
            ++endId;
            adjacencyList.push_back({startId, endId});
        }
        return adjacencyList;
    }
    
    int main()
    {
        unsigned int seed = chrono::system_clock::now().time_since_epoch().count();
        mt19937 generator(seed);
    
        auto rnd = generateErdosRenyiGraph(20, 0.3, generator);    // erzeuge Graph mit 20 Knoten und Kantenwahrscheinlichkeit 0.3
    
        for(auto edge : rnd)
            cout << "{" << edge.startId << "," << edge.endId << "} ";
    }
    

    Edit: Bugfix. Ursprüngliche Version hat Graphen der Größe n+1 erzeugt.



  • Mir würde sich jetzt noch eine Frage stellen:

    Wenn dort ein ungeduldiges Kind wartet, fängt es nur an zu kreischen, wenn der Weihnachtsmann zu einem Haus in der Umgebung mehrfach fährt, oder wenn es die Umgebung wieder über eine bereits gefahrene Straße verlässt (woraus das Kind ja schließen kann, dass der Weihnachtsmann dort ein Haus doppelt besucht)?



  • decimad schrieb:

    Wenn dort ein ungeduldiges Kind wartet, fängt es nur an zu kreischen, wenn der Weihnachtsmann zu einem Haus in der Umgebung mehrfach fährt, oder wenn es die Umgebung wieder über eine bereits gefahrene Straße verlässt (woraus das Kind ja schließen kann, dass der Weihnachtsmann dort ein Haus doppelt besucht)?

    Es werden genau dann Kinder wütend, wenn der Weihnachtsmann in seinem nächsten Schritt zu einem unbesuchten Hof fahren könnte, es aber nicht tut.



  • Irgendwie kommt es mir so vor, als wären die Lösungen dann nicht besonders vielen Freiheiten unterlegen, was ihre Güte betrifft. Also ich meine, wenn man irgendeine Lösung findet, dann ist das auch gleich schon eine der besten (solange man nur benutzte Straßen zurückfährt). Missverstehe ich das Problem?

    Das möglichst schnell umzusetzen ist natürlich noch eine andere Sache...



  • Leider ist mir beim Einbetten des Problems in die Geschichte ein Fehler unterlaufen, der das Problem viel zu einfach macht. Deshalb gibt es jetzt folgenden Zusatz im Ursprungsposting:

    Wichtige Änderung: Wenn der Weihnachtsmann zu einem Hof kommt, der keine unbesuchten Nachbarn mehr hat, so darf dieser Hof nicht zum Starthof benachbart sein, es sei denn der Weihnachtsmann ist einen Hamiltonpfad gelaufen, d.h. jeder Hof wurde genau einmal besucht.

    Der letzte Teil mit dem Hamiltonpfad ist zu euren Gunsten, weil man sich dadurch ein paar eklige Fälle erspart.

    decimad schrieb:

    Missverstehe ich das Problem?

    Ich denke nicht.



  • Magst Dir bitte deinen Erdős–Rényi Generator nochmal ansehen? Der generiert Graphen mit n**+1** Knoten.

    // Sorry, hab' deinen Edit nicht bemerkt. Muss sich angeschlichen haben ...

    ////

    Michael E. schrieb:

    [...] ein Fehler unterlaufen, der das Problem viel zu einfach macht

    Nene, keine Sorge. Ich schwitz jetzt schon Blut und Wasser ob ich das überhaupt hinbekomme - von schnell mal ganz abgesehen. Aber immerhin hab' ich ne verdammt gute Ausrede ... das ist mein allererstel Mal ... mit Graphen 😮



  • Michael E. schrieb:

    Wichtige Änderung: Wenn der Weihnachtsmann zu einem Hof kommt, der keine unbesuchten Nachbarn mehr hat, so darf dieser Hof nicht zum Starthof benachbart sein, es sei denn der Weihnachtsmann ist einen Hamiltonpfad gelaufen, d.h. jeder Hof wurde genau einmal besucht.

    Ist das nicht äquivalent zu "Jeder Hof muss besucht werden."?
    Mir scheint die Einbettung etwas holprig, sie macht die Aufgabe nur unklarer statt klarer.


Log in to reply