Ma 'ne frage zu P, erste Aufgabe:

"Die Kostenfunktion für die Kanten gibt die durchschnittliche Leitungsverzögerung auf diesen Wegen an."

Es gibt z.B. keine direkte Kante von A nach A, es müsste also ein Sternchen in die Adjazenzmatrix.
Andereseits: Die Leitungsverzögerung ist von A nach A wohl 0, es müsste also eine 0 in die Matrix.

Was gehört da rein?

Ich behaupte mal ein Stern, da es - soweit meine Erinnerung ans Skript richtig ist, in einem ungerichteten Graphen keine Schlingen gibt (weder graphisch, noch von den Tupeln her). Zudem passt das Sternchen ja auch viel besser, da wir die örtliche Leistungsverzögerung gar nicht kennen. 0 wäre ja höchstens runtergerundet richtig. :)

ich bin für 0 ;)


0 oder *??
hier bitte wählen:0*42


Umfrage nur für echte P3'ler!

Antworten:
0: [img]http://www.fb18.de/gfx/graphics/r7.gif[/img]
*: [img]http://www.fb18.de/gfx/graphics/b21.gif[/img]
42: [img]http://www.fb18.de/gfx/graphics/g12.gif[/img]

Es gibt z.B. keine direkte Kante von A nach A, es müsste also ein Sternchen in die Adjazenzmatrix.
Andereseits: Die Leitungsverzögerung ist von A nach A wohl 0, es müsste also eine 0 in die Matrix.

ALso eine Leitungsverzögerung von 0 wäre eine ideale Leitung in der die Signale sofort übertragen werden, nicht keine Kante :)
Im übrigen Zitat vom Aufgabenzettel:
"Stellen Sie diesen bewerteten ungerichteten Graphen als Adjazenzmatrix dar. Verwenden Sie * als spezielle Markierung für fehlende Kanten."

Ich denke wer die Aufgaben ganz liest, weiß genug [img]http://www.sternenvolk.de/symb/28.gif[/img]

ALso eine Leitungsverzögerung von 0 wäre eine ideale Leitung in der die Signale sofort übertragen werden, nicht keine Kante :)
Im übrigen Zitat vom Aufgabenzettel:
"Stellen Sie diesen bewerteten ungerichteten Graphen als Adjazenzmatrix dar. Verwenden Sie * als spezielle Markierung für fehlende Kanten."

So denn habe auch ich fuer das Sternlein gestimmt ob dieses einleuchtenden Epistels.

wer sagt, dass da keine kanten eingezeichnet sind?
die könnt ihr nur nicht sehen, von einem punkt zu sich selber ist nämlich nicht so weit..

wer sagt, dass da keine kanten eingezeichnet sind?
die könnt ihr nur nicht sehen, von einem punkt zu sich selber ist nämlich nicht so weit..

Jetzt verwirre bitte nicht die armen Leute mit so boesen Scherzen, am Ende glauben die den Stuss noch [img]http://www.sternenvolk.de/symb/7.gif[/img]

wer sagt, dass da keine kanten eingezeichnet sind?
die könnt ihr nur nicht sehen, von einem punkt zu sich selber ist nämlich nicht so weit..

Vielleicht löst ja Folie I-129 das Problem, zählen also nur Kanten, deren Länge > 0 ist [img]http://www.sternenvolk.de/symb/28.gif[/img]

Ich hab auch Stern genommen. TriPhoenix hat die Begründung schon geliefert [img]http://www.sternenvolk.de/symb/25.gif[/img]

Ich bin ebenfalls ein Anhänger des * [img]http://www.sternenvolk.de/symb/22.gif[/img]
Sieht dann in der fertigen Matrix besser aus, als so'ne
hässlichen nullen!

Ich denke auch *, denn sonst müsste an dem Knoten eine Kante zu sich selbst liegen.

Hab mal ne andere Frage!
Bei Aufgabe 3 und dem Algo von Prim usw.! Verstehe ich das richtig das jeder Knoten mind. EIN MAL "getroffen" werden muss, oder wie? Bzw. wie würde es denn aussehen, wenn ich bei C starte:
1) BD = 7
2) DE = 16
3) EH = 12
4) HI = 11
5) IG = 25
6) GF = 12
7) FC = 10

Ist das dann so richtig?

welche wirkung hat denn auf deine vorgehensweise die tatsache, das du bei C angefangen hast?,
du sollst natürlich im ersten schritt nur die kanten betrachen, die mit C verbunden sind, danach die, die mit C oder F verbunden sind,
da (C F) die erste gewählte kante ist,

und in den nächsten schritten sollst du nicht immer beim endpunkt der letztgewählten kante weitermachen, sonder jeweils die kürzeste unter den kanten wählen, die an den bisherigen teilbaum grenzen, also zum beispiel im 2. schritt die kürzeste, die mit C oder mit F verbunden ist

so stehts ja auch in den 3 sätzen des algorithmus ;)

und ja jeder knoten wird zwangsläufig dabei 1x getroffen, bei deinem vorgehen natürlich nicht unbedingt ;)

