Problem 1

Benutzeravatar
leviathan
Computerversteher
Computerversteher
Beiträge: 307
Registriert: 30. Jul 2008 14:26
Wohnort: Darmstadt
Kontaktdaten:

Re: Problem 1

Beitrag von leviathan »

Nachdem du einen Satelliten entfernt hast, bietet es sich an, die gesamte Funtion nochmal auf die bleibenden anzuwenden, um herauszufinden, ob nicht noch welche raus können - man sucht ja im Endeffekt die minimale Anzahl. Da kommt die Rekursion ins Spiel, wenn man die Funktion passend aufgebaut hat, stellt es sich alles sehr gut zusammen.
Ein Programmierer hat immer eine Lösung. Die passt nur nicht immer zum Problem.

Hiwi für Weiterentwicklung des Lernportals (Moodle).

oliver_g
Mausschubser
Mausschubser
Beiträge: 62
Registriert: 17. Nov 2008 16:27

Re: Problem 1

Beitrag von oliver_g »

Morgen, ich stehe gerade etwas auf dem Schlauch...
Ich hänge gerade bei satCoverage() und verstehe (unter anderem) nicht, was genau die Funktion ausgeben soll. Ich probiers mal mit Beispielen.
Angenommen wir hätten folgende Satelliten:
1.Fall: sat1{12, 15}}, sat2{{7, 9}} und sat3{{20, 21}} dann sollte logischerweise {} ausgegeben werden?
2.Fall: sat1{12, 15}}, sat2{{11, 14}}, sat3{{13, 17}} dann sollte {{13, 14}} ausgegeben werden?
3.Fall: sat1{12, 15}}, sat2{11, 15}}, sat3{{9, 14}} und sat4{{14, 19}} dann sollte {{13, 15}} ausgegeben werden?

Fall 1 und 2 ergeben sich schon aus der Aufgabenstellung, der dritte Fall scheint aber über den Hinweis in der Kommentierung zur Funktion abgedeckt zu werden (ließe sich aufspalten als {13, 14}} und {14, 15}, die wiederum zusammengefasst werden sollen).

Letztlich stellt sich dann wohl doch nur die Frage, wie der Hinweis mit der zeitsortieren Eventliste zu verstehen ist.

Jemand irgend nen Hinweis, was ich vielleicht übersehen haben könnte?

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: Problem 1

Beitrag von robert.n »

oliver_g hat geschrieben:Jemand irgend nen Hinweis, was ich vielleicht übersehen haben könnte?
Guten morgen.^^
Der Hinweis lautet: "Gehen Sie die zeitsortierte Eventliste durch und zählen Sie die jeweils sichtbaren Satelliten."

Auf diese Art und Weise kannst du die Funktion relativ einfach gestalten, also ohne allzu komplizierte Überlegungen.

Benutzeravatar
Le_Coeur
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 135
Registriert: 18. Apr 2009 12:39
Kontaktdaten:

Re: Problem 1

Beitrag von Le_Coeur »

leviathan hat geschrieben:Nachdem du einen Satelliten entfernt hast, bietet es sich an, die gesamte Funtion nochmal auf die bleibenden anzuwenden, um herauszufinden, ob nicht noch welche raus können - man sucht ja im Endeffekt die minimale Anzahl. Da kommt die Rekursion ins Spiel, wenn man die Funktion passend aufgebaut hat, stellt es sich alles sehr gut zusammen.
Also diese weiss ich auch, das Problem bei mir ist: wie muss man die Funktion aufbauen um Rekursion zu verwenden. In Scheme hab ich ganz gut verstanden, wie Rekursion funktioniert, und wie muss man Rekursion verwenden, aber im Java bei mir klappts nicht :evil: Ich weiss nicht warum :shock: -> :idea:
Wie ich verstanden habe, es muss irgendwie so sein

Code: Alles auswählen

if(min< fewestSatellites(...).size()) 
   return thisSatellites
else 
   return fewestSatellites(...)

dk1001
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 14. Okt 2008 12:30

Re: Problem 1

Beitrag von dk1001 »

