Übung3

Benutzeravatar
pv
Erstie
Erstie
Beiträge: 11
Registriert: 14. Apr 2004 19:20

Übung3

Beitrag von pv »

Hi,

können wir davon ausgehen, dass bei der tapestry-aufgabe alle Knoten vollständig miteinander verbunden sind?

Gruß

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

Beitrag von A380 »

Ich schätze mal schon. Ansonsten kann man ja ein Objekt nicht hinzufügen und was dann passieren soll ist undefiniert. Bzw. da man random auswählt entstehen verschiedene Lösungen.....

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

Beitrag von Prom »

Mir ist da noch was aufgefallen...

In der Aufgabe steht "When several nodes are possible candidates for an entry in the neighbor table, pick the node with the smallest ID among them."

Das bedeutet also, wenn ich auf einem Knoten ankomme, dessen ID = ID des Objektes ist, aber noch nicht in der letzten Level bin, werde ich wieder weggeroutet, da in der Neighbor Map ja nicht der näheste (in dem Fall der Knoten selbst), sondern der Knoten mit der kleinsten ID steht...

Fox
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 22. Feb 2005 01:34

Beitrag von Fox »

was ist eigentlich genau mit dem closest entry gemeint, falls das feld in der table leer sein sollte?

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

Beitrag von foo »


Fox
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 22. Feb 2005 01:34

Beitrag von Fox »

äh die antwort hilft mir nicht unbedingt weiter

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

Beitrag von Prom »

Fox: Ich nehme an die meinst beim Routing der Objekte:
Closest entry ist der naeheste Knoten in der aktuellen Zeile. Bist du zum Beispiel in Spalte 6, dann sind in der aktuellen Zeile 5 und 7 die naechsten, danach 4 und 8, usw. Sollten zwei Knoten mit der gleichen Entfernung vorhanden sein, nimmst du den mit der kleineren Nummer.

Fox
Mausschubser
Mausschubser
Beiträge: 56
Registriert: 22. Feb 2005 01:34

Beitrag von Fox »

jop, ok und wenn die zeole leer ist, dann einen level drunter.

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

Beitrag von Allocater2 »

also ich hab jetzt Objekt 28336 ... das landet zufällig auf Node 26817... Die Tabelle von der sieht so aus:

Code: Alles auswählen

#### 26817 ####
Level 0: 00152|10188|_____|30104|40116|50135|60179|70142|80027|_____|
Level 1: 20000|21024|22088|23073|24030|25052|_____|27069|28002|29028|
Level 2: _____|26123|26213|26351|_____|26532|_____|26716|_____|26972|
Level 3: _____|_____|_____|_____|26841|_____|_____|_____|_____|_____|
Level 4: _____|_____|_____|_____|_____|_____|_____|_____|_____|_____|
wo kommt dann das Objekt hin? Eigentlich bin ich ja beim 0. Hob, also bei Level 0. Aber da gibts keine Node die mit 2 anfängt. Wenn ich jetzt an links oder rechts weiterleite dann ist doch nicht mehr die Bedingung erfüllt, dass bei jedem Hob ein Digit mehr übereinstimmt :?:

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

Beitrag von Allocater2 »

Also ich berchne jetzt das level/zeile wo ich nachgucken muss nicht mehr nach dem beim wievielten hob ich bin, sondern danach wieviele digits übereinstimmen zwischen Objekt und aktueller Node.

wenn das feld leer ist, geh ich links und rechts auf suche nach näherem. das ne ganze zeile leer ist berücksichtige ich überhaupt nicht, passiert das, bleibt er halt bei der aktuellen node. (ob das stimmt?)

hier einige Daten:

Code: Alles auswählen

37476: 37479 37484 37471 37463 37493 37496 
56911: 56911 56933 
61071: 61066 61099 61098 61059 
48166: 48240 48226 48198 48193 48100 48202 48134 48152 48126 48217 48118 48186 48125 48113 48157 48137 48128 
61599: 61594 61581 
63282: 63287 63289 

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

Beitrag von Allocater2 »

mmmh falls das so mit der Zuteilung stimmt und ich die Zuteilung richtig verstanden habe, hätte man sich das mit den Tabellen einfach sparen können und gleich nach einer Formel die Objekte den Nodes zuordnen können. Indem man die Formel als Distanz berechnet ala:

