Yoeli

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

Yoeli

Beitrag von A380 »

Noch 2 Fragen zum Yoeli ;)

1) Wann addiere ich das B dazu? "Falls i Spalten der maximalen Dichte überspannt" steht im Skript, doch leider weiß ich nicht mehr genau was das nun bedeutet. Wie groß ist denn die maximale Dichte in dem Beispiel im Skript?

2) Wann ist die vertikale Einschränkung verletzt? Kann man das am VCG ablesen?

koch
Dozentin/Dozent
Beiträge: 221
Registriert: 4. Jul 2005 11:08

Beitrag von koch »

1) Wann addiere ich das B dazu? "Falls i Spalten der maximalen Dichte überspannt" steht im Skript, doch leider weiß ich nicht mehr genau was das nun bedeutet. Wie groß ist denn die maximale Dichte in dem Beispiel im Skript?
Jeweils die Zeilen x mit dem größten d(x) (kann mehrere geben).

2) Wann ist die vertikale Einschränkung verletzt? Kann man das am VCG ablesen?
Ja. Wenn eine Führung des Netzes in der aktuellen Zeile eben Einschränkungen aus dem VCG verletzen würde (z.B. wenn der sagt ``Netz 1 über Netz 2'', aber genau das bei dieser Art der Verdrahtung nicht gilt), dann bildet man die Summe der d(x) in allen Spalten x, in denen die Einschränkung(en) verletzt würde(n) und zieht die mit K gewichtet von wn ab.

Herrzattacke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 20. Nov 2004 16:04

Beitrag von Herrzattacke »

A380 hat geschrieben:1) Wann addiere ich das B dazu? "Falls i Spalten der maximalen Dichte überspannt" steht im Skript, doch leider weiß ich nicht mehr genau was das nun bedeutet. Wie groß ist denn die maximale Dichte in dem Beispiel im Skript?
Gute Frage, da musste ich auch erst mal drüber nachdenken.
Zuerst berechnest du ja die Dichte der einzelnen (Vertikalen) Spalten, durch aufsummieren der Netze die über diese Spalten drüber gehen.

Beispiel:

Code: Alles auswählen

Netze: [1,3][2,3]
i      1    2    3
d(i)   1    1    2
Daraus ergibt sich dann, das das Netz [2,3] die Spalte mit Maximaler Dichte überspannt.

für Frage 2 hab ich jetzt keine Zeit, mach ich evtl. (falls keiner schneller ist) nach der Vorlesung ;)

HTH

EDIT: Da war wohl schon jemand schneller ;)

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

Beitrag von A380 »

Danke, beide Fragen nun gelöst.
Beim VCG hab ich immer "oben" geschaut und vergessen das der Algorithmus ja wechselt.
Das mit dem B ist nun auch klar. War ja einfach ;)

Herrzattacke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 20. Nov 2004 16:04

Beitrag von Herrzattacke »

Jetzt hab ich nochmal eine Frage.

Wenn ich die Vorschrift auf den Folien zur Berechnung der w_i benutze, bekomme ich aber für w_4 etwas anderes raus.
Bei der ersten Berechnung für oben ist mir folgendes aufgefallen.
In der Spalte 4 wird die Vertikale Einschränkung des VCG im bezug auf Netz 4 verletzt. Außerdem ist in Spalte 5 auch ein Vertikale Einschränkung verletzt (so wie es auf den Folien steht).

Daraus ergibt sich im Gegensatz zu den Folien:
\(w_4 = 1000 + 3 - 5*(3+2)\)

Außerdem stellt sich mir die Frage ob man den Yoeli-Algorithmus nicht insoweit vereinfachen könnte, dass man die beiden if-Statements zusammenfasst.

Code: Alles auswählen

for (c:=1; c <= channel_width; ++c) {
  selected_net[c] := 0;
  totalwght[c] := totalwght[c-1];
  foreach (n = "Netz mit rechtem Terminal in Spalte c") {
    if (wn + totalwght[xnmin-1] > totalwght[c]) {
      totalwght[c] := wn + totalwght[xnmin-1];
      selected_net[c] := n;
    }
  }
}
Natürlich kann man die Schleife nach 2 gefundenen Netzen abbrechen.

ARGH!!!
leider geht hier das plus in der Vorschau verloren.

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

Beitrag von A380 »

Herrzattacke hat geschrieben:Jetzt hab ich nochmal eine Frage.

In der Spalte 4 wird die Vertikale Einschränkung des VCG im bezug auf Netz 4 verletzt. Außerdem ist in Spalte 5 auch ein Vertikale Einschränkung verletzt (so wie es auf den Folien steht).
Wieso in Spalte 4? VCG 4 über 2, ist doch ok, oder? Nur in Spalte 5 ist 3 über 4, würde man also erst 4 nehmen hätte man hier den VCG verletzt.

Herrzattacke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 20. Nov 2004 16:04

Beitrag von Herrzattacke »

und wieso ist das dann bei w_2 so?

Spalte 2: OK
Spalte 3: Aktuelles Netz (2) im VCG unter 3 => constraint violation
Splate 4: Aktuelles Netz (2) im VCG unter 4 => constraint violation

Ist ja eigentilch auch klar, denn wenn du das obere Metallsegment nimmst um ein Netz zu routen, dann musst du nachschauen ob das Netz was du routen willst in der aktuellen Spalte den VCG verletzt.

oder sehe ich da was falsch?

--FYI--
Im Buch steht:
Sabih H. Gerez hat geschrieben: 3. For each column x for which an assignment of some net i to the curren side will create a vertical constraint violation, subtract K*d(x) from w_i; K is [...] This discourages the creation of vertical constraint violations.
Zuletzt geändert von Herrzattacke am 6. Feb 2007 20:21, insgesamt 4-mal geändert.
Alle sagten: "Das geht nicht!" Dann kam einer, der wusste das nicht und hat´s gemacht.

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

Beitrag von A380 »

w_2 ist im Graph unter 4 und auch unter 3, also unter beiden. Demnach auch d(x) von beiden. Also so wie du es jetzt aufgeschrieben hast.

Buch? ;)

Herrzattacke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 20. Nov 2004 16:04

Beitrag von Herrzattacke »

A380 hat geschrieben: w_2 ist im Graph unter 4 und auch unter 3, also unter beiden. Demnach auch d(x) von beiden. Also so wie du es jetzt aufgeschrieben hast.
Du meinst wohl meine erste Vermutung, das es sich um einen Fehler auf den Folien handelt, richtig ist?
Zuletzt geändert von Herrzattacke am 6. Feb 2007 21:01, insgesamt 2-mal geändert.
Alle sagten: "Das geht nicht!" Dann kam einer, der wusste das nicht und hat´s gemacht.

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

Beitrag von A380 »

Im ersten Post ging es um w_4 im zweiten um w_2.
Das was du über w_2 geschrieben hast halte ich für richtig, das über w_4 für falsch.

Herrzattacke
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 20. Nov 2004 16:04

Beitrag von Herrzattacke »

stimmt, du hast recht, bei w_4 hab ich falsch gelegen.
Alle sagten: "Das geht nicht!" Dann kam einer, der wusste das nicht und hat´s gemacht.

Antworten

Zurück zu „Archiv“