Problem 1

hi01ebub
Mausschubser
Mausschubser
Beiträge: 66
Registriert: 14. Dez 2008 17:37

Problem 1

Beitrag von hi01ebub »

In Schritt 3 steht als Hinweis, dass wir einen "klassischen Backtracking Algorithmus" benutzen sollen. Ist das Pflicht oder können wird das Problem auch anders/besser lösen?

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

Re: Problem 1

Beitrag von ice-breaker »

dort steht "Hinweis" und nicht "soll", das sind 2 paar Schuhe ;)

ich habe mir die Aufgabe noch nicht genau angesehen, aber muss man nicht nen rekursiven Ansatz verfolgen? Und da würde Backtracking eben deutlich weniger Speicher kosten als eine "Breitensuche", also von jedem Weg rekursiv einen neuen Zweig öffnen, der anders läuft.

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: Problem 1

Beitrag von daniel_b »

Bin ich eigentlich der einzige, der hier völlig auf dem Schlauch steht? Wird das jetzt immer der Stil der Aufgabenstellung 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 »

Warum muss das denn in dieser "blöden" Agentensprache sein?
Sind wir hier im Kindergarten???
tut mir leid wenn das ein bischen "böse" klingt...ich will damit wirklich niemanden beleidigen.
aber ich musste mir gerade erstmal die tests anschauen um überhaupt zu verstehen, was ihr von uns wollt...
Wer Rechtschreibfehler findet, darf sie behalten...

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: Problem 1

Beitrag von daniel_b »

Wenns Spaß macht..

Mir gehts eher drum, dass da doch irgendwas fehlt. Hab ich ne Vorlesung verpasst, oder so? Ich seh da einfach keine Aufgabenstellung, die über die "Selbsterklärung" des Code-Gerüsts hinaus geht. Die "Aufgabenstellung" auf Seite 2 des PDFs ist ja nicht mehr als eine Auflistung der "//zu implementieren"-Kommentare im Gerüst. Wie dieses ganze Ding im Detail (lies: Vorstellung des Autors) funktionieren soll, versuch ich seit gestern abend aus den Testfällen und anhand der vagen Beschreibungen der Funktionen rauszufinden.

In anderen Worten: Entweder darf ich das, was im Blocktext beschrieben ist, komplett selbst bauen - oder ich integrier die Funktionalität eben in ein Gerüst. Dazu bräuchte ich dann aber konkrete Infos, wie man sich das vorstellt. Die Gerüst-Kommentare oder dieses Geschichten-PDF betrachte ich da nicht gerade als angemessen.
Zuletzt geändert von daniel_b am 28. Apr 2009 17:38, insgesamt 1-mal geändert.

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Problem 1

Beitrag von bruse »

Ich hab mir die Aufgabe mal angeschaut und so undurchschaubar finde ichs nicht. Bis zur letzten Teilaufgabe steht doch klar und deutlich da, was gemacht werden soll: Komparator implementieren, Methode entwerfen, die feststellt, ob genug Satelliten zu einem gegebenen Intervall zur Verfügung stehen, das längste solche finden und so weiter.
Die letzte Teilaufgabe ist vielleicht ein bisschen schwerer, aber der WP-Link dürfte helfen. Was genau ist denn unklar? "Versteh gar nix" ist keine sinnvolle Frage nach Hilfe.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

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 »

ein beispiel wie so eine fertige EventList die satEvents ausspucken soll wäre für mich fürn anfang schon hilfreich
Wer Rechtschreibfehler findet, darf sie behalten...

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: Problem 1

Beitrag von daniel_b »

Was rauskommt, kann ich mir ja vorstellen. Ich unterbiete die Einstiegsprobleme aber mal: satEvents() - Wie komm ich an die einzelnen Intervalle der jeweiligen Interval-Collection der Satelliten-Map? (liebe güte..) Ich sag ja, ich steh total auf dem Schlauch.
Zuletzt geändert von daniel_b am 28. Apr 2009 19:32, insgesamt 1-mal geändert.

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Problem 1

Beitrag von bruse »

Wie meinst Du das? Meinst Du, wie Du einen Start- oder Endwert eines einzelnen Intervalls bekommst? Ein kleiner Blick auf das Schlüsselwörtchen "public" vor den Datenfeldern verrät es Dir :D
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

daniel_b
Computerversteher
Computerversteher
Beiträge: 363
Registriert: 15. Okt 2008 16:23

Re: Problem 1

Beitrag von daniel_b »

Nein. War falsch ausgedrückt, ich meinte wie ich an die einzelnen Intervalle (der jeweiligen Intervall-Collection) komme..

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

Re: Problem 1

Beitrag von ice-breaker »

daniel_b hat geschrieben:Intervall-Collection
sagt das nicht schon alles? :shock:

ansonsten ins Javadoc schauen.

Heap
Erstie
Erstie
Beiträge: 18
Registriert: 28. Apr 2009 20:38

Re: Problem 1

Beitrag von Heap »

Hi,
komme bei der Aufgabe 3 nicht weiter, bei der ein klassisches Backtracking genutzt werden soll.

Habe meine Gedanken so weit geordnet,
dass das Abbruchkriterium ist, dass die restlichen Satelliten die mission nicht mehr abdecken.

Alle Möglichkeiten sind immer, dass man einen der verbleibenden Satelitten entfernt.

Also:
Probiere es mit n --> Deckt mission, dann entferne den ersten
--> Deckt mission nicht mehr, füge ersten wieder ein und entferne zweiten --> Probiere erneut usw.

Das Problem ist, dass es ja keine "feste" Prüfung gibt, ob das Problem bereits gelöst ist.
Diese Bedingung habe ich in allen Templates aber gefunden (8-damen --> Ankunft in der 9.Zeile etc.)

Meine Bedinung ist, dass ich alle Zweige prüfen muss, ob dort die geringste Anzahl an Schritten ist,
leider komm ich nicht darauf wie?

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Problem 1

Beitrag von bruse »

Wie würdest Du es denn von Hand machen? Wie würdest du feststellen, dass eine Lösung besser als eine vorige ist?
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

Heap
Erstie
Erstie
Beiträge: 18
Registriert: 28. Apr 2009 20:38

Re: Problem 1

Beitrag von Heap »

Der Vergleich ist ja nicht schwer, schaue einfach ob die Anzahl der Satelliten weniger ist als das vorherige Minimum.

Denke aber, dass das "klassische Backtracking" nicht anwendbar ist.
Dort ist vorgesehen, dass man abbricht, sobald eine Lösung gefunden wurde.
Hier weiß man doch, dass man alle Kombinationen ausprobieren muss.
Also habe ich ein Minimum gefunden und es geht in dem "Zweig" nicht mehr weiter, muss ich trotzdem weiterprüfen, bis es keine möglichkeiten mehr gibt.

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

Re: Problem 1

Beitrag von kned »

soo... nach langem überlegen hab ich das mit dem backtracking verworfen ... davon abgesehen dass der Algo sowieso total ineffektiv ist, ist er in dem Fall auch nur schwer zu implementieren

Hab das ganze jetzt so gelöst:
Alle Elemente durchgehen:
Element von der Map entfernen, wenn !intervalCovered() element wieder hinzufügen

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]

Erwartet: 5 ist: 6 ... evtl nen Fehler in dem Test? oder gibts bei den 150 zufälligen Tests nur einen Fall in dem mein spezieller Fehler abgedeckt wird?!

Antworten

Zurück zu „Archiv“