Distanz(o,n) = matchingleadingdigits(o,n)*-100000000+differenz(o,n)

Also übereinstimmende digits haben super hohe priorität und zählem vor allem. Wenn 2 nodes gleichviele digits übereinstimmen haben, zählt ihre ware distanz zum Objekt.

Objekt 11999
würde also dann zur Node 11000 zugeordnet werden, (digits 2, entfernung 999) anstatt zur Node 12000 (digits 1, entfernung 1)

richtig?

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

Beitrag von Allocater2 »

ich frag mich grad, muss die node in ihre eigene tabelle rein?

#### 00152 ####
Level 0: 00152|10188|20000|30104|40116|50135|60179|70142|80027|_____|
Level 1: 00152|01215|02003|03054|04067|05074|06020|07036|08062|09118|
Level 2: _____|00152|00267|00386|00416|00522|_____|00711|00899|00902|
Level 3: _____|_____|_____|_____|_____|00152|_____|_____|00187|_____|
Level 4: _____|_____|00152|_____|_____|_____|_____|_____|_____|_____|

oder

#### 00152 ####
Level 0: 00187|10188|20000|30104|40116|50135|60179|70142|80027|_____|
Level 1: 00187|01215|02003|03054|04067|05074|06020|07036|08062|09118|
Level 2: _____|00187|00267|00386|00416|00522|_____|00711|00899|00902|
Level 3: _____|_____|_____|_____|_____|_____|_____|_____|00187|_____|
Level 4: _____|_____|_____|_____|_____|_____|_____|_____|_____|_____|

?

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

Beitrag von Allocater2 »

ein weiteres Problem: Irgendwie ist das ganze nicht deterministisch:

Code: Alles auswählen

#### 05074 ####
Level 0: 00152|10188|20000|30104|40116|50135|60179|70142|80027|_____|
Level 1: 00152|01215|02003|03054|04067|05258|06020|07036|08062|09118|
Level 2: _____|_____|05258|_____|_____|__x__|_____|_____|05804|_____|
Level 3: _____|_____|_____|_____|_____|_____|_____|_____|_____|_____|
Level 4: _____|_____|_____|_____|_____|_____|_____|_____|_____|_____|
ich habe diese Node und will das Objekt 05541 einordnen, dann lande ich auf diesem Feld |__x__|. da ist nix also gehe ich links und rechts suchen, ich finde: 05258 und 05804. Zu 05258 ist es eine Differenz von 283.... zu 05805 eine Differenz von 264. Also geh ich nach recht zu 05804.

Das ist aber falsch, denn wäre ich zu 05258 gegangen, hätte ich festgestellt:

Code: Alles auswählen

#### 05258 ####
Level 0: 00152|10188|20000|30104|40116|50135|60179|70142|80027|_____|
Level 1: 00152|01215|02003|03054|04067|05074|06020|07036|08062|09118|
Level 2: 05074|_____|05289|_____|_____|_____|_____|_____|05804|_____|
Level 3: _____|_____|_____|_____|_____|_____|_____|_____|05289|_____|
Level 4: _____|_____|_____|_____|_____|_____|_____|_____|_____|_____|
Tadaaaa, es gibt noch eine 05289, die in der Tabelle vorher nicht aufgetaucht ist. Die Diefferenz dazu ist nun 252. Also die beste, besser als die Differenz von 264.

Bloß wie soll ich diese node denn nach Tabellenalgorithmusvorgehen denn finden? Wenn ich beim neuen Durchlauf zufällig wo anders lande wo ich da hin komme, komme ich halt hin, aber wenn ich von anders wo komme, kann ich nicht hinkommen. Voll komisch.....

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

Beitrag von dcdead »

hätte man sich das mit den Tabellen einfach sparen können und gleich nach einer Formel die Objekte den Nodes zuordnen können.
Hatte ich so gemacht, da ich auf die Aufgabe nicht sooo viel Lust hatte ;) So war das ganze in 5 Minuten gecodet. Komme damit auf die gleichen Zeilen, die du gepostet hattest.

Antworten

Zurück zu „Archiv“