Foren-Programmierwettbewerb

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.

Mir fehlt auch irgendwie die Motivation. Ohne die Startpunkteregel war es relativ einfach, mit der Startpunkteregel muss ich einfach noch etwas zusätzlich ausrechnen. Ich weiss, wie es geht und könnte es programmieren, aber das können andere auch.

Die Hauptschwierigkeit besteht dann darin, den Algorithmus, der klar ist, effizient umzusetzen, was auch hauptsächlich mühsam ist und nicht viel Kenntnis bringt. Ausserdem ist die Aufgabe dazu zu unklar gestellt.

Wenn es irgend ein "offenes" Problem mit verschiedenen Ansätzen wäre ist es etwas anderes, aber so ist das wirklich nur die starre Hausaufgabe und da habe ich bessere Dinge zu tun.

Jester

Magst Du es trotzdem noch auflösen?

Ohne die Startpunktregel genügt jeder Tiefensuchbaum den Anforderungen; nie umdrehen wenn es noch nicht besuchte Nachbarn gibt ist genau die Charakterisierung von Tiefensuchbäumen. Mit der zusätzlichen Regel darf man nun niemals bei einem Nachbarn der Wurzel backtracken.

Jester schrieb:

Magst Du es trotzdem noch auflösen?

+1

Jester schrieb:

Ohne die Startpunktregel genügt jeder Tiefensuchbaum den Anforderungen; nie umdrehen wenn es noch nicht besuchte Nachbarn gibt ist genau die Charakterisierung von Tiefensuchbäumen. Mit der zusätzlichen Regel darf man nun niemals bei einem Nachbarn der Wurzel backtracken.

*-*   *-*
   \ /
    *
   / \
*-*   *-*

Wenn du hier in der Mitte startest, funktioniert deine Idee nicht.

Wenn man nicht an einem Artikulationspunkt startet, geht es aber.

Michael E.

Jester schrieb:

Magst Du es trotzdem noch auflösen?

Gerne. Da niemand etwas eingereicht hat, hat mir die Motivation gefehlt, eine Lösung zu schreiben, die im Zweifel niemanden interessiert. Freut mich, dass es nicht so ist.

Für alle, die keine Erfahrung mit Beweisen haben: Schnappt euch ein Blatt Papier und malt das Geschehen auf. Die Beweise sind nicht schwer.

Meine Motivation kommt daher, dass ich gefragt wurde, wie man einen Independency Tree, also einen Spannbaum mit paarweise nicht benachbarten Blättern, in Linearzeit berechnet. Dieser existiert immer, wenn der Graph nicht gerade ein Kreis, der vollständige Graph oder der vollständige bipartite Graph mit gleich großen Seiten ist. Netterweise lösen Independency Trees unser Problem, wenn man den Weihnachtsmann in einem Blatt starten lässt.

Ein simpler Algorithmus mit quadratischer Laufzeit (für unser Problem) lässt sich direkt dem Paper entnehmen: Starte mit einem beliebigen Spannbaum T und betrachte zwei Blätter v und w, die im Originalgraphen benachbart sind. Dann enthält T zusammen mit der Kante {u,v} (im Folgenden T + {u,v}) einen Kreis C, und wenn es sich nicht gerade um einen Hamiltonkreis handelt (also ein Kreis, der alle Knoten enthält, womit wir uns zufrieden geben), dann gibt es einen Knoten w im Kreis C mit mindestens Grad 3 bzgl. T + {u,v}. Löschen wir eine der zu w inzidenten Kreiskanten aus T + {u,v}, so erhalten wir wieder einen Spannbaum, aber die Anzahl der Blätter hat sich reduziert, weil u und v durch das Hinzufügen von {u,v} keine Blätter mehr sind und beim anschließenden Löschen höchstens ein Blatt hinzukommt, weil w kein Blatt werden kann. Das bedeutet, dass wir nach höchstens n solcher Austauschaktionen einen Hamiltonkreis oder einen Independency Tree gefunden haben, weil die Anzahl der Blätter nicht negativ werden kann. Für jeden Tausch benötigen wir lineare Laufzeit, was bei maximal n Austauschaktionen quadratische Laufzeit ergibt.

