Feedback zur Aufgabe 17 / Feedback concerning challenge no. 17

  • Eine schöne "echte" Knobelaufgabe, die man zum Glück auch ohne Petras Hilfe lösen kann.;)

    Der einzige "Wermutstropfen": Auf einem der Postämter hätten doch auch 42 Briefe liegen können oder zumindest eine der "Reitzeiten" hätte 42 sein können. (Mir fällt da sofort eine ein, mit ein bisschen "Gegenwind"....)


    Allerdings war 143 = 13*11 eine "schöne" Zahl.:saint:

  • Eine merkwürdige Situation:


    Ich habe diese Aufgabe mit ein paar Plausibilitätsüberlegungen angefangen [...]

    Wie würde ein Computer so eine Übersicht mit einem Blick bekommen? Oder würde er stumpfsinning viele Routen durchrechnen und dabei manches durch clevere Progammierung abkürzen?


    Früher habe ich ja geglaubt, dass Computer stärker sind, wenn wir ihnen ein paar Tipps mit auf den Weg geben.

    Inzwischen scheinen verschiedene Projeke (Alpha Go, Schach, usw.) zu zeigen, dann KI-Anwendungen zum Lösen von komplexen Aufgaben eben keine Tipps oder Vorgaben von uns benötigen.

    Schönen Gruß

    Frank

    --

    Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch.

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von Ariane () aus folgendem Grund: Bitte keine Details zum (eigenen) Lösungsweg veröffentlichen.

  • Das war eine Top Aufgabe und mein bisheriger Favorit 2020! Netter Text, trotzdem eindeutig gestellt und nicht zu viel Quatsch drumherum erzählt, der ablenkt. Und auch mathematisch sehr gut - genau die richtige Menge an Informationen ist gegeben, damit diese Aufgabe in angemessener [OT: Habe ich gerade ernsthaft googlen müssen, was reasonable auf deutsch heißt? :thinking: ] Zeit lösbar ist. Das war bei Optimierungsaufgaben in der Vergangenheit leider nicht immer der Fall (ich erinnere mich da z.B: an die Etagenhausaufgabe in 2016 (glaube ich)), aber dieses Jahr umso besser. Auch sehr geschickte Aussagen a) - e)!


    [... Kommentar ins Thema Gendergerechte Sprache (#49) verschoben ...]

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von Ariane () aus folgendem Grund: Kommentar ins Thema Gendergerechte Sprache verschoben.

  • frank.buchholz schrieb:

    ... Plausibilitätsüberlegungen ...


    What is often interesting is seeing how different people use different intuitive claims to reach the same solutions. If you look at your intuition more and more closely you are often able to dissect it into different intuitive statements that are true by themselves. Then these simpler statements can sometimes be easily generalized (sometimes not so easily) to "rules of thumb" that often greatly help us find solutions, for example telling you what to start looking at first.


    frank.buchholz schrieb:

    Wie würde ein Computer so eine Übersicht mit einem Blick bekommen? Oder würde er stumpfsinning viele Routen durchrechnen und dabei manches durch clevere Progammierung abkürzen?



    A computer would typically solve this problem in a completely different way, by transforming it into a different problem. It would describe it as a special solid shape in very high dimension, and then explore this shape to find the solution somewhere on the boundary. This can sound very counter-intuitive, but after a while working with these things the relationship between combinatorial problems and algebraic-geometric interpretations becomes much clearer.

    Would the computer be able to get an overview at a glance? No. Computers do not glance 8o For it to "see" certain "intuitive" properties, those have to be explicitly coded into it, which is why we need to do what I was saying in the first paragraph: to know what our intuition tells us mathematically.

    frank.buchholz schrieb:

    Inzwischen scheinen verschiedene Projeke (Alpha Go, Schach, usw.) zu zeigen, dann KI-Anwendungen zum Lösen von komplexen Aufgaben eben keine Tipps oder Vorgaben von uns benötigen.


    This is true and false. The whole purpose of AI is to let it guess its own intuition, without us having to code it inside it. But how is this done? By "training" the AI, and this often takes a LOT of time. Sometimes MUCH more than the time you need to understand the intuition yourself and code it in by hand ;)

    AI is good for applications so complex that we fail to be intuitive with them, or where our intuition is even wrong.


    Great question! Thanks!

  • Nachdem ich zunächst über den Begriff "zurücklassen" gestolpert bin [...]

    Aber dann habe ich mich fürchterlich im Gemisch aus Fakten, Möglichkeiten und Folgerungen der Aussagen verheddert.

    Ganz sicher bin ich mir immer noch nicht. Aber wenn es richtig ist, dass ich bei einer der Aussagen einen Denkfehler gemacht habe, habe ich jetzt immerhin eine Antwort gefunden, die richtig sein könnte. ;)

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von Ariane () aus folgendem Grund: Bitte keine Details zum (eigenen) Lösungsweg veröffentlichen.

  • Hallo, kann es sein das die zu wenig Arbeit für zu viele Wichtel haben? EInige der Aufgaben scheinen mir stumpfe Arbeitsbeschafungsmaßnahmen zu sein. Bspw. das sie Wurmlöcher benutzen, aber immer noch keine (automatische) Eisenbahn für die Post haben. Das scheint mir nicht auf die optimale Erledigung der Arbeit, sondern auf die Beschäftigung der Wichteln abzuzielen. Ein weiteres Indiz wäre die Langweiligkeit der Tätigkeit.


    Ist das der Fall?

  • Ich stelle mir gerade die folgenden Fragen: Die Briefe sind leider ziemlich schwer und Steffan und Ralph möchten sie so kurz wie möglich tragen. Anstatt die Wegstrecke zu optimieren, wollen sie daher die Tragezeiten reduzieren, d.h., die Strecke, die sie einen Brief tragen müssen, summiert über alle Briefe. Welche Routen wählen sie nun? Macht es einen Unterschied, ob sie die Summe ihrer Tragezeiten minimieren wollen, oder nur die längere der beiden Tragezeiten?

  • Hallo, kann es sein das die zu wenig Arbeit für zu viele Wichtel haben? EInige der Aufgaben scheinen mir stumpfe Arbeitsbeschafungsmaßnahmen zu sein. Bspw. das sie Wurmlöcher benutzen, aber immer noch keine (automatische) Eisenbahn für die Post haben. Das scheint mir nicht auf die optimale Erledigung der Arbeit, sondern auf die Beschäftigung der Wichteln abzuzielen. Ein weiteres Indiz wäre die Langweiligkeit der Tätigkeit.


    Ist das der Fall?

    Hehe, social problems are NP-hard.

  • Ich habe mir erlaubt, für die heutige Aufgabe durchzuprogrammieren... leider mit einer scheußlichen Laufzeit. Aber zum Glück war die Aufgabe nicht zu komplex und ich konnte sie schnell lösen. Aber bei größeren Datenmengen? Da wäre ich aufgeschmissen.


    Wahrscheinlich wäre ich ohnehin mit probieren schneller gewesen. Aber ich vertraue meinem Programm mehr als meiner Intuition 8o

  • Die heutige Aufgabe hat mir wieder sehr gut gefallen. War dadurch [...] war in der Lage einen etwas unkonventionellen Ansatz zur Bestimmung der Routen zu benutzen (zumindest bilde ich mir das ein), der das Finden der Routen ziemlich vereinfacht hat.

    Insofern bin ich dann schon gespannt im neuen Jahr herauszufinden, ob ich tatsächlich eine geniale Idee hatte oder ob das ohnehin die Musterlösung war und/oder andere die gleiche Idee hatten. :S

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von Ariane () aus folgendem Grund: Bitte keine Details zum (eigenen) Lösungsweg veröffentlichen.

  • Ich stelle mir gerade die folgenden Fragen: Die Briefe sind leider ziemlich schwer und Steffan und Ralph möchten sie so kurz wie möglich tragen. Anstatt die Wegstrecke zu optimieren, wollen sie daher die Tragezeiten reduzieren, d.h., die Strecke, die sie einen Brief tragen müssen, summiert über alle Briefe. Welche Routen wählen sie nun? Macht es einen Unterschied, ob sie die Summe ihrer Tragezeiten minimieren wollen, oder nur die längere der beiden Tragezeiten?

    Very good ideas, and very good questions. What you are doing is changing the so called "objective function". There are some very easily resolved objective functions, there are some very hard to solve objective functions.


    What you are suggesting here (i.e. making the weight of a connection not constant, but dependent on an external variable instead (the amount of letters in the backpack)) is a strong complication to the problem. Very good thinking, it is much harder to solve now! These kind of problems, those where the data of your problem is not constant but depends on something else (usually time), are very hard optimization problems that are the central to modern day research.


    Nice question :)

  • Ich habe mir erlaubt, für die heutige Aufgabe durchzuprogrammieren... leider mit einer scheußlichen Laufzeit. Aber zum Glück war die Aufgabe nicht zu komplex und ich konnte sie schnell lösen. Aber bei größeren Datenmengen? Da wäre ich aufgeschmissen.


    Wahrscheinlich wäre ich ohnehin mit probieren schneller gewesen. Aber ich vertraue meinem Programm mehr als meiner Intuition 8o

    This is a very good approach, and I would be very interested to see your code (not in this forum, or else everyone else would have it). Remember that programming is not a shortcut, but a tool. If you are able to use it to get the answers you need and also understand the math within it, then you've just done a great great thing.


    The challenge here was not a simple one for a computer to brute force, even though it's about a network so very tiny. Through smart reformulations of the problem (the high dimensional geometric approach I spoke of above), together with very advanced heuristics and ideas (intuition!) there have been programs able to solve much, MUCH larger instances of similar problems. The key to these programs is 100% the math behind the reformulations though, because also most of the intuition implemented was coming from the geometric approach.


    Bravo for using a computer to solve things :)

  • When branch-and-bound becomes branch-everything it means that you are not actually doing the bounding part. A key component of b&b is that you are able to prove that all of the branching under a certain node will not be better than the solution at that node. Therefore then you can avoid exploring a certain branching of the search-tree if you have already found a feasible solution that is better than the solution at the root of that branching.

    Thank you for all your explanations to this topic in the forum.


    The "branch-everything" was of course an exaggeration. When doing graph optimization problems by hand there is no excuse for ignoring the obvious lower bound and continuing the branches all the way down.

    If I remember correctly, for bigger networks in branch-and-bound we normally need both a good heuristic/intuition to take the good decisions very early as well as a good (often non-trivial) lower bound to discard the bad decisions before branching almost all the way down.

    What I often find in these kind of problems is that the opportunity cost of finding a lower bound (=time to find the lower bound + possibility of errors in that bound - time saved by that bound) is often minimized for the trivial bounds. This, of course, requires a bit more branching which than sometimes feels like a "branch-everything"-approach :).


    A computer would typically solve this problem in a completely different way, by transforming it into a different problem. It would describe it as a special solid shape in very high dimension, and then explore this shape to find the solution somewhere on the boundary. This can sound very counter-intuitive, but after a while working with these things the relationship between combinatorial problems and algebraic-geometric interpretations becomes much clearer.

    Would the computer be able to get an overview at a glance? No. Computers do not glance For it to "see" certain "intuitive" properties, those have to be explicitly coded into it, which is why we need to do what I was saying in the first paragraph: to know what our intuition tells us mathematically.

    I had one course in which we used a solver for this kind of approach. It was a very interesting experience, but I often found it a bit annoying that most problems we did were done by "easy" modelling and then relying on the cleverness of the solver.

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von JdPL () aus folgendem Grund: I forgot the word "bound" in "lower bound"

  • Ich habe mir erlaubt, für die heutige Aufgabe durchzuprogrammieren...

    Nachdem ich durch Probieren keine geeigneten zwei Routen gefunden hatte, habe ich bei dieser Aufgabe auch programmiert. Ich habe [Lösunghinweis entfernt] - in 0,1 Sekunden. Dann war der Rest von Hand kein Problem mehr. Um 20 Uhr hatte ich die Lösung.

    Die Lösung ist vom Lösungsweg unabhängig.

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von Tilman () aus folgendem Grund: Lösunghinweis entfernt

  • Ich habe mir erlaubt, für die heutige Aufgabe durchzuprogrammieren... leider mit einer scheußlichen Laufzeit. Aber zum Glück war die Aufgabe nicht zu komplex und ich konnte sie schnell lösen. Aber bei größeren Datenmengen? Da wäre ich aufgeschmissen.


    Wahrscheinlich wäre ich ohnehin mit probieren schneller gewesen. Aber ich vertraue meinem Programm mehr als meiner Intuition 8o

    Also ich fand Probieren, alleine schon wegen der vielen Zahlen und Verbindungen, zu komplex für mich :D


    Ich hab's dann auch programmiert und nur noch [Lösungshinweis entfernt].


    Die Laufzeit war okay. Unter 1 Sekunde für ein Script in Perl finde ich nicht wild.


    Lass uns im Januar mal die Strategien vergleichen.

    Dieser Beitrag wurde bereits 1 Mal editiert, zuletzt von Tilman () aus folgendem Grund: ​Lösungshinweis entfernt.