Foren » 30. BwInf

• nicht mehr angemeldetes Mitglied

  
   

  5. Dezember 2011 18:07:36 CET

  Irgenwleche Vorschläge zur  Lösung der Städtepartneraufgabe

   

  ich hatte mir die mal überlegt, mein Freund hat dann versucht sie in PHP zu coden ist aber dann gescheitert :(

   

  ist die überhaupt mit "System" zu lösen oder is des stures Raten?

   

  MFG

   

  Jonas

• PaulJJ

  

  • 45 Beiträge
   

  5. Dezember 2011 20:44:31 CET

  Ich habe die Aufgabe nicht gelöst, aber ein System gibt es da bestimmt. Auf die schnelle fällt mir aber gerade nur ein, dass man alle trivialen Fälle sofort lösen kann, um die Probleminstanz zu verkleinern. Dabei ergeben sich evtl. neue triviale Fälle.
  
  Paul
• nicht mehr angemeldetes Mitglied

  
   

  5. Dezember 2011 20:52:35 CET

  wir habens mal so versucht:
  
  da gibts ja städte die nur eine partnerschaft haben oder kein fest ausrichten,
  
  die nimmt man als erstes dran, sodass sich die anzahl der feste auch bei den andren verringert,
  
  dann gibts wieder welche mit 2 partnerschaften die dann nur noch eine haben und somit auch verringert werden usw. usw.
  
  dann kamen wir an einen punkt wo dieses system nicht mehr weiterging... (halt bei der 1000 städtenetz abbildung ) :(
  
  so ist meine frage wer hat diese Aufgabe gemacht? und wenn ja wie?
  
  danke für deine meldung paul
• swante

  

  • 3 Beiträge
   

  7. Dezember 2011 20:07:57 CET

  Mein Programm trifft als Erstes die Entscheidungen, die offensichtlich sind, wie von Jonas beschrieben. Dann habe ich einen Genetischen Algorithmus (jedes Partnerschaftsfest ein Gen) mit Mutation und Cross-Over verwendet, um die Anzahl der Fehler auf ca. 15 zu reduzieren; da das auch noch nicht gereicht hat, habe ich als letztes auch noch den Graph-Algorithmus der Breitensuche ueber die Staedte laufen lassen, z.B. : Richtet Stadt A mehr Feste aus, als es kann, und Stadt E koennte noch mehr Feste ausrichten, als sie es derzeit tut, und es gilt A->B->C->D->E (d.h. A richtet Fest fuer B aus etc.), wird dieser (durch die Breitensuche gefundener) Pfad 'umgekehrt', d.h.: A<-B<-C<-D<-E. Durch mehrmalige Anwendung dieses Prinzip kam ich letztendlich auf 0 Fehler ;)
• Julien Schmidt

  

  • 7 Beiträge
   

  8. Dezember 2011 18:10:04 CET

  Hier sind die entsprechenden Seiten unserer Einsendung. Ich hätte die Seiten ja gerne als PDF exportiert, aber leider kann man ja hier im Forum keine Datein anhängen, daher hier in Bildform:

   

  Großansicht:

  http://www.einstieg-informatik.de/community/public/forum_post/48/01/0147_0856.png

  
  Dieser Beitrag wurde am 8. Dezember 2011 18:15:14 CET von Julien Schmidt bearbeitet

  
• nicht mehr angemeldetes Mitglied

  
   

  8. Dezember 2011 19:29:38 CET

  cool danke! also wahren wir schon mal auf der richtigen Fährte :P
  
  - Bäume und Graphen kommen erst in 11_2 dran XD
  
• Wolfgang Pohl

  

  • Moderator
  • 391 Beiträge
   

  8. Dezember 2011 20:02:27 CET

  Jonas Leeb said:
  Bäume und Graphen kommen erst in 11_2 dran XD

  Das ist eine interessante Anmerkung. Einerseits kann ich das gut verstehen. Von der Schule kennt man das: da kommt in einer Klausur nichts vor, was im Unterricht noch nicht behandelt wurde. Beim BwInf sind wir aber der Meinung, dass bei einem Leistungswettbewerb erwartet werden kann, dass man sich aus Eigeninteresse in ein Gebiet vertieft und mehr macht als im Unterricht. Wer Leistungssport betreibt, geht auch extra trainieren und kommt mit dem Schulsport nicht hin. 

   

  Vermutlich machen die meisten BwInf-Teilnehmer auch mehr, als der Informatik-Unterricht verlangt. Eventuell aber geht dieses mehr eher in die Richtung, dass man programmiert und sich mit neuen Sprachen und Entwicklungs-Tools auseinandersetzt, als dass man sich mal ein Grundlagenbuch schnappt. Das ist überhaupt kein Vorwurf in irgendeine Richtung (erst recht nich an dich, Jonas), sonder einfach ein Gedanke. Ich packe mir im Zweifel an die eigene Nase: Wir schaffen es nicht, das Interesse am "mehr machen" in Informatik in die (unserer Meinung nach) "richtigen" Bahnen zu lenken. Wobei wir überhaupt nichts gegen gute praktische Kenntnisse haben. Die sind wichtig und Voraussetzung dafür, dass Informatik richtig Spaß macht.

   

  Übrigens konnte man auch Aufgabe 5 ohne konkrete Kenntnisse von Graphen bzw. Graphentheorie lösen. Das ging auch auf mehr oder weniger "intuitive" Weise. Ihr werdet es in den Lösungshinweisen nachlesen können.

  
  Dieser Beitrag wurde am 8. Dezember 2011 20:03:39 CET von Wolfgang Pohl bearbeitet
• Julien Schmidt

  

  • 7 Beiträge
   

  8. Dezember 2011 22:58:55 CET

  In NRW/G9 (13 Jahrgangsstufen) wird zumindest bei uns das Thema Graphen separat von Bäumen erst in 13.1 behandelt. Und das auch nur im Leistungskurs!

  
  Dieser Beitrag wurde am 8. Dezember 2011 23:06:22 CET von Julien Schmidt bearbeitet
• JanG

  

  • 9 Beiträge
   

  11. Dezember 2011 20:28:49 CET

  @Julien Schmidt: Genau die gleiche Idee habe ich auch implementiert (aber etwas abgewandelt). Nur so aus Interesse: Wie lange braucht dein Programm zur Lösung des größeren Beispiels?
• Julien Schmidt

  

  • 7 Beiträge
   

  12. Dezember 2011 08:22:45 CET

  Implementiert in Java hat die Verteilung an sich (ohne Parsen der Listen) bei dem großen Beispiel von der BwInf-Website auf einem halbwegs aktuellen PC eine Laufzeit von unter einer Sekunde. Bei dem kleinen Beispiel waren die Messchwankungen meist größer als die Laufzeit selbst ;)
