Übung 3

tunisiano
Neuling
Neuling
Beiträge: 10
Registriert: 29. Dez 2004 23:19
Wohnort: Frankfurt

Übung 3

Beitrag von tunisiano »

Ich war am Montag leider nicht in der Übung, habe mir die 3. Übung angeschaut, auf den ersten Blick sieht es nicht so aus dass man das manuell bearbeiten kann...:shock:
ist das ein Vorurteil oder ist die Übung netter wenn man sie noch näher anschaut?

Benutzeravatar
konfusious
Neuling
Neuling
Beiträge: 7
Registriert: 12. Mär 2005 11:57

Beitrag von konfusious »

Hab grad die CAN-Aufgabe fertig gemacht. Ja man sollte Programmieren ;-)

Stellt euch ruhig auf was ein. Ich hab den ganzen Abend damit verbracht (so ca. 3-4 Std.), und das nur für die 2. Teilaufgabe mit Can.

Die Aufgabenstellung ist leider unklar.
Es ist die Rede von Euklidischer Distanz. Diese kommt jedoch hierbei gar nicht zum Einsatz.
Meiner Meinung nach muß jedes Objekt in die Zone in deren Koordinatenbereich es fällt. Die Euklidische Distanz ist erst beim Routing wichtig.

Ausserdem gibt es folgende zwei Probleme:

1. Zonen lassen sich nicht immer genau halbieren (jedenfalls nicht mit int :-))
Daher ist zu erwarten das es keine absolut einduetige Lösung gibt.

2. Es kann passieren das ein Zonenhalter gar nicht mehr selber in die Zone fällt, was aber egal ist. Um genau zu sein geht es auch gar nicht anders.

Also lasst euch nicht verwirren.

Ich wäre sehr dankbar um eine Klärung wozu die euklidische Distanz hier nützlich sein soll. Routing werd ich jetzt nicht mehr implementieren ;-)

A380
Mausschubser
Mausschubser
Beiträge: 52
Registriert: 16. Dez 2003 21:36

Beitrag von A380 »

Genau das ist auch mein Problem. Entweder sortiere ich die Knoten nach der Distanz ein oder in die Zelle in die es gehört. Beides geht nicht. Evtl. ist auch was anderes damit gemeint.

Weiterhin undefiniert ist wohin jeweils der Rand einer Zelle gezählt wird. Also < oder <=.

Außerdem ist auch unklar wie die Ausgabe sein soll. Besteht o1 dann aus einem Paar (x,y)? Wenn ja wie soll es angegeben werden?

Benutzeravatar
foo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 179
Registriert: 22. Okt 2004 17:59

Beitrag von foo »

Hallo!

Aus dem Forum zu der Veranstaltung letztes Jahr: http://www.fachschaft.informatik.tu-dar ... php?t=3683

Daraus schliesse ich, dass wir diesmal ein richtigen CAN implementieren muessen und die Metrik ein Ueberbleibsel aus der Aufgabenstellung des letzten Jahres ist?

Benutzeravatar
Prom
Computerversteher
Computerversteher
Beiträge: 344
Registriert: 5. Jan 2004 21:43

Beitrag von Prom »

Wie groß ist der Torus eigentlich? 100000x100000 ?

Benutzeravatar
konfusious
Neuling
Neuling
Beiträge: 7
Registriert: 12. Mär 2005 11:57

Beitrag von konfusious »

Ne, er hat schon recht.
Der Torus entsteht einfach durch das wrapping der Koordinaten der Dimensionen.

Ein Can mit zwei Dimensionen kann man sich als Donut vorstellen.

Das ganze stellt also einen mehrdimensionalen Kreis dar.

maTze
Neuling
Neuling
Beiträge: 4
Registriert: 8. Dez 2004 20:44
Wohnort: darmstadt
Kontaktdaten:

Beitrag von maTze »

Eine Frage bezüglich der Trennung der Aufgabenbereiche.

Sei also Node A mal ein Verantwortlichkeitsbereich zugeordnet (Quadrat). Node B bekommt beim Joinen ein Zufallspunkt in diesem Bereich, somit wird vertikal geteilt. Soweit alles klar... aber wer wird links/rechts (analog oben/unten) einsortiert?

