Matroids Matheplanet Forum Index
Moderiert von viertel
Matroids Matheplanet Forum Index » Rätsel und Knobeleien (Knobelecke) » Eine Aufgabe aus der Optimierungsmeisterschaft 2009 zum Lösen
Autor
Kein bestimmter Bereich Eine Aufgabe aus der Optimierungsmeisterschaft 2009 zum Lösen
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Themenstart: 2022-01-01

Hallo Leute! https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_2009_Aufgabe3_1_Bild1_kleiner.jpg https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_2009_Aufgabe3_1_Bild2_kleiner.jpg Es gab im Jahr 2009 eine Optimierungsmeisterschaft (Logic Masters). Dazu sollten Aufgaben von Hand in einer bestimmten Zeit gelöst werden. Die Aufgabenstellungen und später Lösungen waren im Internet verfügbar. Das Ziel war bei mehreren (oder nur einer) Aufgabe(n) möglichst viele Punkte zu erreichen. Hier nun eine Aufgabe. Gesucht sind Lösungen dazu. Ich selbst habe mit einem Computer nach Lösungen geschaut - es geht aber auch von Hand. Selbst habe ich nie nach Lösungen von Hand geschaut. https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_2009_Aufgabe3_1_Bild3_eine_L_sung.jpg Anbei eine Lösung mit 3498 Punkten. Es gibt aber auch Lösungen mit mehr als 3500 Punkten. Wer möchte kann ja nach Lösungen suchen! Das Feld (zeilenweise von links oben nach rechts unten) \showon 1 3 5 2 8 4 7 3 4 3 2 7 5 3 6 1 5 4 3 5 5 3 5 4 5 6 6 4 5 2 7 6 1 4 6 4 8 3 1 4 7 2 6 4 4 2 7 1 5 7 6 4 3 6 5 6 4 2 6 2 8 2 6 7 3 5 3 1 4 7 4 3 7 5 6 5 8 4 6 4 6 4 3 0 6 7 1 4 6 5 3 4 7 4 2 6 2 3 6 5 2 1 7 4 5 6 1 7 2 6 5 4 3 6 2 4 7 7 3 6 3 4 6 4 2 7 3 6 1 5 4 5 4 7 6 5 7 3 6 4 7 6 2 8 1 6 3 5 2 5 3 7 4 7 2 5 3 4 5 1 7 8 6 2 5 3 5 8 4 \showoff Viele Grüße Ronald


   Profil
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.1, eingetragen 2022-01-13

ich hab jetzt die inneren u-boote gegen den achten schlepper getauscht---> 3519 dabei auch wieder max 1 schiff an jeder bohrinsel... "jedes schiff darf eine bohrinsel diagonal berühren" schliesst ja nicht aus das mehrere schiffe an einer bohrinsel liegen ??? (hoffe ich) das zählen ist ziemlich schwierig, ich zähle n x rund um jedes schiff und muss dann die diagonalen anlegerfelder wieder abziehen, mit der zählweise konnte ich dein set bestätigen \showon https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_del3519.jpg \showoff


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.2, vom Themenstarter, eingetragen 2022-01-13

Hallo haribo! Ich fürchte, Deine Lösung passt nicht! Es gilt Bedingung 3: "jedes Schiff darf max. an eine Bohrinsel diagonal andocken." Ich überlege gerade ob Deine Lösung doch geht... Doch sie müsste gehen - ich habe Lösungen gesehen wo auch 2 Schiffe an einer Bohrinsel liegen. Aber ich hatte mich vor Jahren mal mit dieser Optimierungsaufgabe beschäftigt! Da mir persönlich das manuelle Zählen zu anstrengend erschien, habe ich selbst nur nach mit Computerhilfe generierten Lösungen geschaut. Ein von mir probiertes Lösungsverfahren funktioniert zwar ist aber zu langsam: Backtracking - starte links oben und fülle die Felder mit Schiffen/Bohrinseln/Leerfeldern Dazu nutze Richtung waagerecht oder senkrecht für die Typen von Schiffen/... und probiere alle Typen pro Feld durch. U-Boote, Bohrinseln und Leerfelder haben nur eine Richtung. Viele Grüße Ronald


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.3, eingetragen 2022-01-13

kennst du das maximum? [Die Antwort wurde nach Beitrag No.1 begonnen.]


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.4, vom Themenstarter, eingetragen 2022-01-13