• JanG

  

  • 9 Beiträge
   

  12. Dezember 2011 08:34:59 CET

  Bei mir war es ähnlich. Mein PC (intel core i5 Prozessor (4 cores) mit je 2,67GHz Taktfrequenz) hat ca. 75ms für das größere Beispiel gebraucht. Ich habe zuerst alle Trivialfälle rekursiv vereinfacht (ca. 1/3 der ausstehenden Entscheidungen kann man bei dem größeren Beispiel bereits treffen mit der Gewissheit, dass man keinen Fehler gemacht hat). Anschließend habe ich mit einer Greedy Heuristik die Fitness von den einzelnen Städten berechnet und die Feste dann verteilt. Danach blieben 7 Problemfälle übrig, die ich dann durch BFS, so wie swante es beschrieben hat, gelöst habe.
• Tobi1992

  

  • 10 Beiträge
   

  12. Dezember 2011 19:35:59 CET

  Also meine Idee war es zuerst in einem Wert auszudrücken, wie "nötig" es eine Stadt hat ein Fest ausgerichtet zu bekommen. Der Wert setzt sich aus der Anzahl der Partnerstädte Minus der Anzahl der Feste die die Stadt ausrichten kann zusammen. Hat die Stadt einen hohen Wert heißt das, dass viele andere Städte für die Stadt ein Fest ausrichten müssen.
  Bei meiner Methode suche ich mir die Stadt mit dem geringsten Wert aus, also die Stadt die viele Feste im Vergleich zu der Anzahl der Partnerstädte ausrichten kann und lasse sie für diejenigen Partnerstädte ein Fest ausrichten, diese einen ziemlich großen Wert haben. So lässt sich eine erste Annäherung unter Einhaltung der obergrenzen erzeugen.
  Im zweiten Schritt werden alle Feste die noch nicht veranstalltet sind versucht einzelt zu organisieren. Die Anzahl der Feste die noch ausgerichtet werden müssen, stimmt mit der Anzahl der noch freien Feste bei anderen Städten überein. Nun suche ich rekursiv die Städte diese noch Feste ausrichten können, ausgehend von einer der beiden Städte dessen Fest organisiert werden müssen, werden solang die Ausrichter vertauscht bis eine Stadt gefunden ist, diese eben noch ein Festival besitzt. Also klingt jetzt erstmal bisschen verwirrend aber ist ganz einfach - Beispiel:
  Stadt A + Stadt B -> Fest muss organisiert werden, aber kann nicht ausgerichtet werden da sonst die Obergrenze einer der beiden Städte überschritten wird.
  Stadt D -> kann noch ein Fest ausrichten hat aber schon mit jeder seiner Partnerstädte ein Fest
  Nun passiert folgendes:
  Stadt B richtet ein Fest für Stadt C aus - der Ausrichter wird getauscht -> Stadt B kann ein Fest jetzt wieder ausrichten und richtet es für Stadt A aus
  Stadt C hat nun die Obergrenze überschritten, richtet aber ein Fest für Stadt D aus -> Der Ausrichter wird getauscht und alle Obergrenzen sind wieder eingehalten.
  
  Das kleine Beispiel hat mein Programm sofort berechnet (also t < 1s). Beim großen Beispiel benötigt es ca. 5 Sekunden.