Die Mathe-Redaktion - 21.10.2019 02:52 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 455 Gäste und 3 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Matroids Matheplanet Forum Index » Aktuelles und Interessantes » der nächste Al Zimmermann Contest ab 27.07.2019
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich der nächste Al Zimmermann Contest ab 27.07.2019
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26849
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2019-07-21


Siehe azspcs.com/



-----------------
Bild



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 998
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2019-07-23


Hallo viertel,

ja, ich bin mal gespannt, was Al Zimmermann dieses mal wieder ausgebrütet hat. Fifth Avenue klingt irgendwie nach einer optimalen Unterbringung bestimmter Gebäudeumrisse in einer vorgegebenen Grundfläche, aber lassen wir uns mal überraschen, was sich dahinter wirklich verbirgt.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6050
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2019-08-06


Das Problem sieht recht spannend aus. Die Lösung haben Struktur, aber anscheinend nicht soviel, dass man die Struktur nur finden und reproduzieren muss.
Ich habe es mal mit lokalen Suchverfahren versucht und habe damit die ersten 5 Probleme gelöst(*).
Da die besten Werte jetzt auch wieder auf der Seite mit aufgeführt werden, werde ich in den nächsten Tagen mal nach und nach für alle n einen Durchlauf machen und schauen, wo ich damit lande.

(*) "optimale Lösung" / "gelöst" -- bedeutet hier immer "den besten bekannten(!) Wert (gefunden)"



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 998
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2019-08-06


Hallo Kitaktus,

ich finde die Programmieraufgabe auch sehr interessant.

Habe auch schon gerätselt, ob die optimale Lösung eine bestimmte Struktur bzw. ein bestimmtes Muster aufweisen muss, aber hatte diesbezüglich noch keine passende Programmieridee, weil ich noch keine ausgereifte Idee habe, welches Muster es sein könnte.

Bin erstmal mit einem rudimentäreren Ansatz rangegangen, der zwar auch schon recht passable Ergebnisse erzielt, aber diesmal gibt es wie beim letzten Mal auch wieder sehr viele Teilnehmer mit sehr guten Ergebnissen, so dass es schon eines besonderen Kniffes bedarf, um an die optimalen Lösungen heranzukommen.

Leider hab ich bislang für kein gefordertes $n$ die bisherige Optimallösung, nicht mal für $n=6$.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6050
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2019-08-07


Es ist (leider?!) mal wieder so ein typisches "Simulated-Annealing"-Problem(*). Es bilden sich Strukturen, die lokal betrachtet sehr wenig Energie haben, aber wenn man den Betrachtungsfokus vergrößert, dann treffen die lokalen Cluster irgendwo aufeinander und dort passt es dann nicht so richtig. Jetzt braucht man einen Effekt, die die Cluster wieder aufbricht und eine Neuanordnung der Elemente zulässt.
Ich schätze, dass im Bereich Score 24-25 etliche Leute mit Simulated-Annealing-Ansätzen unterwegs sind.
Das schlägt sich auch in den Zielfunktionswerten wieder. Nach dem ersten Durchlauf waren vier meiner Scores im Bereich 0.93-0.94, während alle anderen im Bereich 0.98-1.00 lagen. Bei den vier Werten habe ich offenbar irgendeine "Barriere" nicht durchbrochen.
Man müsste sich jetzt eigentlich intensiver mit den Strukturen befassen. Aber das kostet halt Zeit...

(*) Siehe hier.



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 998
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2019-08-07


Hallo Kitaktus,

klingt vielversprechend dieser Ansatz "Simulated Annealing". Muss ich mal die nächste Zeit gucken, ob es mir gelingt, daraus einen tauglichen Algorithmus zu basteln.

Letztlich denke ich schon, dass gewisse Strukturen oder Muster erfüllt sein müssen, weil totales Chaos führt ja normalerweise nicht zu einem besten Resultat. Aber gut möglich, dass es mehrere solcher "Cluster" sein müssen, die auf bestimmte Weise verzahnt werden müssen.

Erst dachte ich ja schon, ob man vielleicht solche Muster wie bei den Verknüpfungstafeln symmetrischer oder alternierender Permutationsgruppen verwenden kann, aber das passt nicht, da in der Gruppentafel ja nur $n$ statt $n^{2}$ verschiedene Elemente vorkommen und dann auch nicht klar ist, wie bzw. gemäß welcher Abbildung man $n$ verschiedene Fälle (d. h. Tokenfelder) nutzbringend auf $n^{2}$ verschiedene aufblähen kann. Außerdem gibt es nicht zu jedem $n$ von 6 bis 30 eine symmetrische oder alternierende Permutationsgruppe mit passender Mächtigkeit.

