Schaltungsanalyse Widerstandsnetzwerk

A

Arne Lüllmann

Guest
Hallo,

kennt jemand einen schlauen Algorithmus zur Erstellung eines
"vollständigen Baumes", wie er bspw für das Maschenstromverfahren
gebraucht wird? Es geht dabei um zufällige Netzwerke aus Widerständen,
die kreuz und quer miteinander verdrahtet sind.

Herzlichen Dank,
Arne
 
Arne Lüllmann wrote:
Hallo,

kennt jemand einen schlauen Algorithmus zur Erstellung eines
"vollständigen Baumes", wie er bspw für das Maschenstromverfahren
gebraucht wird? Es geht dabei um zufällige Netzwerke aus Widerständen,
die kreuz und quer miteinander verdrahtet sind.
Click to expand...
Der Algorithmus, den Du suchst, nennt sich DFS (Depth First Search oder
Tiefensuche). Der kann einen beliebigen Graphen durchlaufen und generiert
dabei einen Spannbaum.

Man fängt an einem Knoten an, markiert ihn als "besucht", packt alle seine
direkten Nachbarn auf einen Stack und nimmt dann den nächsten vom Stack und
macht das selbe. Findet man einen Knoten, der bereits besucht ist, so kommt
er natürlich nicht mehr auf den Stack. Ist der Knoten noch nicht besucht,
so stellt dies eine Kante im Spannbaum vom aktuelle bearbeiteten zu diesem
Knoten dar.

Ausführlichere Erläuterung gibts zum Beispiel bei Wikipedia:
http://de.wikipedia.org/wiki/Tiefensuche

Gruß,

Andreas
--
..------- - - ---.
| Andreas Schroeder - www.a-netz.de |
'-----------------------------------'
 
Arne LĂźllmann wrote:

kennt jemand einen schlauen Algorithmus zur Erstellung eines
"vollständigen Baumes", wie er bspw fßr das Maschenstromverfahren
gebraucht wird? Es geht dabei um zufällige Netzwerke aus Widerständen,
die kreuz und quer miteinander verdrahtet sind.
Click to expand...
Bist du dir sicher, dass du einen vollständigen Graphen haben willst
(also von der Größe (n^2)/2 mal so groß wie Eingangsknoten)? Also "jeder
mit jedem"? Schau dir mal den Floyd-Algorithmus und den Dijkstra an, die
berechnen jeweils kĂźrzeste Wege zwischen zwei Knoten - dann noch
dynamisches Programmieren und das sollte recht effizient zu lĂśsen sein.

Aber irgendwie weiß ich nicht wirklich, ob das das ist, was du suchst.

Gruß,
Johannes
 
* Johannes Bauer <dfnsonfsduifb@gmx.de> [2006-03-28 18:24]:
Arne Lüllmann wrote:
kennt jemand einen schlauen Algorithmus zur Erstellung eines
"vollständigen Baumes", wie er bspw für das Maschenstromverfahren
gebraucht wird? Es geht dabei um zufällige Netzwerke aus Widerständen,
die kreuz und quer miteinander verdrahtet sind.

Bist du dir sicher, dass du einen vollständigen Graphen haben willst
(also von der Größe (n^2)/2 mal so groß wie Eingangsknoten)? Also "jeder
mit jedem"? Schau dir mal den Floyd-Algorithmus und den Dijkstra an, die
berechnen jeweils kürzeste Wege zwischen zwei Knoten - dann noch
dynamisches Programmieren und das sollte recht effizient zu lösen sein.
Click to expand...
Gesucht wird eher ein "Minimaler Spannbaum" (besser: irgendein
Spannbaum, da die Kanten ja keine Gewichte haben). Dafür gibt es die
Algorithmen von Kruskal und Prim, die beide einfach zu verstehen sind.
 
Lars Noschinski wrote:

Gesucht wird eher ein "Minimaler Spannbaum" (besser: irgendein
Spannbaum, da die Kanten ja keine Gewichte haben). DafĂźr gibt es die
Algorithmen von Kruskal und Prim, die beide einfach zu verstehen sind.
Click to expand...
Ah okay, ich bin durch das Wort "vollständig" da auf die falsche Fährte
gelockt worden.

Viele Grüße,
Johannes
 
Johannes Bauer schrieb:
Arne LĂźllmann wrote:

kennt jemand einen schlauen Algorithmus zur Erstellung eines
"vollständigen Baumes", wie er bspw fßr das Maschenstromverfahren
gebraucht wird? Es geht dabei um zufällige Netzwerke aus Widerständen,
die kreuz und quer miteinander verdrahtet sind.