Nun wollen wir ja aber lineare Laufzeit und keine quadratische. Also starten wir mit einem Tiefensuchbaum T, weil bei diesem, wie du bereits erwähnt hast, zwei Blätter, die nicht gerade die Wurzel sind, nicht benachbart sein können. Also ist das einzige problematische Blatt die Wurzel r, falls diese denn ein Blatt ist. Sei u ein anderes Blatt, das zu r im Originalgraphen benachbart ist. Wir führen nun dieselbe Austauschaktion durch wie vorher, nur passen wir auf, dass das neu entstehende Blatt zu keinem anderen Blatt benachbart ist. Dann reicht insgesamt ein Tausch aus. Mit der Suche nach einem passenden Knoten w in dem Kreis in T + {r,u} starten wir im Blatt u und gehen den u-r-Weg in T nach oben, bis wir den ersten Knoten w mit Grad mindestens 3 gefunden haben. Sei {v,w} die letzte dabei benutzte Kante. Dann ist T' := T + {r,u} - {v,w} wieder ein Spannbaum und v ist ein Blatt von T'. Wir müssen nur noch zeigen, dass v zu keinem anderen Blatt von T' benachbart ist. Sei l ein solches Blatt. Zum Zeitpunkt, als die Tiefensuche l gefunden hat, war v auf dem Stack, denn wäre v noch nicht bekannt gewesen, so wäre l kein Blatt, weil v dranhängen würde, und v kann nicht vom Stack entfernt werden, bevor alle Nachbarn, insbesondere l, gefunden wurden. Also ist l im Subbaum von v bzgl. T. Aber v und w sind gerade so gewählt, dass der Subbaum von v ein einfacher Pfad ist und somit gibt es dort keine weiteren Blätter außer u. Nun ist aber u = v oder u ist kein Blatt mehr, was ein Widerspruch zur Wahl von l ist.

In Code gegossen, sieht das so aus (ich hoffe, das ist die richtige Version):

enum class VisitedState
{
    unfound,
    found
};

vector<Street> helpSanta(size_t numberOfHouses, const vector<Street>& streets)
{
    if(numberOfHouses <= 1)
        return {};

    vector<vector<size_t> > neighbors(numberOfHouses);
    for(const auto& edge : streets)
    {
        neighbors[edge.startId].push_back(edge.endId);
        neighbors[edge.endId].push_back(edge.startId);
    }

    vector<VisitedState> visited(numberOfHouses, VisitedState::unfound);
    vector<size_t> predecessor(numberOfHouses, -1);
    stack<size_t> callStack;
    callStack.push(0);      // Wurzel
    size_t numberOfNonRootLeaves = 0;
    size_t criticalLeaf = -1;   // Blatt, das mit der Wurzel benachbart ist
    vector<Street> tree;
    vector<size_t> position(numberOfHouses, -1);
    size_t rootDegree = 0;

    while(!callStack.empty())  // Tiefensuche, merke dir die Vorgänger jedes Knotens
    {
        auto vertex = callStack.top();
        callStack.pop();
        if(visited[vertex] == VisitedState::unfound)
        {
            if(vertex != 0)    // Die Wurzel hat keinen Vorgänger
            {
                tree.push_back({vertex, predecessor[vertex]});
                if(predecessor[vertex] == 0)
                    ++rootDegree;
            }
            visited[vertex] = VisitedState::found;
            position[vertex] = tree.size();
            bool isLeaf = true;
            for(auto neighbor : neighbors[vertex])
            {
                if(visited[neighbor] == VisitedState::unfound)
                {
                    predecessor[neighbor] = vertex;
                    callStack.push(neighbor);
                    isLeaf = false;
                }
            }
            if(isLeaf)
            {
                ++numberOfNonRootLeaves;
                if(criticalLeaf == -1 && find(begin(neighbors[vertex]), end(neighbors[vertex]), 0) != end(neighbors[vertex]))
                    criticalLeaf = vertex;
            }
        }
    }
    if(tree.size() != numberOfHouses - 1)   // Graph nicht zusammenhängend
        return {};

    if(numberOfNonRootLeaves == 1)      // Hamiltonpfad
        return tree;

    if(rootDegree >= 2)     // Wurzel ist kein Blatt => alle Blätter nicht benachbart
        return tree;

    if(criticalLeaf == -1)  // Es gibt kein Blatt, das mit der Wurzel benachbart ist
        return tree;

    vector<size_t> degree(numberOfHouses, 0);    // Grad bzgl. des gefundenen Baums
    for(auto edge : tree)
    {
        ++degree[edge.startId];
        ++degree[edge.endId];
    }
    assert(degree[criticalLeaf] == 1);

    // Finde ersten Knoten auf criticalLeaf-Wurzel-Pfad mit Grad >= 3 und tausche Kanten aus.
    size_t father = predecessor[criticalLeaf];
    size_t son = criticalLeaf;
    while(degree[father] == 2)
    {
        son = father;
        father = predecessor[father];
    }
    tree[position[son] - 1] = {0, criticalLeaf};
    return tree;
}