Bisher hab ich lediglich einen Algorithmus, der auf Zufallsfunden kombiniert mit Greedy-Strategie beruht, wobei mein Greedy-Verfahren sehr simpel gehalten ist. Ich verwerfe dort im Gegensatz zu Simulated Annealing sofort solche Lösungen, die eine temporäre Verschlechterung bringen. Aber es leuchtet mir ein, dass man kleinere vorübergehende Verschlechterungen wohl zulassen muss, um zu einer besseren Gesamtlösung zu kommen.

Mal sehen, ob ich meine Ergebnisse noch irgendwie verbessern kann in nächster Zeit.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1335
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2019-08-07


Ich habe ebenfalls mit einer lokalen Suche (jedoch nicht SA) die ersten 5 Probleme lösen können. Die geraden n scheinen dabei leichter zu sein als die (um 1 kleineren) ungeraden Werte.

Ich gehe davon aus, dass man - wie in den vorherigen Contests eigentlich auch - problemspezifische Eigenschaften ausnutzen muss, um vorne mitzuspielen.

Kay



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6050
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2019-08-09


So, ich habe meine persönlichen Ziele erreicht: Scores über 99% in allen Probleminstanzen, Durchschnittsscore über 99,5%. Der Rest ist Zugabe.

So richtig Bewegung scheint in den Bestwerten auch nicht mehr zu sein. Seit ich die Scores mitschreibe gab es nur drei Verbesserungen, jeweils im Bereich der letzten angezeigten Nachkommastelle.



  Profil  Quote  Link auf diesen Beitrag Link
Yggdrasil
Senior Letzter Besuch: im letzten Monat
Dabei seit: 01.07.2004
Mitteilungen: 846
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2019-08-11


2019-08-07 11:44 - Kitaktus in Beitrag No. 4 schreibt:
Es ist (leider?!) mal wieder so ein typisches "Simulated-Annealing"-Problem(*).

Hallo Kitakus,

ich habe mich auch mal an dem Problem mit diesem Ansatz versucht.
Sehe ich das richtig, dass man dabei nicht auf die Idee verfallen sollte, zwischendurch wieder auf reine Abstiegsverfahren zu wechseln, weil man damit nur wieder „in die lokalen Minima zurückrollt“?





  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6050
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2019-08-12


Für solche Probleme gibt es prinzipiell zwei Strategien:
a) Simulated-Annealing: Verbesserungen werden immer zugelassen. Verschlechterung nur mit einer bestimmten Wahrscheinlichkeit, wobei typischerweise die Wahrscheinlichkeit kleiner gewählt wird, wenn die Verschlechterung groß ist und mit der Zeit sinken sollte, damit man in Richtung Optimum driftet.(*)
(*) Eng verwandt: Threshold-Accepting - Verschlechterungen werden zugelassen, wenn sie nicht zu schlecht sind (über dem Threshold liegen). Der Threshold wird mit der Zeit angehoben.

Im "Endstadium" tritt dann der von dir beschriebene Effekt auf. Sind Verschlechterungen zu selten, so werden die meisten von ihnen in der nächsten Runde der lokalen Suche direkt wieder zurückgenommen. Man "rollt" ins lokale Optimum zurück.
Es gibt hier - unter dem Namen Tabu-Suche - Ansätze, genau das zu verhindern. Es gibt dann eine Liste von Suchschritten, die eine zeitlang nicht direkt zurückgenommen werden dürfen (also tabu sind).

b) Lokale Suche mit Störung: Es werden im Suchlauf nur Verbesserungen zugelassen. Ist ein lokales Optimum erreicht, stört man die Lösung (z.B. durch Permutation einiger Einträge) und startet dann die lokale Suche neu.

Man kann auch beide Strategien verknüpfen:
Man macht Simulated-Annealing, aber ein "Schritt" ist nicht der Übergang zu einem Nachbarn, sondern ein Schritt ist "Lösung stören und bis zum lokalen Optimum suchen". Dann entscheidet man nach dem Simulated-Anealing-Ansatz, ob man die Änderung behält, oder nicht.
Das ist so in etwa mein bisheriger Ansatz.

