Problem 1

Christoph-D
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: Problem 1

Beitrag von Christoph-D »

Heap hat geschrieben:Denke aber, dass das "klassische Backtracking" nicht anwendbar ist.
Dort ist vorgesehen, dass man abbricht, sobald eine Lösung gefunden wurde.
Wikipedia ist wohl keine sehr verlässliche Quelle, aber andererseits ist "backtracking" auch nicht eindeutig definiert (in 3 Büchern wirst du voraussichtlich 3 Definitionen finden, die sich alle im Detail unterscheiden):
In dem Wikipedia-Artikel zu "backtracking" wird der Algorithmus, der bei der ersten Lösung abbricht und keine weiteren berechnet, als "Variante" bezeichnet:
http://en.wikipedia.org/wiki/Back_track ... g_variants
Diesem Artikel nach bricht also "klassisches Backtracking" nicht bei der ersten Lösung ab.
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

Christoph-D
Computerversteher
Computerversteher
Beiträge: 325
Registriert: 11. Dez 2005 13:14
Wohnort: Darmstadt

Re: Problem 1

Beitrag von Christoph-D »

kned hat geschrieben:Findet zwar nicht das minimale, aber das würde ein normaler Backtrack Algo ja auch nicht

Es gehen alle Tests bis auf den TestRandom mit der answers[121]
Fragt die Aufgabe nach einem minimalen Ergebnis? Wenn ja, würde das den fehlgeschlagenen Test erklären. :)
"I believe in the fundamental interconnectedness of all things." (Dirk Gently)

ice-breaker
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 216
Registriert: 14. Okt 2008 17:56

Re: Problem 1

Beitrag von ice-breaker »

Backtracking beschreibt doch nur die Art, wie der Algorithmus funktioniert, also wie eine Tiefensuche die Äste immer weiter laufen und wenn ein Weg nicht mehr funktioniert, geht man zurück, bis man wieder auf einen Weg kommt, der möglicherweise eine Lösung ist, von Abbruchbedingung ist da keine Rede.

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

Re: Problem 1

Beitrag von leviathan »

Also ich habe das mit einer etwas abgewandter Form des Backtracking Algo (Kombination von Rekursion und Iteration) implementiert, und alle Tests laufen unverändert durch, kein Problem. Am Ende kommt bei mir eine der möglichen Minimallösungen raus - welche genau (wenn's mehrere Kombinationen gibt; kommt in den Tests glaube ich nicht vor), kann man nicht festlegen - hängt von der Reihenfolge in der HashMap ab.
Ein Programmierer hat immer eine Lösung. Die passt nur nicht immer zum Problem.

Hiwi für Weiterentwicklung des Lernportals (Moodle).

kned
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 14. Okt 2008 18:49
Kontaktdaten:

Re: Problem 1

Beitrag von kned »

Christoph-D hat geschrieben:
kned hat geschrieben:Findet zwar nicht das minimale, aber das würde ein normaler Backtrack Algo ja auch nicht

Es gehen alle Tests bis auf den TestRandom mit der answers[121]
Fragt die Aufgabe nach einem minimalen Ergebnis? Wenn ja, würde das den fehlgeschlagenen Test erklären. :)
naja bei 150 tests und nur einem Fehlschlag ... habs jetzt doch mit Backtrack gemacht, tests 7/7 ^.^

fetzer
Kernelcompilierer
Kernelcompilierer
Beiträge: 522
Registriert: 1. Okt 2008 17:18

Re: Problem 1

Beitrag von fetzer »

...

edit: dumb! (oder auch: dieser post kann gelöscht werden)

Benutzeravatar
a_ilgen
Erstie
Erstie
Beiträge: 15
Registriert: 15. Okt 2008 17:17
Kontaktdaten:

Re: Problem 1

Beitrag von a_ilgen »

Ich bekomme auch bei Test 121 eine Fehler. Wenn ich den Test 121 ausschliese laufen die restlichen Tests durch. Ist der TEst vielleicht buggy?
if(TUD.scherbenhaufen()) TUD.leave();

kned
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 14. Okt 2008 18:49
Kontaktdaten:

Re: Problem 1

Beitrag von kned »