Da ich die Zufallspunkte beim Join als Information sehe, die rein zum Einsortieren in die Netzstruktur vorhanden ist, bin ich mir nicht sicher, ob es sinnvoll ist, die x- oder y-Komponente der (Zufalls-Join-)Punkte zu vergleichen. Vielleicht eher was simples wie "der alte Besitzer der Fläche kommt links/oben hin, der neu gejointe rechts/unten"?

Antworten wären nett, da sonst logischerweise unterschiedliche Ergebnisse zustande kommen.

Grüßlein,
maTze
====================
===> οιδα ουδεν ειδ
====================

Benutzeravatar
Prom
Computerversteher
Computerversteher
Beiträge: 344
Registriert: 5. Jan 2004 21:43

Beitrag von Prom »

Eigentlich sollte hier im Forum noch was dazu gepostet werden ...

dirk.bradler
Neuling
Neuling
Beiträge: 4
Registriert: 23. Okt 2006 16:11

Beitrag von dirk.bradler »

Hallo P2Pler,
Join bei CAN:
- sobald ein Bereich gesplittet wird, setzt den alten Node nach links bzw. unten und den neuen Node entsprechend in den anderen Bereich.
- setzt die Position der Nodes dann in die Mitte des jeweiligen Berichs (abrunden)
- Grösse 100000x100000
- Falls ein node exakt auf eine grenze fällt, den kleineren Wert nehmen

Gruss

Dirk

Benutzeravatar
Ultr1
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 13. Okt 2004 17:53
Wohnort: Dreieich
Kontaktdaten:

Beitrag von Ultr1 »

dirk.bradler hat geschrieben: - setzt die Position der Nodes dann in die Mitte des jeweiligen Berichs (abrunden)
Was hat das für einen Sinn? Jeder Knoten merkt sich doch seinen Zuständigkeitsbereich - da ist es doch egal welche Koordinaten er selber mal hatte als er einsortiert wurde. Der Zuständigkeitsbereich hat doch insofern nichts mehr mit Lokalitäten zu tun (zumal ja die rechts/links bzw oben/unten Aufteilung relativ willkürlich ist). Ein Punkt muss beispielsweise nicht einmal bzgl. seiner Koordinaten in seiner Fläche liegen - hauptsache zum Zustädigkeitsbereich. Wozu also die Koordinaten dann neu machen? In der Ausgabe in der txt sollen doch auch sicherlich die Original-Nodes ausgegeben werden?
Und die Standardabweichung - soll die dann vom Mittelpunkt der Fläche oder von der Original berechnet werden. Die dann von der Abwandlung zu berechnen macht meiner Meinung nach ebenso wenig Sinn.

Ich will ein Beispiel machen:
Ich adde meinen ersten Knoten. Der sei koordinatenmäßig ganz rechts . Er ist für alles zuständig. Ich adde den nächsten, der koordinatenmäßig ganz weit links liegt. Der erste rechte Knoten (der alte) kriegt jetzt den linken Teilbereich und der linke den rechten. Sie liegen also lokal nicht mehr in ihrem Zuständigkeitsbereich. jetzt ist gefordert, dass wir die neuen Koordinaten auf den Mittelpunkt verschieben (das wäre eine Verschiebung komplett zur anderen Seite...). Was bringt mir das nun? Ich habe mir in meinen Areas doch jeweils abgespeichert wo ihr Zuständigkeitsbereich ist, wozu die veränderte Koordinate? Die Koordinate ist bei mir lediglich eine Art Area-ID - bei mir werden einfach immer nur die Areabereich geändert. Was hab ich durch diese Verschiebung gewonnen?
Gruß
Ultri
Es ist nicht entscheidend, was der Mensch tut, sondern was er ist. (Henry Miller)

maTze
Neuling
Neuling
Beiträge: 4
Registriert: 8. Dez 2004 20:44
Wohnort: darmstadt
Kontaktdaten:

Beitrag von maTze »