Übers Wochenende habe ich bei den meisten n (bei 14 von 20) damit noch (kleinere) Verbesserungen erreicht (ca. 15% der verbleibenden Abweichung zum Optimum). Ein bischen Potential gibt es noch, aber ganz große Sprünge werde ich damit wohl nicht machen (zumal mein Rechner so langsam sein Lebensende erreicht hat).



  Profil  Quote  Link auf diesen Beitrag Link
Yggdrasil
Senior Letzter Besuch: im letzten Monat
Dabei seit: 01.07.2004
Mitteilungen: 846
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2019-08-13


Danke für die Anregungen. Ich werde auch noch versuchen einen Ansatz der Form „Zufall + Optimierungen mit Tabus“ als Simulated-Annealing-Schritt einzubauen.
Derzeit bewege ich mich im Bereich >95% für große N und >98% für kleine N.
Da hat mein Raspberry Pi 3 also noch etwas zu rechnen für gute Resultate :)

Das du in der öffentlichen Liste keine Bewegung siehst kann auch daran liegen, dass Verbesserungen erst kurz vor Ablauf des Wettbewerbes eingereicht werden. Mir ist nicht bekannt, wie die Community diesbezüglich bei diesem Wettbewerb tickt, aber Zimmermans Seite/Kommentare läd/laden ja quasi dazu ein, nicht jede kleine Verbesserung zu posten.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6050
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2019-08-14


Ich möchte mich etwas korrigieren. Ein bisschen Bewegung ist in den besten Lösungen noch drin, aber es sind hauptsächlich Veränderungen in der letzten Nachkommastelle und da bei den Standings eine Stelle weniger angezeigt wird, sieht man dort fast nichts.

Hinsichtlich der erreichbaren Güte mit meinen Verfahren spielt die Problemgröße keine große Rolle.
Bei allen Problemen der Größe 18-30 liege ich im Bereich 99.35-99.55%. Bei den kleineren Problemen ist die Spreizung etwas größer 99.15-100%.
Mit lokaler Suche allein sollte man mit ein paar Versuchen so im Bereich 93-97% landen.



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6050
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2019-08-28


Ein kleines Update:
Mit Nachoptimieren (zusätzliche Betrachtung von 3-, 4- und 5-Austauschen) ließen sich die Ergebnisse etwas verbessern. Insbesondere eine optimale Lösung für N=11 ist dabei mit abgefallen.
Einen größeren Schritt bin ich weitergekommen, als ich am letzten Wochenende mal eine (eingeschränkte) Tabusuche programmiert habe. Die Idee ist, gezielt nach längeren Austausch-Zyklen zu suchen. Gegenüber einer normalen Tabusuche beschränke ich mich auf Austausch-Schritte, die einen vorhandenen Austauschzyklus verlängern: A rückt auf die Position von B, B auf die Position von C, C auf die Position von D usw.



  Profil  Quote  Link auf diesen Beitrag Link
woodstock68
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2016
Mitteilungen: 30
Aus: Karlsruhe, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2019-10-10 19:36


Den aktuellen Wettbewerb finde ich sehr faszinierend, da sich auch nach über zwei Monaten immer noch neue Dinge ausprobieren lassen und manchmal noch zu einer kleinen Verbesserung führen. Über meinen aktuellen 14. Platz will ich mich auch nicht beschweren ;-)

Mein Vorgehen ist ähnlich wie bei Kitaktus - zufällige Ausgangsanordnungen optimieren, dann leicht "stören", wieder optimieren usw.

@Kitaktus: 3er-Austauschungen kann ich auch für n=30 komplett untersuchen (läuft dann aber ein paar Stunden), aber 4er- oder gar 5er-Austauschungen muß man auf geschickt gewählte beschränken - ist bei dir auch so, oder?

Letzte Woche habe ich mich mit Visualisierungen der Lösungen beschäftigt (via matplotlib unter Python), was sehr schöne Muster erkennen lässt (Bilder kann ich hier nicht direkt zeigen, oder?)

@Yggdrasil: ich denke, die meisten Teilnehmer reichen gefundene Lösungen gleich ein. Da seit Ende August keine neue beste Lösung mehr eingereicht wurde, wäre es natürlich auch eine Strategie, diese bis zum Schluss geheim zu halten, um so noch Tomas und Martin vom ersten Platz zu verdrängen.

Sehr neugierig bin ich auf die Methoden, welche Tomas verwendet hat, um so schnell so ausgezeichnete Lösungen zu finden - er hatte sie ja im Prinzip nach einer oder zwei Wochen, bis auf ein paar kleine Verbesserungen.



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 998
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2019-10-12 18:02


