Algoritmus nalezení smyček v el. obvodu – C / C++ – Fórum – Programujte.com

Čelím vskutku komplexnímu problému. Píšu modul do programu, který provádí analýzu el. obvodu pomocí smyčkových proudů (pokud neznáte tak -> http://user.unob.cz/…L/Tema04.htm). Můj problém je najití NEZÁVISLÝCH smyček (závislí mi to hledá furt ...). Už sem vyzkoušel vše co mne napadlo a nyní opravdu netuším. Pro najití smyček používám hledání nejkratší cesty v grafu (můj nejnovější nápad zahrnoval i analýzu uzlů (v obvodu) a podle toho se upravovali délky hran mezi součástkami...ale...hledá to nezávislé smyčky jen někdy -> pokud tomu sedne topologie obvodu). Kdybych měl více času, asi bych se pokusil řešit problém nějak jinak (třeba evolučním algoritmem...a i ten by asi nepomohl). Já ho však nemám, a proto se ptám jestli někoho nenapadá nějaké elegantní řešení problému ...  

Skús algoritmus hladania komponent grafu. Tu je niečo z Wikipedie: http://en.wikipedia.org/…ph_theory%29

Jednoduchý algoritmus, ktorý ti zrejme bude stačiť, je popísaný v knihe Algoritmy a programovací techniky (Topfer), ktoru najdes aj na internete (ulozto). Je tam na strane 138.

To se bohužel nedá použít ... smyčky můžou mít stejnou topologii ...

EDIT:
navíc graf obvodu je souvislí, komponenty mohu získat pouze když je graf nesouvislí...takže ne, tato metoda nejde použít

Nedokazu si moc dobre predstavit, jak by hledani komponent grafu souviselo s problemem hledani smysek v obvodu. Co takhle hledani cyklu? http://en.wikipedia.org/wiki/Cycle_detection

cycle detection mi není k ničemu, opravdu vím jak najít v obvodu (převedeném na graf) smyčku. Ale já chci smyčky nezávislé a né ZÁVISLÉ. Toto je právě ten problém který řeším ... proto jsem přidal link s návodem na smyčkové proudy protože nestačí pouze ovládat programování k vyřešení tohoto problému ale ještě metodu smyčkových proudů ...

#5 Sefiros

To je jedno. Hlavni je, aby se v grafu obvodu nasly vsechny, resp. aby vsechny hrany byly v nejake smycce. V nejhorsim pripade bude vysledna soustava pro proudu preurcena, ale konzistentni, cili resitelna!

ne, jediná závislá smyčka způsobí (i kdyby všechny ostatní byli nezávislé) neřešitelnost výsledné soustavy rovnic ... pokud se pletu tak mi prosím podej důkaz

#7 Sefiros

Jak jsem uz napsal, pridani "zavisle" smycky na resitelnosti soustavy nic nezmeni. Proto se ji take rika zavisla, protoze ve vysledne soustave rovnic vytvori rovnici linearne zavislou na zbylych rovnicich. Predpokladam, ze nekdo s minimalni znalosti linearni algebry, resitelnosti soustav linearnich rovnic a Kirchhoffovych zakonu si to dokaze sam.

Ano, vytvoří rovnici lineárně závislou, ale ... sakra jak to říci, to je prostě ten problém. Prostě to nejde ! Tak si zkus ručně ňákej obvod propočítat a uvidíš (pokud tam teda najdeš chybu ...). 

EDIT: A možnost, že budu hledat všechny možný kombinace smyček v obvodu nepřichází v úvahu (u velkejch obvodů bych to něchtěl vidět ...) ... to má do elegantního řešení daleko .... sem se proto ptal jestli někoho nenapadne jak od sebe odlišit smyčky závislé a nezávislé...