Ich Idiot! Startpunkt war B - nicht C!
Also wäre das bei B angefangen:
1) BD
2) DE
3) EH
4) HI
5) HG
6) GF
7) FC
8) BA

stimmt das jetzt oder check' ich da was nicht?

wie gesagt, alle nachbarkanten betrachten, nicht nur die vom letzten endpunkt

oh jetzt ist ja anders, so ists richtig denke ich

Oha, interessant! Ich hätte nicht gedacht, dass ich ausgehend vom Startpunkt D eine andere Lösung (mit gleicher Gesamtlänge des Baumes bei Abweichung einer Kante) erhalte. Ergo gibt es hier also mindestens 2 MST, oder?

si

(bei gleichen kantenlaengen wird eine zufällig ausgewählt, das kann komplexe folgen haben)

"Komplexe" Folgen dürfte das eher nicht haben, weil kaum alle Folgekanten dieselbe Länge haben werden.

hehe, na gut einfache folgen ;)

Hallo!

Ich wollte mal vergleichen, ob wir alle das gleiche raus haben bei Aufgabe 2.

Dijkstras Algorithmus

—————————————-

(A 0 A), (B 23 A), (C 26 A)

—————————————-

(B 23 A), (C 26 A), (E 51 B), (D 30 B)

—————————————-

(C 26 A), (E 51 B), (D 30 B), (F 36 C)

—————————————-

(D 30 B), (F 36 C), (E 46 D), (G 50 D), (H 65 D)

—————————————-

(F 36 C), (E 46 D), (H 65 D), (I 77 F), (G 48 F)

—————————————-

(E 46 D), (I 77 F), (G 48 F), (H 58 E)

—————————————-

(G 48 F), (H 58 E), (I 73 G)

—————————————-

(H 58 E), (I 69 H)

—————————————-

(I 69 H)

abgesehen von der sortierung der randknotenliste ist das fein, und sortierung müsste egal sein

Hilfe!

Kann mir mal jemand einen Tip geben, wie ich an Aufgabe 2 rangehe???? Je mehr ich ausprobiere, umso weniger seh ich durch !

hmm tipp, ich hatte mal einen leicht komplizierten weg
aufgeschrieben, der aber immerhin die randkantenliste sortiert hält

1.
man muss wissen, welche knoten man schon hat (in eine liste z.b.),
man braucht eine liste der randkanten (die man immer sortiert hält, mit entfernung vom startknoten!)

2.
ne schleife bis liste der randkanten leer:
erste kante der randkanten nehmen,
dann hat man auch den zugehoerigen neuen knoten,
diesen in die liste der alten knoten tun,

die neu hinzukommenden randkanten bestimmen
(mit entfernung zum startpunkt),
und jeweils in die liste der bisherigen randkanten einfuegen

3.
das einfuegen einer neuen kante:
die liste der bisherigen randkanten durchgehen,
jede kante anschauen, bei größerer entfernung davor einfuegen,

dann die liste weiter durchlaufen und die alte kante
zum gleichen endpunkt löschen, falls vorhanden

(hat die alte kante eine kleinere entfernung, dann natürlich die alte behalten und die neue verwerfen)

4.
irgendwo zwischendurch die ergebnisse mal ausgeben,

Hilfe!

Kann mir mal jemand einen Tip geben, wie ich an Aufgabe 2 rangehe???? Je mehr ich ausprobiere, umso weniger seh ich durch !

1. Frueher anfangen
2. Zunaechst auf Papier per Hand die ersten Schritte ausprobieren
3. sich ueber den absolut miesen, vorgegebenen Quellcode aergern (Graph.java… schauder)

abgesehen von der sortierung der randknotenliste ist das fein, und sortierung müsste egal sein

Meinst Du nach Knotenbezeichnung sortiert oder nach Gesamtkosten vom Startknoten?

schau mal hin ;):

http://vsis-www.informatik.uni-hamburg.de/teaching/ws-02.03/p3/a4/dijkstrabsp.pdf

edit

Frueher anfangen

und selber erst um 15.xx hier mit dijkstra ankommen ;)

Frueher anfangen

und selber erst um 15.xx hier mit dijkstra ankommen ;)

Naja Ergebnisse zum Vergleichen posten und die totale Verzweiglung ist aber schon ein Unterschied [img]http://www.sternenvolk.de/symb/25.gif[/img]



NP: Harald Lesch - "unwahrscheinlich… unwahrscheinlich!"

EDIT: Ich habe mal drei kleine Kostproben auf meine Homepage gestellt, falls jemand den begnadeten Entertainer (mehr Popstar als Physik-Professer) noch nicht kennen sollte.

http://www.geocities.com/ackehurst/

Ich bin für einen extra Lesch Bereich! B3 ab 0h Rockt!

Ich bin für einen extra Lesch Bereich! B3 ab 0h Rockt!

Ich habe momentan drei kleine MP3s von ihm auf der Page.

www.geocities.com/ackehurst/

EDIT: jetzt sinds 4