wie gesagt, bei test 121 findet man mit einer linearen Methode nicht die minimalste Abdeckung ...

Klauz
Erstie
Erstie
Beiträge: 16
Registriert: 10. Okt 2008 08:20

Re: Problem 1

Beitrag von Klauz »

kned hat geschrieben:wie gesagt, bei test 121 findet man mit einer linearen Methode nicht die minimalste Abdeckung ...
Hallo!

Bei mir schlägt auch die besagte 121 im Test fehl ;-) Der Rest geht. Da die Werte, die im Test verwendet werden ja nicht "random" sind hab ich mir das ganze mal auf einem Zettel aufgemalt und komme auch auf eine minimale Abdeckung von 6 Satelliten (im Test 5).

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

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

Re: Problem 1

Beitrag von robert.n »

Habe mir mal die Zusammenstellung von Durchlauf 121 (FewestSatellitesTest.testRandom) ausgeben lassen:
Sat0, Sat1, Sat2, Sat3, Sat7
Vllt. bringt dich das ja weiter.

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

Re: Problem 1

Beitrag von ivoch »

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.

[EDIT2]Die obigen Überlegungen sind falsch, da ich angenommen hatte, dass Klauz die Zeiten direkt in der Testmethode hatte ausgeben lassen, ohne die +1 die zu Math.max() addiert wird zu berücksichtigen. Hier die richtigen Überlegungen:

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. Sat1 und Sat6 sind bis mindestens 72 aktiv, also müssen wir nur Sat7 berücksichtigen - wir nehmen Sat5 dazu, und schon haben wir eine dreifache Abdeckung auch bis 72. Also die benötigten Satelliten sind Sat0, Sat1, Sat2, Sat5, Sat6 und Sat7. Beachte aber - diese sind die Zeiten vom Test0, nicht vom Test121, also 6 ist schon richtig.

Bei Test121 sind die Zeiten anders - 12:28, 22:82, 0:61, 9:45, 27:57, 57:61, 70:80, 13:85. Hier werden die Satelliten 12:28, 22:82, 0:61, 9:45, 13:85 gebraucht, für eine Abdeckung von 12 bis 61, also 49, was auch die richtige Antwort ist.
Zuletzt geändert von ivoch am 4. Mai 2009 14:24, insgesamt 1-mal geändert.

Klauz
Erstie
Erstie
Beiträge: 16
Registriert: 10. Okt 2008 08:20

Re: Problem 1

Beitrag von Klauz »

ivoch hat geschrieben:es wird ja +1 zur Endzeit addiert, damit es nicht vorkommen kann, dass Start- und Endzeit eines Satelliten dieselbe sind
Hallo ihr Zwei!

Danke für die schnelle Antwort. Bis zum Zeitpunkt 50 kann ich das nachvollziehen. Sat7 geht bis 71 und es muss bis 72 abgedeckt werden. Daher müsste doch eigentlich doch noch ein weiterer Satellit her, damit der Intervall bis 72 abgedeckt ist.

Wieso wird +1 zur Endzeit addiert? Wenn z.b. 1 bis 3 abgedeckt sein muss, reicht es doch nicht wenn man drei Satelliten hat, die von 1 bis 2 präsent sind?

MfG
Klaus

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

Re: Problem 1

Beitrag von Le_Coeur »

"time" in Class "Event", ist es die Zeit wenn "Event" passiert?

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

Re: Problem 1

Beitrag von robert.n »

Was meint ihr mit "Test 121"?

longestSatCoverage ist bei mir zwar 2x das Intervall (38, 72), aber nicht bei i=121, sondern bei i=0 und i=99.

Wir haben aneinander vorbeigeredet. :x :mrgreen:

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

Re: Problem 1

Beitrag von Le_Coeur »

Mit der letzten Aufgabe komme ich nicht dran:( Ich verstehe nicht, wie kann man hier Rekursion verwenden.
Ich iteriere durch eine Schleife -> 1) entferne ein Satelite 2) falls "!intervalCovered" dann addiere ich wieder zurueck 3) else ich speichere Groesse von HashMap als min, aber wie muss ich dann Rekursion aufrufen?:) Ich brauche kleinen Hinweis :idea: :|

Antworten

Zurück zu „Archiv“