Das Maximum kenne ich bisher nicht, die beste mir bekannte Lösung beträgt 3545. Das ist die beste Lösung die damals im Wettbewerb von einem Teilnehmer gefunden wurde.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.5, eingetragen 2022-01-13

ist halt die frage ob eine bohrinsel ein "schiff" ist, ich denke nicht weil sie nicht selber fahren kann hab doch beim abziehen einen fehler oben drin, correktur 1519, ich ändere es oben,


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.6, vom Themenstarter, eingetragen 2022-01-13

Ich denke Bohrinsel zählt nicht als Schiff - ich habe auch schon eine Lösung mit 2 Schiffen an einer Bohrinsel gesehen. Diese Lösung wurde von den Aufgabenstellern erlaubt. Hier mal die beste mir bekannte Lösung: https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/15578_Schiffe_Opt05_3545_kleiner.jpg Ob es noch bessere Lösungen gibt, weiß ich nicht. Für mich ist es eine interessante Aufgabe - von Hand oder mit Computerhilfe gute Lösungen zu finden!


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.7, eingetragen 2022-01-14

die zählerei ist ziemlich komplex und damit fehlerträchtig, drum finde ich das interessanteste bisher, zu überlegen wie man zählt ich zähle, bei der dir bekannten besten lösung, mit 3563 etwas mehr als du angibst, tya nun finden wir mal nen fehler... das ist schon recht müssig und keineswegs ausgeschlossen dass ich versehentlich irgendwo etwas verschoben habe und falschen felder zähle... reine addierfehler dürfte ich nicht haben https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_del3563.JPG


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.8, vom Themenstarter, eingetragen 2022-01-14

Hallo haribo! Ich schau dann noch auf Deine Lösungen. Ich habe Lösungen meist so gespeichert: - Typen von Schiffen etc. mit Position auf Brett mit Richtung Dann habe ich Kollisionen berechnet -> unzulässige Überlappungen etc. Falls die Kollisionen bei 0 sind ist die Lösung zulässig. Dann berechne die Zielfunktion. Viele Grüße Ronald


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.9, eingetragen 2022-01-15

Nur kommen wir derzeit bei gleichen Positionen zu unterschiedlichen Summen! 3563 vs 3545 Davon kam maximal eine den zählregeln entsprechen


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.10, vom Themenstarter, eingetragen 2022-01-15

Die 3545 haben die Leute, die den Wettbewerb veranstaltet haben, gemessen und ich auch als ich diese Lösung bei mir getestet habe. Ich habe dafür ein Programm.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.11, eingetragen 2022-01-15

tya den fehler sollten wir irgendwie finden, ich rechne auch nach bestem wissen und gewissen, und komme mit verschiedenen ansätzen mehrmals auf 3563 die wasserwerte zwischen dir und mir kann man gut per bild-überlagerung vergleichen, die sind exakt gleich, das dürfte also stimmen https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_delueberlagert.JPG -ich hab jetzt auf deine darstellungs/berechnungsweise umgestellt und also die wasserwerte neben den schiffen im obersten feld dargestellt -darunter ein feld mit den anzahlen der umliegenden schiffsfeldern und -darunter die feldweise multiplikation der rechenwerte (wasserwerte x schiffsfelder) erstellt, nebst zeilenweiser summen und dann gesamtsumme kannst du irgendwie die gleichen tabellen deines programms erstellen? oder fals nicht, kann irgendwer meine "summe umliegender schiffsfelder" überprüfen? (viele augen sehen mehr als zwei) die differenz im ergebnis beträgt 18, also muss wohl irgendwo 3*6 od 2*9 different sein, aber wo verdammte axt? https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_delumliegendefelder.JPG corrigierte version


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.12, vom Themenstarter, eingetragen 2022-01-15

