Hallo, ich programmiere zur Zeit ein Programm wo man ein Diagramm erstellen kann. Die Elemente soll mit einem Autorouter verbunden werden können. Leider finde ich im Inet nichts zum Thema Autorouter. Auch das Stichwort Evolutionäre Algorithmen haben mich nicht weiter gebracht. Hat Jemand eine einfach Idee wie ein Autorouter funktionieren könnte? Als Eingang in den Autorouter sollen zwei Punkte übergeben werden und raus kommen soll eine List von Punkten, durch die die Verbindung läuft. Mein Ansatz alle Möglichkeiten auszuprobieren und zu bewerten hat nicht geklappt, da das einfach zu langsam ist. Moritz
:
Bearbeitet durch User
Man findet schon einiges, wenn man weiss was man sucht -- und sucht. Tal Dayan's Thesis fand ich ganz interessant zum Thema topologisches Routing -- es gibt noch mindestens zwei weitere Arbeiten zum Thema, eine davon frei verfügbar. Aber womöglich suchst Du eher etwas zum Geometrischen Routing, Stichwort wäre dann Maze-Router. Oder für Pfade über vorgegebene Punkte "Dijkstra shortest path search". (Das Problem beim PCB-Routing ist ja eher, dass man beliebige Wege hat.) Ich habe nicht wirklich verstanden was Du genau suchst -- so in Richtung Schaltplaneditor, wo man die Symbole verschiebt und die Verbindungen dann selbstständig verlegt werden? Daran hatte ich auch schon mal gedacht -- ist wohl einfacher als PCB Routing, aber auch nicht ganz trivial, und es soll ja dann für die Menschen irgendwie "schön" aussehen.
Moritz M. schrieb: > Hallo, > > ich programmiere zur Zeit ein Programm wo man ein Diagramm erstellen > kann. Die Elemente soll mit einem Autorouter verbunden werden können. > Leider finde ich im Inet nichts zum Thema Autorouter. Auch das Stichwort > Evolutionäre Algorithmen haben mich nicht weiter gebracht. Hat Jemand > eine einfach Idee wie ein Autorouter funktionieren könnte? Einfach ist das leider nicht zu machen. Autorouter sind sehr komplex. > Mein Ansatz alle Möglichkeiten auszuprobieren und zu bewerten hat nicht > geklappt, da das einfach zu langsam ist. Wundert mich nicht. Ich denke das Problem des Autorouters bei einem elektronischen Layout ist in etwa mit dem TSP (http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden) vergleichbar und damit wahrscheinlich NP-Vollständig. Da helfen nur Heuristiken. Das ist ein weites Feld. Das ganze läge dann in O(n!), wenn du n Knoten hast. Bei 10 Knoten also schon über 3 Millionen Möglichkeiten. Das steigt so heftig an, da kannst du deine Brute-Force Methode leider vergessen :-( Was genau ist eigentich mit "Diagramm" gemeint? Wegsuche auf einem Graph mit Kantengewichten geht mit Dikstra. Grade nochmal nachgeschaut, laut Wikipedia scheint das Routing tatsächlich ein TSP zu sein: > Die größte Instanz eines (symmetrischen) Rundreiseproblems, die bisher > nachweisbar optimal gelöst wurde, ist ein Planungsproblem für das Layout > integrierter Schaltkreise mit 33.810 Knoten. In dem Wikilink oben stehen übrigens einige sehr interessante Heuristiken für das Problem. Da wirst du sicher einiges finden, und es ist anzunehmen dass kommerzielle Autorouter diese ebenfalls nutzen. gruß cyblord
:
Bearbeitet durch User
cyblord ---- schrieb: > Das ist ein weites Feld. Ja. Den obigen Wikipedia Artikel muss ich auch mal lesen... Kennst Du zufällig eine gute praktische Berechnung für Streiner-Bäume? Momentan benutze ich einfach einen Minimalen Spannbaum, das ist ja recht trivial. Ein paar Steiner-Punkte wären schon nett, aber was ich dazu so gefunden habe war recht kompliziert, mir würde eine einfache Heuristik genügen.
Da du sagst, du möchtest Diagramme erzeugen: Dann hast da ja wahrscheinlich ein zugrunde liegendes Zeichenraster, in dem du die Elemente platzierst und in dem auch die Verbindungslinien gezeichnet werden. Für so etwas könnte man Cell-basierte Autorouter ansetzen. Einen einfachen Algorithmus kann ich dir auch ausformulieren, der sich einen Weg durch die Zellen von A nach B sucht, keine anderen bestehenden Verbindungen kreuzt und gar nicht mal so aufwändig ist. Aber ob die Ergebnisse beim Diagrammzeichnen so berauschend sind, ...
:
Bearbeitet durch User
Karl Heinz Buchegger schrieb: > Für so etwas könnte man Cell-basierte Autorouter ansetzen. Einen > einfachen Algorithmus kann ich dir auch ausformulieren, der sich einen > Weg durch die Zellen von A nach B sucht, keine anderen bestehenden > Verbindungen kreuzt und gar nicht mal so aufwändig ist. Ah. jetzt hab ich es wieder. Seit gestern Abend hab ich in meinem Gedächtnis nach dem Namen des Algorithmuses gekramt und bin nicht drauf gekommen. Lee-Algorithmus http://en.wikipedia.org/wiki/Lee_algorithm Hab ich mal auf einem Z80 in Assembler implementiert. Funktioniert an sich nicht so schlecht. Aber wie gesagt: ob so was prinzipiell für Diagramme eine gute Idee ist ... müsste man wahrscheinlich probieren. Das Problem ist die Reihenfolge in der die Verbindungen verlegt werden. Je nachdem kriegt man unterschiedlich 'gute' Ergebnisse.
:
Bearbeitet durch User
Karl Heinz Buchegger schrieb: > keine anderen bestehenden > Verbindungen kreuzt Weder bei Schaltplänen noch bei Diagrammen ist Kreuzungfreiheit erforderlich, das gilt nur auf Leiterplatten. Im Gegenteil, erzungenes Umgehen von Kreuzungen macht die Sache nur unübersichtlich. Gruss Reinhard
Reinhard Kern schrieb: > Karl Heinz Buchegger schrieb: >> keine anderen bestehenden >> Verbindungen kreuzt > > Weder bei Schaltplänen noch bei Diagrammen ist Kreuzungfreiheit > erforderlich, das gilt nur auf Leiterplatten. Im Gegenteil, erzungenes > Umgehen von Kreuzungen macht die Sache nur unübersichtlich. Eben. Drum denke ich auch, dass einem ein Autorouter wie er im Platinendesign eingesetzt wird, nicht wirklich weiter bringt. OK. Ein Autorouter könnte Verbindungen suchen, die nicht durch Diagramm-Symbole durchlaufen. Aber ob das so hilfreich ist?
Vielen Dank an alle. Also genau geht es um einen Editor für Neuronale Netze (dem entsprechend mehr in Richtung Schaltplan editor). Ich werde mal unter euren Stichpunkten weiter suchen. Moritz
Karl Heinz Buchegger schrieb: > Verbindungen suchen, die nicht durch Diagramm-Symbole durchlaufen. Nicht durch Symbole und Text, und dann möglichst wenige Knicke und Kreuzungen und natürlich möglichst kurze Pfade. Und dann eventuell noch eine Bündelung, also möglichst viele Leitungen parallel direkt nebeneinander. Ja müsste man mal probieren.
Tach zusammen, das Feld der Informatik, das sich mit dem genannten Problem beschäftigt nennt sich "Graph Drawing" (eine wirklich gute dt. ÜS fällt mir gerade nicht ein). Eine Anlaufstelle wäre: http://graphdrawing.org - hier sind auch die entsprechenden LNCS-Bände aufgeführt. Ob man jetzt einen TSP, MST, BFS, ... braucht, bestimmt die Art des Graphen (gerichtet, zyklisch, planar, ...) und wie ausgefuchst man das Ganze gestaltet (will man isomorphe Subgraphen?, usw...). Normalerweise teilt man den Gesamtprozess in Einzelschritte auf, von denen allerdings viele auch NP-vollständig sind, deshalb muss man eigentlich so gut wie immer auf Heuristiken setzen und vorher entsprechende Annahmen treffen / sich mit Einschränkungen abfinden. Soll heissen: Es kommt auf das genaue Problem an und was man sich davon erwartet. Viele Grüße, tk
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.