Also ich bin zwischenzeitlich nicht mehr zu nennenswerten weiteren Verbesserungen gekommen, obwohl ich noch versucht habe, nach dem Simulated Annealing Prinzip vorzugehen. Mal gucken, zwei Wochen läuft der Wettbewerb noch, mal sehen, wer dann am Ende die Nase vorn hat.

Ist das nur bei mir so, dass die Al Zimmermann Webseite nicht erreichbar ist (gestern auch schon nicht)?

LG Primentus

Edit:
Ach ja, hab mich grad dran erinnert, dass es ja vor paar Wochen eine Benachrichtigung gab, dass man auf einen Alternativlink ausweichen soll.



  Profil  Quote  Link auf diesen Beitrag Link
Wally
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 02.11.2004
Mitteilungen: 8546
Aus: Dortmund, Old Europe
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2019-10-12 20:04


Wie ist denn der Alternativlink?

Wally



  Profil  Quote  Link auf diesen Beitrag Link
Primentus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.02.2016
Mitteilungen: 998
Aus: Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2019-10-12 20:30


Hallo Wally,

das ist dieser hier: Programming Contest
Reversing Nearness ist der aktuelle.

LG Primentus



  Profil  Quote  Link auf diesen Beitrag Link
Kay_S
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.03.2007
Mitteilungen: 1335
Aus: Koblenz (früher: Berlin)
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2019-10-12 23:07


Ich arbeite mich momentan bzgl. der Werte \(n\) von unten nach oben.
Mit meinem jetzigen Algo bin ich für \(n \leq 23\) sehr zufrieden, die Qualität der Ergebnisse für \(n = 24\) lässt aber zu wünschen übrig. Einige Probleme scheinen deutlich schwieriger zu sein als andere (auch kleinere).



  Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6050
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2019-10-12 23:25


2019-10-10 19:36 - woodstock68 in Beitrag No. 13 schreibt:
@Kitaktus: 3er-Austauschungen kann ich auch für n=30 komplett untersuchen (läuft dann aber ein paar Stunden), aber 4er- oder gar 5er-Austauschungen muß man auf geschickt gewählte beschränken - ist bei dir auch so, oder?
Ja, natürlich. Die Positionen der Token, oder die Werte auf den Token müssen nahe beieinander liegen. Wobei man dann "nah" je nach Problemgröße und Zahl der auszutauschenden Token wählen kann.


Letzte Woche habe ich mich mit Visualisierungen der Lösungen beschäftigt (via matplotlib unter Python), was sehr schöne Muster erkennen lässt
(Bilder kann ich hier nicht direkt zeigen, oder?)
Man darf halt keine Lösung daraus erkennen können.
Das es diverse Muster gibt, ist mir klar, aber ich habe den Aufwand der "händischen" Analyse gescheut. Ist halt ein Unterschied, ob ich Rechenzeit verbrauche, oder meine eigene Zeit.


@Yggdrasil: ich denke, die meisten Teilnehmer reichen gefundene Lösungen gleich ein. Da seit Ende August keine neue beste Lösung mehr eingereicht wurde, wäre es natürlich auch eine Strategie, diese bis zum Schluss geheim zu halten, um so noch Tomas und Martin vom ersten Platz zu verdrängen.
Da die Roh-Scores veröffentlicht werden, ist das Geheimhalten von neuen Bestwerten schon attraktiv, wenn man selbst nicht in Führung liegt. Andernfalls stürzen sich die weiter vorn platzierten genau auf diese eine Instanz und finden die richtige Lösung, bevor man selbst zur Spitze aufschließen konnte.
Andererseits, wenn ich eine Verbesserung hätte, würde ich sie sofort einreichen. Die Ehre, sie als erster gefunden zu haben, wäre mir wichtiger als die eher hypothetische Chance am Ende noch zu gewinnen.


Sehr neugierig bin ich auf die Methoden, welche Tomas verwendet hat, um so schnell so ausgezeichnete Lösungen zu finden - er hatte sie ja im Prinzip nach einer oder zwei Wochen, bis auf ein paar kleine Verbesserungen.
Na ja. Tomas kann ziemlich schnell ziemlich schnellen Code erzeugen und hat vermutlich auch einiges an Rechenkapazität zur Verfügung.
Ich hoffe, dass auch ein paar wirklich originelle Ideen eine Rolle spielen, denn den Aspekt "wer kann den gleichen Algorithmus einfach schneller machen", finde ich persönlich nicht so spannend(*).
Der Wettbewerb "Sums and Products II" war so ein Beispiel, bei dem wahrscheinlich alle 30-Punkte-Teilnehmer genau das gleiche programmiert haben.