Bist du dir sicher, dass du einen vollständigen Graphen haben willst
(also von der Größe (n^2)/2 mal so groß wie Eingangsknoten)? Also "jeder
mit jedem"? Schau dir mal den Floyd-Algorithmus und den Dijkstra an, die
berechnen jeweils kĂźrzeste Wege zwischen zwei Knoten - dann noch
dynamisches Programmieren und das sollte recht effizient zu lĂśsen sein.

Aber irgendwie weiß ich nicht wirklich, ob das das ist, was du suchst.

Gruß,
Johannes
Click to expand...
Vielen Dank fĂźr die Antworten.
Na ja, es geht um das Aufstellen des lin. Gleichungssystems aus Maschen-
und Knotenregel. Um die Mschen zu Identifizieren brauche ich einen
Algorithmus. Und hier bietet das Verfahren mit vollständigem Baum - d.h.
ein Teilgraph, der alle Knoten miteinander verbindet, ohne eine
geschlossene Masche entstehen zu lassen - und dem komplementären Baum -
d.h. der Rest - einen Weg zur Bestimmung aller unabhängigen Maschen.

Bin mir nicht sicher, ob mir das Wissen um die kĂźrzeste Verbindung da
weiterhilft. Bin auf diese Verfahren auch schon gestoßen. Aber auf eine
Idee zum Verfahren haben sie mich noch nicht gebracht.

schöne Grüße,
Arne
 
Lars Noschinski schrieb:
:
Arne Lüllmann wrote:
kennt jemand einen schlauen Algorithmus zur Erstellung eines
"vollständigen Baumes", wie er bspw für das Maschenstromverfahren
gebraucht wird? Es geht dabei um zufällige Netzwerke aus Widerständen,
die kreuz und quer miteinander verdrahtet sind.

Bist du dir sicher, dass du einen vollständigen Graphen haben willst
(also von der Größe (n^2)/2 mal so groß wie Eingangsknoten)? Also "jeder
mit jedem"? Schau dir mal den Floyd-Algorithmus und den Dijkstra an, die
berechnen jeweils kürzeste Wege zwischen zwei Knoten - dann noch
dynamisches Programmieren und das sollte recht effizient zu lösen sein.

Gesucht wird eher ein "Minimaler Spannbaum" (besser: irgendein
Spannbaum, da die Kanten ja keine Gewichte haben). Dafür gibt es die
Algorithmen von Kruskal und Prim, die beide einfach zu verstehen sind.
Click to expand...
ah danke, da werde ich gleich mal nachschauen. Deine Antwort hatte
irgendwie Verspätung bei mir.

viele Grüße,
Arne
 
* Arne Luellmann <arne.luellmann@stud.uni-goettingen.de> [2006-03-28 18:40]:
Bin mir nicht sicher, ob mir das Wissen um die kürzeste Verbindung da
weiterhilft. Bin auf diese Verfahren auch schon gestoßen. Aber auf eine Idee
zum Verfahren haben sie mich noch nicht gebracht.
Click to expand...
Wie gesagt, ein (minimaler) Spannbaum ist das, was du suchst.

http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal
http://de.wikipedia.org/wiki/Algorithmus_von_Prim

für eine erste Anlaufstelle.
 
* Arne Luellmann <arne.luellmann@stud.uni-goettingen.de> [2006-03-28 18:41]:
ah danke, da werde ich gleich mal nachschauen. Deine Antwort hatte irgendwie
Verspätung bei mir.
Click to expand...
Wenn man sich vorstellt, dass es früher durchaus Newslaufzeiten von
mehreren Tagen gab ... ;)
 
Lars Noschinski schrieb:
* Arne Luellmann <arne.luellmann@stud.uni-goettingen.de> [2006-03-28
18:40]:
Bin mir nicht sicher, ob mir das Wissen um die kürzeste Verbindung da
weiterhilft. Bin auf diese Verfahren auch schon gestoßen. Aber auf
eine Idee zum Verfahren haben sie mich noch nicht gebracht.

Wie gesagt, ein (minimaler) Spannbaum ist das, was du suchst.

http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal
http://de.wikipedia.org/wiki/Algorithmus_von_Prim

für eine erste Anlaufstelle.
Click to expand...
genau, gerade ausgedruckt! Bin sehr dankbar!
Arne
 
"Arne Lüllmann" <arne.luellmann@stud.uni-goettingen.de> schrieb im
Newsbeitrag news:e0b9pc$h57$1@gwdu112.gwdg.de...
Hallo,

kennt jemand einen schlauen Algorithmus zur Erstellung eines
"vollständigen Baumes", wie er bspw für das Maschenstromverfahren
gebraucht wird? Es geht dabei um zufällige Netzwerke aus Widerständen,
die kreuz und quer miteinander verdrahtet sind.

Herzlichen Dank,
Arne
Click to expand...
Hallo Arne,

Wenn es um die Berechnung mit einem Computer geht, dann kannst du stur
eine Matrix aufstellen und mit dem Gauß-Algo lösen.