Siehe dir mal das Beispiel "Damenproblem" aus der Vorlesung an. Da wird eine Dame nach der anderen aufs Brett gestellt und geprüft ob sich die bereits postierten Damen schlagen können (Abbruch) oder nicht (weiter). Und das so lange bis alle Damen positioniert sind.
Bei den Satelliten ist das gerade umgekehrt: Es sind alle Satelliten auf dem "Feld" und du musst jetzt "nur noch" schauen welche Satelliten du entfernen kannst ohne an der Abdeckung für die Mission etwas zu ändern. Am Einfachsten ist das (und so ist es von der Aufgabe auch gedacht), in dem du einfach jeden Satelliten mal entfernst und schaust ob die Abdeckung noch erfüllt ist (dafür ist die Hilfsmethode gedacht) - wenn dem so ist, kannst du versuchen noch einen Satelliten zu entfernen, wenn nicht wird der Satellit wohl benötigt, du musst ihn also wieder hinzufügen und probierst das selbe nun mit einem anderen Satelliten in der Hoffnung das du diesen Entfernen kannst.
Der Unterschied ist jetzt nur, dass es beim Damenproblem egal war wo die Damen stehen, Hauptsache du kannst alle positionieren - wenn du also eine gültige Position gefunden hattest konntest du aufhören mit suchen. Bei der Satellitengeschichte sollst du aber die minimale Lösung finden, dass heißt du musst Zwischenlösungen speichern und diese miteinander vergleichen -> Denn du willst am Ende ja nur die Lösung mit den wenigsten Satelliten zurückgeben.
MfG. David Kalnischkies
"Sprächen die Menschen nur von Dingen, von denen sie etwas verstehen, die Stille wäre unerträglich."
"If Java had true garbage collection, most programs would delete themselves upon execution." -- Robert Sewell

Benutzeravatar
Le_Coeur
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 135
Registriert: 18. Apr 2009 12:39
Kontaktdaten:

Re: Problem 1

Beitrag von Le_Coeur »

Also, in der Folie 3 steht:

Code: Alles auswählen

Backtracking (Teilproblem x) 
   Wenn Problem noch nicht gelöst: //hier hab ich einfach geprueft ob HasMap.size() == 1, denn es ist auf jeden Fall minimale Loesung
   Für alle möglichen Lösungsversuche für Teilproblem x //Scheife durch alle Satelliten
      Mache Lösungsversuch  // ich entferne ein Satellite und pruefe intervalCovered falls nicht dann addiere ich wieder zurueck
      Backtracking (Teilproblem x+1)  //hier speichere ich HashMap.size() als min und dann irgendwie muss ich rekursion verwenden??
      Nimm Lösungsversuch wieder zurück // addiere ich wieder zurueck
Ist solche realizierung im Prinzip richtig?

dk1001
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 14. Okt 2008 12:30

Re: Problem 1

Beitrag von dk1001 »

Schwierig da jetzt was zu sagen ohne alles zu verraten... am besten einen Tutor im "Reallife" fragen, der kann da besser helfen.

drei Hinweise aber:
1. Abbruch bei 1? Du kannst schon früher abbrechen... (Wann und Warum?)
2. Gegen wir mal davon aus, du hast 5 Satelliten. Erstmal prüfst du ob die überhaupt die Mission abdecken. Wir nehmen mal an das tuen die Fünf. Dann gehen wir jetzt hin und entfernen erstmal den ersten Satelliten, prüfen ob die Mission noch abgedeckt ist, wenn ja entfernen wir aus den 4 Satelliten wieder einen usw. Bis wir feststellen, dass die Satelliten nicht mehr ausreichen. Dann fügen wir den zuletzt entfernten wieder hinzu und merken uns dieses Ergebnis erstmal als möglicherweise Minimal. Wir probieren natürlich auf jeder Stufe jeden Satelliten einmal zu entfernen. Haben wir das getan haben wir für diese Stufe entweder eine Abdeckung gefunden, die dann logischerweise (für diese Stufe) minimal ist, wir haben mehrere Abdeckungen gefunden bei der wir uns für eine entscheiden müssen oder aber wir haben keine gefunden: null. Das Ergebnis geben wir nun an die Rekursionsstufe vor dieser zurück, die merkt sich dieses Ergebnis als eine mögliche Minimale Abdeckung, fügt den entfernten Satelliten wieder hinzu und probiert einem anderen Satelliten zu entfernen. Dein Ansatz ist also nicht ganz verkehrt - du musst nur darauf achten, dass du bedingungslos jeden entfernten Satelliten auch wieder hinzufügst. Du musst nur eine Bedingung aufstellen die kontrolliert ob das Ergebnis des Rekursionsaufruf gültig ist (!=null) und ob die eventuell ermittelte Lösung minimaler ist als bereits vorher gefundene Lösungen.
3. Du darfst dir nicht HashMap.size() merken, du musst dir die Namen der Satelliten merken, die zusammen genommen die Abdeckung der Mission erfüllen.
MfG. David Kalnischkies
"Sprächen die Menschen nur von Dingen, von denen sie etwas verstehen, die Stille wäre unerträglich."
"If Java had true garbage collection, most programs would delete themselves upon execution." -- Robert Sewell

Benutzeravatar
ff1010
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 30. Apr 2009 17:33
Wohnort: Frankfurt
Kontaktdaten:

Re: Problem 1

Beitrag von ff1010 »