(*) Das dürfen andere gerne anders sehen. Es ist ja schließlich ein "_Programmier_wettbewerb".

[Die Antwort wurde nach Beitrag No.16 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
woodstock68
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2016
Mitteilungen: 30
Aus: Karlsruhe, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2019-10-14 21:01


@Kay_S: ja, deine glatten 16 Punkte sind mir vor ein paar Tagen in der Rangliste aufgefallen. Inzwischen hast du ja noch für ein 17. n etwas eingereicht. Ich komme "nur" auf 13 n mit einem vollen Punkt, die 18 ist sehr sehr nahe dran. Da du wahrscheinlich auch Lösungen für die restlichen n im Vorrat hast, rechne ich Ende nächster Woche mit dir relativ weit oben.

@Kitaktus: genau diese Beobachtungen habe ich auch gemacht - wenn ich z.B. vier Tokens erfolgreich vertausche, liegen diese meist ganz nahe beieinander und lagen auch im Ausgangstorus ganz nahe beieinander.
Mit dem neuen Rekord veröffentlichen sehe ich es wie du - falls ich etwas finde, wird es sehr zeitnah eingereicht. Auf einen neuen Rekord für ein n mache ich mir allerdings aktuell keine Hoffnungen mehr.
Ich hoffe auch, dass Tomas mit einer Idee um die Ecke kommt, welche uns an die Stirn schlagen lässt und Sätze wie "ja klar, warum bin ich da nicht selber drauf gekommen" ausrufen lässt ;-)
Bei "Sums and Products II" war es so, dass wenn du wusstest, dass die Lösung durch ein Golomb-Lineal realisiert werden kann, nur noch reine Fleißarbeit übrig blieb ( de.wikipedia.org/wiki/Golomb-Lineal ). So mancher hat dann auch das Fortran-Programm von 1986 im Netz entdeckt...



  Profil  Quote  Link auf diesen Beitrag Link
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6050
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2019-10-15 10:56


@ Sums and Products II

Mathematisch gesehen ist nicht klar, dass man mit dem algebraischen Ansatz zu optimalen(!) Lösungen kommt.
Wenn man aber sieht, dass nach ein paar Tagen x Teilnehmer die gleiche Punktzahl haben, liegt ja nahe, dass es da einen allgemeingültigen Ansatz geben muss. Den sucht man dann, programmiert ihn nach und findet - wie erwartet - die gleichen Ergebnisse.
Ich befürchte, dass kaum einer ersthaft etwas anderes versucht hat. Daher hat der Wettbewerb praktisch keine neuen Erkenntnisse gebracht.



  Profil  Quote  Link auf diesen Beitrag Link
woodstock68
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2016
Mitteilungen: 30
Aus: Karlsruhe, Deutschland
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2019-10-15 20:45


@ Sums and Products II

Da die Aufgabe des Wettbewerbs nicht identisch mit der Definition eines Golomb-Lineals ist, hast du natürlich recht: ob damit die optimalen Lösungen gefunden wurden ist nicht sicher. Meine damaligen Ansätze VOR der Umsetzung mit Golomb-Linealen waren allerdings um Welten schlechter als die dann gefundenen Lösungen.

Allerdings hat der Wettbewerb Tomas und Gil zu weiteren Forschungen an Golomb-Linealen inspiriert, was auch nicht schlecht ist: cube20.org/golomb/

@ Reversing Nearness

Durch die Visualisierung ist mir folgendes aufgefallen: Ausgehend von meiner besten Lösung eines Grids "schüttele" ich diese ein wenig durch, realisiert durch 1-3 züfällige Vertauschungen von 2 Tokens. Danach laufen dann die Optimierungsschritte. Wenn dabei ein neuer Rekord gefunden wird, bestehen die Unterschiede zur vorherigen Lösung immer in EINER langen Kette von Verschiebungen (und evtl. zusätzlich gefundenen 3er- und 4er-Ketten durch separate Optimierungsschritte). Sowohl die Kette im aktuellen Grid wie auch die Position der zugehörigen Tokens im Initialgrid sind fast immer räumlich sehr nahe.



  Profil  Quote  Link auf diesen Beitrag Link
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]