Hallo, benutzt habe ich ein Zählprogramm (siehe unten) das - eine 17x17 Matrix einliest (x,y 3 bis 15 mit Zahlwerten, Rest 0) - eine Lösung mit Typ(1 Bohrinsel, 2 Tanker, 3 bis 5 Schiffe, 6 Uboot, Koordinaten, Richtung (1 waagerecht; 2 senkrecht) - Ausgabe Kollisionen (Schiffe überlappen sich in Lösung etc.) - Ausgabe der gespiegelten Lösung (oben und unten gespiegelt) - Ausgabe der Punktzahl Die genaue Funktionsweise der Zählung müsste ich erst wieder nachvollziehen, da es schon lange her ist... \showon der Plan mit je 2 leeren Randfeldern \sourceon Opti05Plan17.txt 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 5 2 8 4 7 3 4 3 2 7 5 0 0 0 0 3 6 1 5 4 3 5 5 3 5 4 5 6 0 0 0 0 6 4 5 2 7 6 1 4 6 4 8 3 1 0 0 0 0 4 7 2 6 4 4 2 7 1 5 7 6 4 0 0 0 0 3 6 5 6 4 2 6 2 8 2 6 7 3 0 0 0 0 5 3 1 4 7 4 3 7 5 6 5 8 4 0 0 0 0 6 4 6 4 3 0 6 7 1 4 6 5 3 0 0 0 0 4 7 4 2 6 2 3 6 5 2 1 7 4 0 0 0 0 5 6 1 7 2 6 5 4 3 6 2 4 7 0 0 0 0 7 3 6 3 4 6 4 2 7 3 6 1 5 0 0 0 0 4 5 4 7 6 5 7 3 6 4 7 6 2 0 0 0 0 8 1 6 3 5 2 5 3 7 4 7 2 5 0 0 0 0 3 4 5 1 7 8 6 2 5 3 5 8 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \sourceoff \showoff \showon Lösung mit 3545 Punkten \sourceon Lsg01.txt 24 1 1 8 1 1 2 3 1 1 10 12 1 2 4 9 2 2 5 3 2 3 5 11 2 3 5 13 2 3 10 5 1 3 10 10 2 4 1 6 2 4 1 11 2 4 3 1 2 4 5 5 1 4 7 1 2 4 11 1 1 5 1 1 1 5 2 13 2 5 7 5 2 5 7 7 2 5 12 6 2 5 12 8 2 5 13 1 1 5 13 12 1 6 13 4 1 \sourceoff \showoff \showon Opti05verifyLsg.for \sourceon Fortran program Opti05verifyLsg implicit none integer wert(17,17),wert2(17,17),schiffe(100,4),belegung(17,17) integer ug(6),og(6) integer slots,az,bsp,i,j,zf,zf2,kolli,typkolli,bigkolli double precision faktor,faktor2,faktor3 common /rp1/ slots common /rp2/ faktor common /rp3/ faktor2 common /rp4/ faktor3 common /rp5/ az common /rp6/ bsp c slots = 26 c fak = 500 faktor = 240 c fak2 = 250 faktor2 = 120 c fak3 = 125 faktor3 = 60 az = 1000000 c bsp = 4 ug(1) = 3 ug(2) = 2 ug(3) = 0 ug(4) = 0 ug(5) = 0 ug(6) = 0 og(1) = 3 og(2) = 2 og(3) = 4 og(4) = 6 og(5) = 8 og(6) = 4 open(11,file = 'Opti05Plan17.txt') do 100 i = 1,17 do 200 j = 1,17 read (11,*) wert(i,j) belegung(i,j) = 0 200 continue 100 continue close(11) c berechne gsepiegelten Plan do 300 i = 1,17 do 400 j = 1,17 wert2(i,j) = wert(18-i,j) 400 continue 300 continue bsp = 01 if (bsp == 1) then open(22,file = 'Lsg01.txt') endif if (bsp == 2) then open(22,file = 'Lsg02.txt') endif if (bsp == 3) then open(22,file = 'Lsg03.txt') endif if (bsp == 4) then open(22,file = 'Lsg04.txt') endif if (bsp == 5) then open(22,file = 'Lsg05.txt') endif if (bsp == 6) then open(22,file = 'Lsg06.txt') endif if (bsp == 7) then open(22,file = 'Lsg07.txt') endif if (bsp == 8) then open(22,file = 'Lsg08.txt') endif if (bsp == 9) then open(22,file = 'Lsg09.txt') endif if (bsp == 10) then open(22,file = 'Lsg10.txt') endif read(22,*) slots do 1000 i = 1,slots read(22,*) schiffe(i,1) read(22,*) schiffe(i,2) schiffe(i,2) = schiffe(i,2) + 2 read(22,*) schiffe(i,3) schiffe(i,3) = schiffe(i,3) + 2 read(22,*) schiffe(i,4) 1000 continue close(22) call erzeuge_plan(schiffe,slots,belegung,ug,og, c bigkolli,typkolli,kolli) call berechne_zf(belegung,wert,faktor,faktor2,faktor3, c bigkolli,typkolli,kolli,zf) call berechne_zf(belegung,wert2,faktor,faktor2,faktor3, c bigkolli,typkolli,kolli,zf2) print *,'Plan' call ausgabe(wert) print *,'Plan (gespiegelt)' call ausgabe(wert2) print *,'Bsp = ',bsp call ausgabe(belegung) print *,'Zielfunktion ',zf print *,'bigkolli ',bigkolli,' // typkolli ',typkolli,' // kolli ' c ,kolli print *,'Zielfunktion (gespiegelter Plan)',zf2 end c ***************************************** c bilde belegung und kollis aus "schiffe" c ***************************************** subroutine erzeuge_plan(schiffe,slots,belegung,ug,og, c bigkolli,typkolli,kolli) implicit none integer belegung(17,17),schiffe(100,4) integer su(6),ug(6),og(6) integer bigkolli,typkolli,kolli,slots integer zeile,spalte,i,summebohr,richtung,laenge,merk integer ugz,ogz,ugs,ogs bigkolli = 0 typkolli = 0 kolli = 0 do 100 zeile = 1,17 do 200 spalte = 1,17 belegung(zeile,spalte) = 0 200 continue 100 continue c (a) Typkolli do 1000 i = 1,6 su(i) = 0 1000 continue do 1100 i = 1,slots merk = schiffe(i,1) if (merk > 0) then su(merk) = su(merk) + 1 endif 1100 continue do 1200 i = 1,6 if (og(i) < su(i)) then typkolli = typkolli + (su(i)-og(i)) endif if (ug(i) > su(i)) then typkolli = typkolli + (ug(i)-su(i)) endif 1200 continue c (b) belege felder c (1) belege Bohrinseln do 2000 i = 1,slots if (schiffe(i,1) == 1) then ugz = schiffe(i,2) ogz = ugz + 1 ugs = schiffe(i,3) ogs = ugs + 1 do 2100 zeile = ugz,ogz do 2200 spalte = ugs,ogs if (belegung(zeile,spalte) == 0) then belegung(zeile,spalte) = 1 else bigkolli = bigkolli + 1 endif 2200 continue 2100 continue c (1) kolli Einer do 2300 spalte = ugs-1,ogs if (belegung(ugz-1,spalte).ne.0) then kolli = kolli + 1 endif 2300 continue do 2400 zeile = ugz-1,ogz if (belegung(zeile,ogs+1).ne.0) then kolli = kolli + 1 endif 2400 continue do 2500 spalte = ugs,ogs+1 if (belegung(ogz+1,spalte).ne.0) then kolli = kolli + 1 endif 2500 continue do 2600 zeile = ugz,ogz+1 if (belegung(zeile,ugs-1).ne.0) then kolli = kolli + 1 endif 2600 continue c (2) kolli Zweier do 2700 spalte = ugs-2,ogs if (belegung(ugz-2,spalte)==1) then kolli = kolli + 1 endif 2700 continue do 2800 zeile = ugz-2,ogz if (belegung(zeile,ogs+2)==1) then kolli = kolli + 1 endif 2800 continue do 2900 spalte = ugs,ogs+2 if (belegung(ogz+2,spalte)==1) then kolli = kolli + 1 endif 2900 continue do 3000 zeile = ugz,ogz+2 if (belegung(zeile,ugs-2)==1) then kolli = kolli + 1 endif 3000 continue c (3) Abstand 2 von Mitte? do 3100 spalte = 7,9 if (belegung(7,spalte)==1) then kolli = kolli + 1 endif 3100 continue do 3200 zeile = 7,10 if (belegung(zeile,10)==1) then kolli = kolli + 1 endif 3200 continue do 3300 spalte = 7,10 if (belegung(11,spalte)==1) then kolli = kolli + 1 endif 3300 continue do 3400 zeile = 8,11 if (belegung(zeile,6)==1) then kolli = kolli + 1 endif 3400 continue c (4) Abstand 1 von Mitte? do 3500 spalte = 7,8 if (belegung(8,spalte)==1) then kolli = kolli + 1 endif 3500 continue do 3600 zeile = 8,9 if (belegung(zeile,9)==1) then kolli = kolli + 1 endif 3600 continue do 3700 spalte = 8,9 if (belegung(10,spalte)==1) then kolli = kolli + 1 endif 3700 continue do 3800 zeile = 9,10 if (belegung(zeile,7)==1) then kolli = kolli + 1 endif 3800 continue endif 2000 continue c (c) belege Felder ohne Bohr do 4000 i = 1,slots if (schiffe(i,1) > 1) then laenge = 6-schiffe(i,1) richtung = schiffe(i,4) if (richtung == 1) then ugz = schiffe(i,2) ogz = ugz ugs = schiffe(i,3) ogs = ugs+laenge else ugz = schiffe(i,2) ogz = ugz+laenge ugs = schiffe(i,3) ogs = ugs endif do 4100 zeile = ugz,ogz do 4200 spalte = ugs,ogs if (belegung(zeile,spalte) == 0) then belegung(zeile,spalte) = schiffe(i,1) else bigkolli = bigkolli + 1 endif 4200 continue 4100 continue c (1) kolli Einer ohne Eckfelder do 4300 spalte = ugs,ogs if (belegung(ugz-1,spalte).ne.0) then kolli = kolli + 1 endif 4300 continue do 4400 zeile = ugz,ogz if (belegung(zeile,ogs+1).ne.0) then kolli = kolli + 1 endif 4400 continue do 4500 spalte = ugs,ogs if (belegung(ogz+1,spalte).ne.0) then kolli = kolli + 1 endif 4500 continue do 4600 zeile = ugz,ogz if (belegung(zeile,ugs-1).ne.0) then kolli = kolli + 1 endif 4600 continue c (2) Kolli Eckfelder summebohr = 0 if (belegung(ugz-1,ugs-1) == 1) then summebohr = summebohr + 1 endif if (belegung(ugz-1,ogs+1) == 1) then summebohr = summebohr + 1 endif if (belegung(ogz+1,ugs-1) == 1) then summebohr = summebohr + 1 endif if (belegung(ogz+1,ogs+1) == 1) then summebohr = summebohr + 1 endif if (summebohr > 1) then kolli = kolli + summebohr-1 endif if (belegung(ugz-1,ugs-1) > 1) then kolli = kolli + 1 endif if (belegung(ugz-1,ogs+1) > 1) then kolli = kolli + 1 endif if (belegung(ogz+1,ugs-1) > 1) then kolli = kolli + 1 endif if (belegung(ogz+1,ogs+1) > 1) then kolli = kolli + 1 endif c (3) Abstand von Mitte? do 4700 spalte = 7,8 if (belegung(8,spalte)<5.and. c belegung(8,spalte)>0) then kolli = kolli + 1 endif 4700 continue do 4800 zeile = 8,9 if (belegung(zeile,9)<5.and. c belegung(zeile,9)>0) then kolli = kolli + 1 endif 4800 continue do 4900 spalte = 8,9 if (belegung(10,spalte)<5.and. c belegung(10,spalte)>0) then kolli = kolli + 1 endif 4900 continue do 5000 zeile = 9,10 if (belegung(zeile,7)<5.and. c belegung(zeile,7)>0) then kolli = kolli + 1 endif 5000 continue endif 4000 continue if (belegung(9,8).ne.0) then kolli = kolli + 1 endif end c ********************************** c passt aktuelles Schiff aufs Brett? c ********************************** subroutine zulaessig(typ,zeile,spalte,richtung,erg) implicit none integer typ,zeile,spalte,richtung,laenge,x,y,erg erg = 1 if (zeile<3.or.spalte<3.or.zeile>15.or.spalte>15) then erg = 0 return endif if (typ == 1) then c Bohrinsel laenge = 1 x = zeile+1 y = spalte+1 else c Rest laenge = 6-typ if (richtung == 1) then x = zeile y = spalte+laenge else x = zeile+laenge y = spalte endif endif if (x > 15.or.y > 15) then erg = 0 endif end c ************************************** c berechne Zielfunktion c ************************************** subroutine berechne_zf(belegung,wert,faktor,faktor2,faktor3, c bigkolli,typkolli,kolli,zf) implicit none integer belegung(17,17),wert(17,17) integer bigkolli,typkolli,kolli,zf,zf2,zeile,spalte,summe integer fak,az double precision faktor,faktor2,faktor3 zf = 0 do 100 zeile = 3,15 zf2 = 0 do 200 spalte = 3,15 if (belegung(zeile,spalte) == 0) then c suche Nachbarn az = 0 fak = 0 if (belegung(zeile-1,spalte+1) == 0.and. c belegung(zeile,spalte+1) > 0) then call punkte(belegung(zeile,spalte+1),summe) fak = fak + summe az = az + 1 endif if (belegung(zeile,spalte+1) == 0.and. c belegung(zeile+1,spalte+1) > 0) then call punkte(belegung(zeile+1,spalte+1),summe) fak = fak + summe az = az + 1 endif if (belegung(zeile+1,spalte+1) == 0.and. c belegung(zeile+1,spalte) > 0) then call punkte(belegung(zeile+1,spalte),summe) fak = fak + summe az = az + 1 endif if (belegung(zeile+1,spalte) == 0.and. c belegung(zeile+1,spalte-1) > 0) then call punkte(belegung(zeile+1,spalte-1),summe) fak = fak + summe az = az + 1 endif if (belegung(zeile+1,spalte-1) == 0.and. c belegung(zeile,spalte-1) > 0) then call punkte(belegung(zeile,spalte-1),summe) fak = fak + summe az = az + 1 endif if (belegung(zeile,spalte-1) == 0.and. c belegung(zeile-1,spalte-1) > 0) then call punkte(belegung(zeile-1,spalte-1),summe) fak = fak + summe az = az + 1 endif if (belegung(zeile-1,spalte-1) == 0.and. c belegung(zeile-1,spalte) > 0) then call punkte(belegung(zeile-1,spalte),summe) fak = fak + summe az = az + 1 endif if (belegung(zeile-1,spalte) == 0.and. c belegung(zeile-1,spalte+1) > 0) then call punkte(belegung(zeile-1,spalte+1),summe) fak = fak + summe az = az + 1 endif if (az >= 2) then zf2 = zf2 + wert(zeile,spalte)*fak endif endif 200 continue zf = zf + zf2 100 continue zf = zf-faktor*bigkolli-faktor2*typkolli-faktor3*kolli end c ******************************************* c Ausgabe c ******************************************* subroutine ausgabe(belegung) implicit none integer belegung(17,17) integer k do 100 k = 3,15 write(*,9999) belegung(k,3:15) 100 continue 9999 format(13I3) end c **************************** c bestimme Wert eines Schiffes c **************************** subroutine punkte(zahl,wert) implicit none integer zahl,wert if (zahl == 1) then wert = 4 else wert = 7-zahl endif end \sourceoff \showoff \showon Ausgaben ... Zielfunktion 3545 bigkolli 0 // typkolli 0 // kolli 0 Zielfunktion (gespiegelter Plan) 3296 \showoff Eventuell kannst Du mal testen was bei dir gespiegelt heraus kommt - bei mir 3296 (1.Zeile wird zu Zeile 13, Zeile 13 wird zu Zeile 1, ...). Sofern das nicht zu viel Aufwand macht... Edit: geändert Zeile 15 in 13. Viele Grüße Ronald


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.13, eingetragen 2022-01-15

die ersten beiden notationen verstehe ich erste sind die wasserwerte zweite die anordnung der div schiffe die dritte (fortran ?) das kann ich nur seeeeehr minimal, also keine chance die vierte, was heisst gespiegelt? soll ich die schiffe gespiegelt anordnen, aber die wasserwerte beibehalten? wo liegt dann die probebohrung? (zeile 1 wird zu zeile 13 usw) ??? die zielfunktion, also evtl punktezahlberechnung, ist dort ja nur als summe angegeben, das kann ich also auch nicht ansatzweise nachvollziehen können aber um meine fehlermöglichkeit nochmals auszugrenzen, kannst du die umliegenden schiffsfelder, also das mittlere feld meiner letzten graphik, mal kontrollieren (ich habs dreimal feld für feld durchsucht und entweder nen brett vorm kopf oder es ist richtig) das wäre nett haribo


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.14, vom Themenstarter, eingetragen 2022-01-15

Ich meinte Zeile 1 wird zu 13 etc. Diese Spiegelung müsste auch erreichbar sein, wenn man die Werte der Felder spiegelt. Was mich bei der Spiegelung gerade durcheinander gebracht hatte, war meine interne Zählung. Mit 17 Zeilen und 17 Spalten. Damit konnte ich auch Nachbarfelder von links oben (3,3) etc. gut berechnen.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.15, eingetragen 2022-01-15

oben-unten gespiegelte schiffe, bekomme ich wieder etwas mehr heraus als du, 3308 (differenz 12) [Die Antwort wurde nach Beitrag No.13 begonnen.]


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.16, vom Themenstarter, eingetragen 2022-01-15

Man könnte noch versuchen, weniger Schiffe der Lösung auf das Brett zu tun. Also Zielfunktionswerte für nur 3 Bohrinseln, 3 Bohrinseln + 2 Tanker etc. zu berechnen. Irgendwo muss die Differenz ja her kommen... Oder Du bist im Optimieren besser als ich :-) \showon 3 Bohrinseln, 2 Tanker 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Zielfunktion 261 bigkolli 0 // typkolli 0 // kolli 0 Zielfunktion (gespiegelter Plan) 225 \showoff Ich hoffe mein Programm rechnet für das fast leere Brett richtig...


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.17, eingetragen 2022-01-15

