Foren » 36. BwInf

• Thomas Leineweber

  

  • 230 Beiträge
   

  9. April 2018 12:30:31 CEST

  Hallo zusammen,
  heute, Montag, 09.04.2018, ist Einsendeschluss für die zweite Runde. Nach dem Einsendeschluss kann auch gerne über die konkreten Lösungsideen und deren Umsetzungen diskutiert werden. Dann können die Einsendungen gerne auch online für andere zur Verfügung gestellt werden. Das PMS wird voraussichtlich irgendwann in der Nacht vom Montag zum Dienstag geschlossen. Um auf Nummer sicher zu gehen, sollte mit der Veröffentlichung von Einsendungen bis zum Dienstag Abend gewartet werden.
  
  Wenn Ihr Eure Einsendung online gestellt habt, wäre es auch ganz gut, hier einen Link zu posten. Dann gibt es auch die Möglichkeit, über verschiedenen Lösungen zu diskutieren. Die Diskussion kann hier aber auch im IRC (siehe andere Topics hier im Forum) stattfinden.
  
  Viele Grüße
  Thomas
• nicht mehr angemeldetes Mitglied

  
   

  10. April 2018 18:25:32 CEST

  Dann fang ich mal an... Ich habe Aufgabe 1 (in Java) und Aufgabe 2 (in Python) bearbeitet. Aufgabe 1 habe ich (wie wahrscheinlich viele andere auch) mit Backtracking und relativ gutem Pruning gelöst, sodass bei mir bis n = 14 eine maximal hohe Mauer in annehmbarer Zeit berechnet werden kann. Aufgabe 2 habe ich in ein Minimum-Cut-Problem umformuliert, was zu ziemlich guten Ergebnissen führt. Meine Einsendung habe ich auf GitHub gestellt ( https://github.com/laugengebaeck/BwInf-36-R2 ). Übrigens habe ich zufällig genau 42 Seiten Dokumentation.  Es würde mich interessieren, wie ihr die Aufgaben gelöst habt und wer bei Aufgabe 1 das höchste n hat.

  
  Dieser Beitrag wurde am 12. September 2018 10:32:41 CEST von nicht mehr angemeldetes Mitglied bearbeitet
• Henning Hillebrandt

  

  • 8 Beiträge
   

  10. April 2018 19:34:43 CEST

  Ich bin in Aufgabe 1 bis n = 17 gekommen (mit Ausnahme von n = 16). Dafür habe ich auch Backtracking und Pruning verwendet. Mich würde auch interessieren, wie hoch eure Mauern so werden konnten. :)
  Dieser Beitrag wurde am 10. April 2018 19:41:54 CEST von Henning Hillebrandt bearbeitet
• Simon Döring

  

  • 45 Beiträge
   

  10. April 2018 19:42:12 CEST

  Ich komme bei Aufgabe 1 auf n = 19.
  Grundlegend verwende ich auch einen Backtracking-Algorithmus, welcher bei bestimmten Situationen "Äste" des Suchbaumes abkürzt.
  
  Bei Aufgabe 2habe ich versucht den "Weg" mit den kleinsten Kosten zu finden, welcher durch die Matrix führt.
  Ein "Weg" ist hierbei eine Abfolge von Mauer, welche am Ende mit einander verbunden sind.
  Eine Mauer ist ein Objekt, welches sicher zwischen zwei Elementen der Matrix befindet. Jede Mauer muss mindestens den Wert 1 haben, d.h., dass die Differenz der Objekte, zwischen welche sie sich befindet, mindestens 1 sein muss.
  
  Hiefür habe ich eine Mischung aus den Dijkstra-Algorithmus und den Simplex-Algorithmus verwendet.
  
  Geschrieben in C++
• Johannes Häring

  

  • 1 Beiträge
   

  11. April 2018 20:42:43 CEST

  Habe bei Aufgabe 1 n = 36 in 20 Sekunden und n = 38 in 30 Minuten geschafft. Habe dazu auch einen Backtracking-Algorithmus genutzt und immer versucht die nächste freie Fugen-Position zu füllen.
  Habe auch Abbrech-Kriterien genutzt, um möglichst früh Zweige abzulehnen.
  
  Außerdem habe ich Aufgabe 2 gemacht, habe hier auch einen Backtracking-Algorithmus genutzt. Ein Schritt bedeutet, dass man auf das nächste Feld wechselt und dabei eine Barriere schafft, also einen Meter Höhenunterschied erschafft.
  Das Problem habe ich in sofern vereinfacht, dass ich nur eine Umschaufelaktion machen kann, um eine Barriere zu schaffen.
  Zusätzlich habe ich noch Heuristiken verwendet.
  Meine Ergebnisse sind:
  wildschwein1: 628,7€
  wildschwein2: 600,0€
  wildschwein3: 307,5€
  wildschwein4: 351,7€
  wildschwein5: 410,8€
• Gabriel Dengler

  

  • 31 Beiträge
   

  4. Juni 2018 23:39:34 CEST

  Es ist zwar schon eine Zeit her, dass Einsendeschluss war, da allerdings wenige ihre Einsendung öffentlich gestellt haben und gar keine Einsendung die dritte Aufgabe behandelt, stelle ich auch noch meine Einsendung öffentlich: https://1drv.ms/f/s!AnkfQ2-GMfyUlhhi-7ub11HRdk-S
  
  Bearbeitet habe ich die Aufgaben 1 und 3.
  
  LG Gabriel
  Dieser Beitrag wurde am 4. Juni 2018 23:42:03 CEST von Gabriel Dengler bearbeitet