Man kann übrigens auch, wie im Paper angedeutet (so richtig klar wird es dort finde ich nicht, wie man es machen soll), zuerst einen passenden Pfad suchen und dann bei der Tiefensuche mit genau diesem Pfad anfangen, sodass die Wurzel der Tiefensuche von Anfang an nicht mit den Blättern benachbart sein kann. Grobe Skizze: Starte von einem beliebigen Knoten u aus einen möglichst langen Pfad P_1 in beliebige Richtung. Sei v der Endknoten von P_1. Dann sind alle Nachbarn von v in P_1. Starte dann ebenfalls von u aus einen zweiten möglichst langen Pfad P_2 in eine andere Richtung, sodass kein Knoten aus P_1 nochmals besucht wird, und sei w der Endknoten dieses Pfades. Wenn v und w nicht benachbart sind, können wir unsere Tiefensuche in w starten, weil alle Nachbarn von w in P_1 + P_2 liegen und alle diese Knoten außer v keine Blätter sein können. Wenn v und w allerdings benachbart sind, gehe von v rückwärts entlang P_1, bis man anders abbiegen kann. Folge dann der neuen Richtung wieder so weit wie möglich. Dann muss man auch von w aus wieder den Pfad so weit wie möglich verlängern. Dann weiß man sicher, dass die neuen Endknoten der Pfade nicht benachbart sind, weil das P_2-Ende in der Knotenmenge von P_1 + P_2 bleibt, aber das P_1-Ende nicht in dieser Knotenmenge liegt.

Problem aller bisherigen Beschreibungen war immer, wenn man zufällig einen Hamiltonkreis gefunden hat. Das bedeutet noch nicht, dass es keinen Independency Tree gibt, aber es gibt dann tatsächlich nur genau dann einen, wenn es einen Hamiltonpfad (also einen Pfad, der alle Knoten enthält) mit nicht benachbarten Endknoten gibt, was genau dann der Fall ist, wenn keiner der oben genannten drei Spezialfälle eintritt. Dieser Hamiltonpfad ist dann auch direkt ein Independency Tree. Die Existenz ist nicht direkt ersichtlich, weshalb ich die Sonderregel mit dem Hamiltonkreis in die Aufgabe eingefügt habe. Wie man außerhalb der Spezialfälle von dem gefundenen Hamiltonkreis in Linearzeit zu einem Hamiltonpfad mit nicht benachbarten Endknoten kommt, erspare ich mir, wenn keiner explizit danach fragt, aber im Prinzip ist es das sorgfältige Anwenden des Beweises aus dem Paper.