Mh ja, die Aufgabe ist "mit sehr viel Freiheit" versehen ;)

Ist es auch ok, wenn man gar nicht rundet? Es gibt auch tolle Klassen wie Rectangle2D.Float bzw .Double...

Und noch eins... ich nehme stark an, dass die x-Achse des Systems von links nach rechts und die y-Achse (wie bei [so gut wie] allen Computergeschichten) von oben nach unten geht, korrekt? Wenn man das vertauscht, ergeben sich logischerweise verschiedene Ergebnisse beim Einteilen... (weil "oben entspricht y=0" würde heißen, dass der alte Knoten nach der Teilung die größere y-Koordinate besitzt... ansonsten die kleinere)

Und noch was: Müssen wir den Code, mit dem wir die Aufgaben gelöst haben, nicht auch mitsenden? Auf dem Aufgabenblatt steht nämlich nichts davon...

Grüßlein,
maTze
====================
===> οιδα ουδεν ειδ
====================

Benutzeravatar
konfusious
Neuling
Neuling
Beiträge: 7
Registriert: 12. Mär 2005 11:57

Beitrag von konfusious »

Also ich muss mal was dazu sagen.

Ich hab bereits mal ein richtiges Can im Rahmen eines Projekts implementiert. Und daher weiß ich das ein Node seine ID nur zum ersten Auffinden einer Zone die geteilt werden soll braucht. Später kann es ihm total egal sein welche ID er hat (Keine Angst, das stimmt. Ich hab das mit nem Doktor aus Ungarn lange diskutiert). Und so hab ichs auch implementiert. Ich seh nicht ein warum ich das nochmal umschreiben sollte. Hier mit in die Mitte setzen und so....wozu???

Es gibt absolut keine Veranlassung das so zu machen.
Ausserdem kann es dadurch sogar zu Kollisionen bzgl. des Hashs kommen, da durch das in die Mitte setzen die Kollisionsfreiheit einer Hash-Funktion evtl. nicht mehr gewährleistet ist.

Sorry wenn ich das so sagen muß, aber diese Forderung ist schlichtweg falsch.

Allocater2
Mausschubser
Mausschubser
Beiträge: 61
Registriert: 19. Nov 2004 20:53

Beitrag von Allocater2 »

ääääääh, also ich vergesse jetzt einfach, was ein CAN ist und mache 2 Schleifen die so aussehen und dann hab ich die leichteste Version implementiert, da die Aufgeabenstellung eh total uneindeutig und widersprüchlich ist, oder was?

for(alle objects)
for(alle nodes)
berechne(eukl_distance(object,node))
}
mappe object zu nahester node
}

fertig?

Benutzeravatar
Ultr1
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 13. Okt 2004 17:53
Wohnort: Dreieich
Kontaktdaten:

Beitrag von Ultr1 »

Und was machst du dann mit deiner euklidischen Distanz? Ich bin noch nicht ganz hintergestiegen wofür man dir brauchen könnte außer vll für die Abweichung.
Es ist nicht entscheidend, was der Mensch tut, sondern was er ist. (Henry Miller)

dcdead
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 190
Registriert: 11. Nov 2004 21:20

Beitrag von dcdead »

Also das mit dem nähestem Node dürfte IMHO nicht gehen. Mal angenommen du hast eine sehr große Zone, in deren Randbereich ein Objekt eingefügt werden soll. An diese große Zone grenzt nun eine sehr viel kleinere Zone an (die halt schon öfter gesplittet wurde). In diesem Fall würde der nächste Knoten aber der der kleinen Zone sein, da er halt näher dran ist, als der (ich nehme an dass du's so gemacht hast) in der Mitte der großen Zone liegende Knoten.

Das mit dem Knoten in die Mitte seiner untergeordneten Zone "zu verschieben" finde ich auch ziemlich unglücklich. Hab es ebenfalls so implementiert, dass die Koordinaten der einzelnen Nodes nicht geändert werden und sich halt nur die Koordinaten ihrer untergeordneten Zonen ändern.

Antworten

Zurück zu „Archiv“