Foren-Programmierwettbewerb

SeppJ

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.

Michael E.

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

Swordfish

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?

Michael E.

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.

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)?

Michael E.

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...

Michael E.

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.

Swordfish

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

volkard

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.

Swordfish

volkard schrieb:

Ist das nicht äquivalent zu "Jeder Hof muss besucht werden."?

Am. Joa. So hatt' ich die Aufgabe aber von Anfang an verstanden? Alle Knoten besuchen, dabei die Anzahl der benutzen Kanten minimieren und ja nicht von unbesuchten Knoten dabei erwischt werden einen schonmals besuchten Knoten nochmals anzulaufen. (?)

Michael E.

volkard schrieb:

Mir scheint die Einbettung etwas holprig, sie macht die Aufgabe nur unklarer statt klarer.

Eigentlich sollte die Extraktion der Infos aus dem Text Teil der Aufgabe sein, aber ich gebe zu, dass es mittlerweile etwas unübersichtlich ist. Daher kann ich dir gerne die Aufgabenstellung ohne Weihnachtsmann und Kinder formulieren: 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 \notin \{p\_1,\ldots,p_{i-1}\}$ oder $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.

Swordfish

Yay. Volkard ist jetzt sicher im Bilde. Aber ich als mathematisches Nackerbatzl?

Michael E. schrieb:

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, [...]

Klar soweit. Aber dann ...

Michael E. schrieb:

[...] sodass $p\_i \notin \{p\_1,\ldots,p_{i-1}\}$ oder $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.

... ich glaube zwar zu erahnen, was Du sagen willst, aber ... kommt denn meine laienhafte Umschreibung von oben hin?

~// sorry falls ich hier grade mächtig das Nivea drück :(~

Michael E.

Swordfish schrieb:

Yay. Volkard ist jetzt sicher im Bilde. Aber ich als mathematisches Nackerbatzl?

Dafür gibts ja den Weihnachtsmann.

... ich glaube zwar zu erahnen, was Du sagen willst, aber ... kommt denn meine laienhafte Umschreibung von oben hin?

Ja. Beachte nur die Sonderregel für den Startknoten. Dieser darf nie Nachbar sein, wenn in einem Knoten die unbesuchten Nachbarn ausgehen.

~// sorry falls ich hier grade mächtig das Nivea drück :(~

Ach, Quatsch.

Michael E.

Arbeitet jemand dran oder plant dran zu arbeiten?

SeppJ

Michael E. schrieb:

Arbeitet jemand dran oder plant dran zu arbeiten?

Ich nicht mehr. Auch wenn der Grund dafür ziemlich doof klingen mag: Wegen der Neuformulierung der Problemstellung in Graphensprache und der neuen Sonderregeln. Vorher konnte ich mich richtig schlau fühlen, wenn ich selber eine mathematische Abstraktion der Problemstellung formulierte, nach Lösungen suchte und dabei vielleicht irgendwelche ausgefuchsten Strategien erkannte (vermutlich das, was auch immer mit der neuen Startpunkt-Nachbar-Regel verhindert werden soll). Nun ist es bloß noch etwas, das nach einer langweiligen Hausaufgabe im Informatikstudium klingt. Nicht mehr spannend. Nur wenn mir sehr langweilig sein sollte.

Jester

Ohne die Startpunkteregel isses halt trivial, macht also schon Sinn die dazuzunehmen.

SeppJ

Jester schrieb:

Ohne die Startpunkteregel isses halt trivial, macht also schon Sinn die dazuzunehmen.

Mag sein. Trotzdem ist für mich der Unterschied zwischen "ich löse Probleme mit meinen Mathekenntnissen" und "ich löse eine Matheaufgabe mit meinen Mathekenntnissen" ein wichtiger. Ist vielleicht nicht der logischte Grund, aber da es hier um Motivation geht, anzufangen, spielt das eine wichtige Rolle.

Michael E.

SeppJ: Das kann ich vollkommen nachvollziehen. Ich hätte einfach besser beim Stellen der Aufgabe aufpassen sollen. Naja, Lektion gelernt. Ich werde trotzdem erst nächste Woche auflösen für den Fall, dass sich noch jemand dran versucht.