Foren » 30. BwInf

• PaulJJ

  

  • 45 Beiträge
   

  17. April 2012 15:42:39 CEST

  Hallo,

   

  jetzt wo die zweite Runde vorbei ist, würde ich mich sehr dafür interessieren, wie ihr Aufgabe 3 gelöst habt. Ich persönlich habe mich damit recht schwer getan. Mein Bauchgefühl hat mir immer gesagt, dass es für das Berechnen des bestmöglichen Platzes eine effiziente und garantiert optimale Lösung gibt, aber diese habe ich während der gesamten Zeit nicht finden können. Ich habe das dann so gelöst, dass ich (nachdem das Lieblingsteam und alle sicher überholten und uneinholbaren Teams alles gewonnen haben) in allen verbleibenden Spielen jedem Team zufällig entweder 0 oder 1 Tor(e) gegeben habe. Diese zufälligen Ergebnisse habe ich dann so verändert, dass möglichst wenige Mannschaften dadurch vor das Lieblingsteam gelangen.

   

  Mit diesem Ansatz konnte in allen sechs Beispielfällen bestenfalls Platz 1 erreicht werden.

   

  Wie habt ihr es gemacht?

   

  Paul

• Lucas Elbert

  

  • 19 Beiträge
   

  17. April 2012 17:23:09 CEST

  Ganz ähnlich wie du :D. Habe auch keine Lösung gefunden, die effizient ist und garantiert in allen denkbaren Fällen das Optimum liefert. Aber vielleicht gibt es so eine auch nicht (vergleiche Meisterschaftsproblem 3-1-0 Regel). Ich hab mich also auf effizient (und meistens optimale Ergebnisse) beschränkt.

  Hab das ausgewählte Team und alle Teams, die nicht mehr einholbar sind bzw. die das ausgewählte Team nicht mehr einholen können, natürlich all ihre Spiele gewinnen lassen und den Rest dann mit einem evolutionären Algorithmus gelöst.

  Ebenfalls überall 1sten Platz erreicht.

   

  (Ich hoffe es war nun in Ordnung, nach dem 16.04, soetwas zu posten.)

   

  Lucas

  
  Dieser Beitrag wurde am 17. April 2012 18:09:12 CEST von Lucas Elbert bearbeitet
• Nata

  

  • 5 Beiträge
   

  20. April 2012 16:41:30 CEST

  Eine optimale Loesung kann ich fuer meinen Algo auch nicht garantieren, wobei ich kein Szenario finden konnte, bei dem er kein optimales Ergebnis gefunden hat.
  Im Grunde hab ich die Trivialspiele (Spiele der Mannschaft die gewinnen soll, solche von Mannschaften mit mehr Punkten oder solcher, die sie nie erreichen koennen) genauso geloesst wie ihr. Die Restlichen Mannschaften hab ich dann sortiert nach bei welcher Mannschaft (punkte(lieblingsteam)-punkte(irgendeinTeam)) / verbleibendeSpiele(irgendeinTeam) am geringsten war. Jedes der Spiele hab ich dann versuchtso zu spielen, dass insgesammt die wenigsten Punkte enstehen, wobei das aktuelle Team die Moeglichkeit bekommt, Punkte abzugeben (weil tendenziell andere Teams mehr Punkte aufnehmen koennen). Sollte es bei einem Team nicht moeglich sein, ein Spiel zu spielen, wird es nach oben gepushed, also gewinnt alle Spielle ausser die mit der lieblingsmannschaft.
• Lucas Elbert

  

  • 19 Beiträge
   

  21. April 2012 16:32:00 CEST

  Auch hier würden mich noch eure Ideen interessieren, die ihr hattet, um die Aufgabenstellung zu erweitern. Mir persönlich viel es bei den anderen Aufgaben etwas leichter sinnvolle Erweiterungen zu finden. Hier habe ich implementiert:
  
  1. Ein Spiel besteht nicht aus einem Mannschaftstripel, sondern einem n-Tupel von Mannschaften
  2. Die Regel, wie viele Punkte bei welchem Spielausgang verteilt werden (Standard: 5:2:1) kann variiert werden
• Maximilian J

  

  • 2 Beiträge
   

  22. April 2012 22:35:10 CEST

  Ich meine das Knotenüberdeckungsproblem auf das Problem reduziert zu haben. Die Aufgabe lässt sich mittels erschöpfender Suche lösen, wobei diese durch ein wenig Pruning relativ flott ist. Erweiterungen habe ich genau wie Luc as.

  
  Dieser Beitrag wurde am 23. April 2012 14:50:06 CEST von Maximilian J bearbeitet
• Tobi1992

  

  • 10 Beiträge
   

  23. April 2012 18:15:14 CEST

  ich hab noch als erweiterung, dass die form der mannschaften analysiert wird auf der basis ihrer bisher gezeigten leistung und dann die saison auf der grundlage der form logisch simuliert wird. Man kann die form seiner lieblingsmannschaft auch noch variieren
• MaTh

  

  • 1 Beiträge
   

  1. Mai 2012 17:44:39 CEST

  Mein Algo hat wie bei allen auch erst die Lieblingsmannschaft alle Spiele gewinnen lassen, den Rest hab ich per default auf unentschieden gesetzt (insgesamt kommen so am wenigsten Gesamtpunkte in die Tabelle)
  Dann hab ich alle Teams, die weniger Punkte als die Lieblingsmannschaft hatten, so viele Spiele gewinnen lassen, bis sie auf Punktegleichstand waren (den Spiele hab ich eine Wertung gegeben, damit sie in "sinnvollen" Spielen gewinnen).
  Danach von oben runter: die beste Mannschaft (falls nicht Favorit) durfte alle Spiele gewinnen, die Teams, die dadurch weniger Punkte als der Favorit hatten, haben wieder zu ihm aufgeholt usw.
  Abbruch des Algos, wenn der Favorit Platz 1 erreicht hat, und als Ausgabe wurden nur die Spiele explizit gezählt, die einen oder 2 Gewinner hatten (ausgenommen die Spiele des Favoriten), den Rest unter dem Punkt "unentschieden" zusammengefasst bzw. halt "Spiele des Favoriten". Noch ein kleiner Hinweis bezüglich der Teams, die gleich viele Punkte haben (also dass der Favorit insg. mehr Tore braucht als die).
  Als Erweiterung hab ich eine "realisitsche" Berechnung, also von jedem Team wird der Torschussschnitt ermittelt, falls noch keine Spiele gespielt wurden, wurde er auf den Schnitt aller Tore pro Mannschaft pro Spiel gesetzt, und so die Tabelle ausgefüllt.