| |
| Autor |
 Eine Aufgabe aus der Optimierungsmeisterschaft 2009 zum Lösen |
|
Delastelle
Senior 
Dabei seit: 17.11.2006
Mitteilungen: 1996
 |  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 
Dabei seit: 25.10.2012
Mitteilungen: 3723
 | 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
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| Beitrag No.3, eingetragen 2022-01-13
|
kennst du das maximum?
[Die Antwort wurde nach Beitrag No.1 begonnen.]
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| Beitrag No.27, eingetragen 2022-01-18
|
sorry da war ein versorger zu viel drin
|
Profil
|
haribo
Senior
Dabei seit: 25.10.2012
Mitteilungen: 3723
| Beitrag No.28, eingetragen 2022-01-18
|
wie lange bearbeitungszeit hatte man damals bei der meisterschaft? warst du teilnehmer?
|
Profil
|
Delastelle
Senior
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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
Dabei seit: 17.11.2006
Mitteilungen: 1996
| 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
Dabei seit: 25.10.2012
Mitteilungen: 3723
| 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! |
|
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]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