Grundlagen und Rechneverfahren der Elektrotechnik
Gerhard Schnell, Konrad Hoyer, Martin Vömel
Vieweg Verlag
ISBN 3-528-04530-2

Und hier kannst du es einsehen oder ausleihen,
http://kirke.hbz-nrw.de/dcb/Alle_015/Buecher_23/in_NRW_35/003324951.html

Gruß
Helmut
 
Hallo,

Arne Luellmann schrieb:
Na ja, es geht um das Aufstellen des lin. Gleichungssystems aus Maschen-
und Knotenregel. Um die Mschen zu Identifizieren brauche ich einen
Algorithmus. Und hier bietet das Verfahren mit vollständigem Baum - d.h.
ein Teilgraph, der alle Knoten miteinander verbindet, ohne eine
geschlossene Masche entstehen zu lassen - und dem komplementären Baum -
d.h. der Rest - einen Weg zur Bestimmung aller unabhängigen Maschen.
Click to expand...
Hmm... wieso nimmst Du nicht einfach einen normalen Zyklentest? Also
z.B. Tiefensuche, dabei den "Vater" merken. Jeder schon besuchten
Nachfolger eines Knotens, der nicht der eigene "Vater" ist, bedeutet
einen Zyklus.

Gruesse,

Norbert Stuhrmann
 
Norbert Stuhrmann schrieb:
Hallo,

Arne Luellmann schrieb:
Na ja, es geht um das Aufstellen des lin. Gleichungssystems aus Maschen-
und Knotenregel. Um die Mschen zu Identifizieren brauche ich einen
Algorithmus. Und hier bietet das Verfahren mit vollständigem Baum - d.h.
ein Teilgraph, der alle Knoten miteinander verbindet, ohne eine
geschlossene Masche entstehen zu lassen - und dem komplementären Baum -
d.h. der Rest - einen Weg zur Bestimmung aller unabhängigen Maschen.

Hmm... wieso nimmst Du nicht einfach einen normalen Zyklentest? Also
z.B. Tiefensuche, dabei den "Vater" merken. Jeder schon besuchten
Nachfolger eines Knotens, der nicht der eigene "Vater" ist, bedeutet
einen Zyklus.

Gruesse,

Norbert Stuhrmann
Click to expand...
Vielen Dank!
KĂśnnte man bspw. Spice fĂźr einen Test des eigenen Ergebnisses benutzen,
wenn man eine entsprechende Verbindungsliste erzeugt? Und zwar auch noch
für Netzwerke mit ca. 10.000 Widerständen unregelmäßig angeordnet?

Gruß,
Arne
 
"Arne Luellmann" <arne.luellmann@stud.uni-goettingen.de> schrieb im
Newsbeitrag news:e0ddep$2p0h$1@gwdu112.gwdg.de...
Norbert Stuhrmann schrieb:
Hallo,

Arne Luellmann schrieb:
Na ja, es geht um das Aufstellen des lin. Gleichungssystems aus
Maschen-
und Knotenregel. Um die Mschen zu Identifizieren brauche ich einen
Algorithmus. Und hier bietet das Verfahren mit vollständigem Baum -
d.h.
ein Teilgraph, der alle Knoten miteinander verbindet, ohne eine
geschlossene Masche entstehen zu lassen - und dem komplementären Baum -
d.h. der Rest - einen Weg zur Bestimmung aller unabhängigen Maschen.

Hmm... wieso nimmst Du nicht einfach einen normalen Zyklentest? Also
z.B. Tiefensuche, dabei den "Vater" merken. Jeder schon besuchten
Nachfolger eines Knotens, der nicht der eigene "Vater" ist, bedeutet
einen Zyklus.

Gruesse,

Norbert Stuhrmann

Vielen Dank!
Könnte man bspw. Spice für einen Test des eigenen Ergebnisses benutzen,
wenn man eine entsprechende Verbindungsliste erzeugt? Und zwar auch noch
für Netzwerke mit ca. 10.000 Widerständen unregelmäßig angeordnet?

Gruß,
Arne
Click to expand...
Hallo Arne,

SPICE sollte das problemlos können.

Ein gutes und trotzdem kostenloses SPICE-Programm ist
LTspice/SwitcherCADIII.
Es hat keienrlei Begrenzung der Schaltungsgröße und hat eine graphische
Schaltplaneingabe, kann aber auch direkt Netzlisten verarbeiten.
Also mit ein paar tausend Widerständen habe ich schon mal mit LTspice
simuliert.

http://ltspice.linear.com/software/swcadiii.exe

Falls du Probleme mit dem Programm hast, dann kannst du in der User-Group
nachfragen.

http://groups.yahoo.com/group/LTspice/

Gruß
Helmut
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top