ich hab hier, ausser im #1, noch nie versucht zu optimieren, daran kanns also wirklich nicht liegen hab immer nur versucht für gleiche lösungen gleiches ergebnis zu zählen von mir aus können wir in 24 schritten immer ein schiff mehr rausstreichen -muss ich nur die reihenfolge- verstehen, am ende muss die summe dann ja NULL sein (ich hab nicht verstanden was die idee hinter der gespiegelten variante war...) p.s. bei deinem beispiel mit 3 bohrinseln und 2 tankern komm ich auf 1287, also komplett (~faktor 5 was anderes als du mit den 261)


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.18, vom Themenstarter, eingetragen 2022-01-15

Die gespiegelte Variante diente nur zum Suchen anderer Lösungen. Aber eine gute Lösung gespiegelt war meist um einiges schlechter als eine Originallösung (ohne Spiegelung). Mit einem Programm ist das Spiegeln nicht sehr schwer. Was mir aufgefallen ist: - falls ein Feld nur ein Schiff neben sich hat, gibt es keine Punkte - in der Lösung 3545 gibt es für rechts oben (Ecke) keine Punkte - es liegt nur ein Schiff dran. - ich glaube auch in der 1.Zeile das 4 Feld von links zählt nicht, da liegt nur eine Bohrinsel dran


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.19, eingetragen 2022-01-15