ivoch hat geschrieben:
Klauz hat geschrieben:Hab ich da jetzt vielleicht einfach ein Verständnisproblem? Wieso eine minimale Abdeckung von 5?

Hier noch mal die Werte:

Sat0 38 bis 50
Sat1 40 bis 85
Sat4 55 bis 56
Sat5 57 bis 72
Sat2 32 bis 50
Sat3 4 bis 32
Sat7 21 bis 71
Sat6 39 bis 72
longestSatCoverage: 38 bis 72
Also, Sat0, Sat2 und Sat7 decken ab 38 ab. Sat0 und Sat2 fallen um 50 aus, also müssen zwei andere her - Sat1 und Sat6. Jetzt sind Sat1, Sat6 und Sat7 aktiv und die alle decken bis mindestens 72 ab (es wird ja +1 zur Endzeit addiert, damit es nicht vorkommen kann, dass Start- und Endzeit eines Satelliten dieselbe sind), also haben wir insgesamt 5 Satelliten gebraucht - Sat0, Sat1, Sat2, Sat6 und Sat7.


[EDIT] Robert, hast du dich vielleicht vertippt? Sat3 ist doch gar nicht in der Zeitspanne von longestSatCoverage über dem Zielgebiet.
Hi, also wenn ich mir das auf dem Papier aufzeichne, komme ich nicht ganz auf deine Lösung. Da der Sat7 "nur" bis 71 geht, wird bei mir noch Sat6 benötigt. Du begründest dies mit dem +1, was ja bei deiner Lösung dann auch stimmen würde... aber kannst du genauer erläutern, warum wir eine +1 bei der Endzeit benötigen?

ivoch
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 199
Registriert: 3. Mär 2004 10:51

Re: Problem 1

Beitrag von ivoch »

ff1010 hat geschrieben:
ivoch hat geschrieben:
Klauz hat geschrieben:Hab ich da jetzt vielleicht einfach ein Verständnisproblem? Wieso eine minimale Abdeckung von 5?

Hier noch mal die Werte:

Sat0 38 bis 50
Sat1 40 bis 85
Sat4 55 bis 56
Sat5 57 bis 72
Sat2 32 bis 50
Sat3 4 bis 32
Sat7 21 bis 71
Sat6 39 bis 72
longestSatCoverage: 38 bis 72
Also, Sat0, Sat2 und Sat7 decken ab 38 ab. Sat0 und Sat2 fallen um 50 aus, also müssen zwei andere her - Sat1 und Sat6. Jetzt sind Sat1, Sat6 und Sat7 aktiv und die alle decken bis mindestens 72 ab (es wird ja +1 zur Endzeit addiert, damit es nicht vorkommen kann, dass Start- und Endzeit eines Satelliten dieselbe sind), also haben wir insgesamt 5 Satelliten gebraucht - Sat0, Sat1, Sat2, Sat6 und Sat7.


[EDIT] Robert, hast du dich vielleicht vertippt? Sat3 ist doch gar nicht in der Zeitspanne von longestSatCoverage über dem Zielgebiet.
Hi, also wenn ich mir das auf dem Papier aufzeichne, komme ich nicht ganz auf deine Lösung. Da der Sat7 "nur" bis 71 geht, wird bei mir noch Sat6 benötigt. Du begründest dies mit dem +1, was ja bei deiner Lösung dann auch stimmen würde... aber kannst du genauer erläutern, warum wir eine +1 bei der Endzeit benötigen?
Hmm, also da ist was schiefgelaufen...

Erstmal zu deiner Frage: In testRandom() gibts ja diese Zeile: "intervals[j][1] = Math.max(x, y)+1;" - hier wird +1 addiert, damit es nicht vorkommen kann, dass Start- und Endzeit eines Satelliten gleich sind (die Zeiten sind ja "Random"). Ein Übling hatte mir letzte Woche sein Praktikum gezeigt und er hatte alle Zeiten testweise auf der Konsole ausgeben lassen. Er hatte aber x und y ausgeben lassen, hatte also diese +1 nicht berücksichtigt. Ich hatte mir die Aufgabe und seine Lösung nicht komplett angeschaut, da er nur eine kleine Frage hatte. Die Zeiten, die Klauz in seinem Beitrag angegeben hatte schienen mir bekannt vor und deswegen dachte ich, dass auch er die Ausgabe direkt in der Testmethode gemacht hatte, ohne die +1 zu berücksichtigen. Jetzt habe ich mir die Aufgabe etwas näher angeschaut, und in seinen Zeiten ist die +1 tatsächlich schon mitberücksichtigt.

Also du hast Recht und es werden tatsächlich 6 Satelliten gebraucht, um die Zeitspanne 38:72 zu decken.