jetzt kommen wir meinem fehler auf die spur, endlich es zählt nur wenn es mindestens zwei schiffe berührt... himmel das wars jetzt komm ich auf gleiche zahlen (aber hab auch wieder gar keine idee wie das geschickt einzuarbeiten wäre)


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.20, eingetragen 2022-01-15

dann hätte ich im feld "umliegende doppelschiffe" diese beiden "nur ein schiff-felder" mit NULL ausfüllen müssen, (hab die zeichnung in #11 entsprechend corrigiert) und ein einziges schiff bzw einige weiterauseinanderliegende würden gar keine punkte bringen acht stunden fehlersuche, ich wäre nie drauf gekommen, danke für deine geduld haribo


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.21, eingetragen 2022-01-15

Dann muss ich in #1 auch noch 3x8=24 abziehen, damit ist das auch keine Optimierung mehr...


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.22, vom Themenstarter, eingetragen 2022-01-15

So ähnlich wie Du bisher nicht auf noch bessere Lösungen gekommen bist, ging es mir mit Computeransätzen. Probiert habe ich z.B. folgendes (Slot-Ansatz): - verwende 30 bis 50 Slots für mögliche Schiffe - fülle die Slots zufällig mit Schiffen und Lagen und Richtungen - führe Verbesserungsschritte aus; dazu: - tausche den Typ eines Slots um die richtigen Anzahlen der Typen zu erreichen - tausche bei einem Typ die Richtung - tausche 2 Slots: Schiffe 1 und Schiff 2 tauschen die Positionen sofern Schiff 1 einen anderen Typ hat als Schiff 2 - verschiebe ein Schiff um -1,+1 in x oder/und y Richtung - es wird mit Straftermen gearbeitet, die Zielfunktion wird abgesenkt falls z.B. 2 Schiffe auf demselben Feld sind oder es eine Typkollision gibt (zuwenig/zuviel Bohrinseln, Tanker, etc.) mit solchen Informationen habe ich versucht gute Lösungen zu finden. Nur so richtig gut hat dieser Ansatz nicht funktioniert.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.23, eingetragen 2022-01-15

Only submarines bringen nur 2500 Punkte, größere Schiffe sind meist bevorteilt, innenlagen besser als Rand und die wiederum besser als Ecken, zugleich gar nicht so einfach alle zulässigen Schiffe unterzubringen... damit sind die Spielräume gering und es bleiben jeweils nur wenige tauschmöglichkeiten... und strategische weiterführende Ansätze nicht erkennbar Ich such noch etwas weiter um eine eigene >3500 Lösung zu finden, aber mit weniger Zeitaufwand als heute... Zu kompliziert ansich...


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.24, eingetragen 2022-01-16

https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_del3498.JPG 3500 bekomme ich bisher nicht hin, aber immerhin einen gleichstand mit dir 3498 hoffe es richtig gezählt zu haben, indem ich im wasserwertefeld sowohl die diagonalberührfelder als auch die nur-ein-schiff-berührenden auf null gesetzt habe(pink) ich hab bei dieser lösung die letzten 70 punkte mit nachbarschafts-vertauschungen im try and error hinbekommen oben die schlepper gegen die bohrinseln; 117 vs 70; 370 vs 189 usw die drei untersten reihen muss ich noch durchprobieren, mal sehen ob da was drin ist


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.25, eingetragen 2022-01-16

tagesziel erreicht 3506, nur eine weitere vertauschung links am rand schlepper gegen versorger https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_del3506.JPG


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.26, eingetragen 2022-01-18

https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_delidee.JPG ich sinniere über diese idee: den benötigten wasserbedarf jedem schiff direkt umlaufend + 0.5 zuzuschlagen, dabei den bohrinseln die ecken wegkappen, damit die diagonalanlegung funktioniert und es dann als rechtwinkliges packproblem auf einem um 1 erweiterten feld zu betrachten, also flächen-feld 14 x 14 u-boot dann 2 x 2 schlepper 2 x 3 ... usw probebohrung muss weiterhin im wasserbereich liegen und ihre umliegenden einschränkungs regeln behalten


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.27, eingetragen 2022-01-18

sorry da war ein versorger zu viel drin


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.28, eingetragen 2022-01-18

wie lange bearbeitungszeit hatte man damals bei der meisterschaft? warst du teilnehmer?


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.29, vom Themenstarter, eingetragen 2022-01-18

Ich habe nicht teilgenommen - habe nur die Aufgabenstellungen und einige Lösungen gesehen. Es waren 10 Aufgaben - man hatte pro Aufgabe so ca. 2 Stunden Zeit.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.30, eingetragen 2022-01-20

bei 10 aufgaben ist es dann eine frage der priorisierung, ich hatte ja nach 2h nichtmal die zählweise richtig begriffen...


   Profil
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 2018
  Beitrag No.31, vom Themenstarter, eingetragen 2022-01-20

Wobei es überall Demo-Aufgaben gab. Um eine Aufgabe richtig zu verstehen. Siehe oben "Themenstart" Beispiel. Auch waren es teilweise Rätsel deren Typ häufiger zu Lösen war. Z.B. so eine Art Kreuzworträtsel.


   Profil
haribo
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 25.10.2012
Mitteilungen: 3753
  Beitrag No.32, eingetragen 2022-01-20

hab nochmal von vorne angefangen und nach 2h war das beste ergebnis 3488 nachdem man offenbar ab 2500 wettbewerbspunkte bakam, dürfte das, im sinne des wettbewerbs, immer noch recht gut sein und klar ich hab ja nun sowiso vorwissen, drum ist es nicht vergleichbar händisch ist das lokale optimieren schon langsam, schon das durchprobieren ob das uboot gegen einen der schlepperplätze getauscht werden kann dauerte 15min (und brachte dabei ~20 punkte) https://www.matheplanet.de/matheplanet/nuke/html/uploads/b/35059_del3488.JPG


   Profil
Delastelle hat die Antworten auf ihre/seine Frage gesehen.
Dies ist eine Knobelaufgabe!
Der Themensteller hat bestimmt, dass Du Lösungen oder Beiträge zur Lösung direkt im Forum posten darfst.
Bei dieser Aufgabe kann ein öffentlicher Austausch über Lösungen, Lösungswege und Ansätze erfolgen. Hier musst Du keine private Nachricht schreiben!

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-2022 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. 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]