Aber: Die Zeiten von Klauz sind nicht vom 121. Test, sondern vom 1. (also answers[0]). Und answers[0] ist 6, also wenn du Sat5 zu meinen Überlegungen im zitierten Beitrag oben hinzufügst, dann stimmen diese auch.

Das Problem von Klauz ist dass er answers[121] == 5 mit den Zeiten von answers[0] vergleicht und deswegen die falsche Ergebnis bekommt.


[EDIT] Ich habe auch meinen zitierten Beitrag aktualisiert, damit ich niemanden verwirre.

André R.
Windoof-User
Windoof-User
Beiträge: 33
Registriert: 16. Okt 2008 12:17

Re: Problem 1

Beitrag von André R. »

Hi,
ich bekomme bei testTwoHandover und smallOverlap immer eine Nullpointer Exception - kann allerdings die Stelle nicht ausfindig machen und Eclipse gibt nur den J-Unit Testfall als Stelle an.

Random läuft durch (zwar falsch, aber ok...) - somit kann die Funktion ja nicht total kaputt sein.

Jemand eine Idee warum die beiden Probleme machen könnten? (Ich weiss - schwer ohne code)

Vorgehen ist;
schleife
Abbruchbedingung überprüfen
aktuelle Map in eine neue kopieren und einen entfernen
überprüfen ob intervall okay und ob intervall kleiner als vorheriges, wenn ja speichern (die map)
rekursion
satellit hinzufügen

Wenn fertig, das beste Ergebnis zurück geben.
(Ich hoffe mal, dass das nun nicht zu genau ist - aber hey es funktioniert ja sowieso nicht ;) )

jonas
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 177
Registriert: 5. Okt 2008 21:35
Wohnort: DA

Re: Problem 1

Beitrag von jonas »

André R. hat geschrieben:Hi,
ich bekomme bei testTwoHandover und smallOverlap immer eine Nullpointer Exception - kann allerdings die Stelle nicht ausfindig machen und Eclipse gibt nur den J-Unit Testfall als Stelle an.
[...]
In der Fehlermeldung (selbst unter JUnit) steckt die Datei, die Zeilennummer und der Stacktrace...
Siehst du dort die Test-Klasse dann gibst du wohl irgendwo null zurück und die Test-Klasse will damit arbeiten.
Schau doch mal zu wie die Test-Klasse an dieser Stelle arbeitet, im Debug-Modus siehst du dann sofort wo es knallt.
Wenn du mit dem Debug-Modus nicht vertraut bist solltest du das schleunigst werden, der ist (meiner Meinung nach) total wichtig und hilft bei eigentlich jeder Problemsuche schnell weiter.
Dabei interessantes Feature was vielen nicht vertraut ist: Breakpoint-Properties -> Hit Count.

Des weiteren:
André R. hat geschrieben: [...]
Random läuft durch (zwar falsch, aber ok...) - somit kann die Funktion ja nicht total kaputt sein.
[..]
Wie ist das bei Testfällen, laufen die weiter sobald ein Fehler bzw ein falsches Ergebnis kommt?
Ich meine nein!
Daher muss nur die erste Prüfung etwas "falsches" zurück geben und schon wird nicht weiter getestet - sie kann also durch aus total kaputt sein.

Benutzeravatar
martin
Mausschubser
Mausschubser
Beiträge: 83
Registriert: 28. Sep 2008 20:50
Wohnort: Dieburg...die Stadt im Grünen :)
Kontaktdaten:

Re: Problem 1

Beitrag von martin »

sacht mal wie lang braucht bei euch der algo um den randomTest bei fewestSats durchzuführen?
bei mir knapp 22sec :|
Wer Rechtschreibfehler findet, darf sie behalten...

André R.
Windoof-User
Windoof-User
Beiträge: 33
Registriert: 16. Okt 2008 12:17

Re: Problem 1

Beitrag von André R. »

0,610 sekunden :P

Benutzeravatar
leviathan
Computerversteher
Computerversteher
Beiträge: 307
Registriert: 30. Jul 2008 14:26
Wohnort: Darmstadt
Kontaktdaten:

Re: Problem 1

Beitrag von leviathan »

0.125 :)

Core2Duo 2,5GhZ, (sehr geringfügig optimierter) klassische Backtracking-Algorithmus.
Bei 22 Sekunden würde ich mir Gedanken machen ob da nicht zufällig die eine oder andere Schleife zu viel drin ist.
Ein Programmierer hat immer eine Lösung. Die passt nur nicht immer zum Problem.

Hiwi für Weiterentwicklung des Lernportals (Moodle).

Ziuzia
DON'T PANIC
Beiträge: 42
Registriert: 27. Okt 2007 16:36

Re: Problem 1

Beitrag von Ziuzia »

0.146 Sekunden.
C2D 2.0GHz (Akkubetrieb) :P

Antworten

Zurück zu „Archiv“