Finden Sie Stromkreis mit gegebenem Widerstand

Question

Ich brauche etwas Hilfe mit dem folgenden Problem:
Angesichts einer Reihe von Resistenzen, müssen Schaltung mit gegebenem Widerstand (d. H. Wir wählen einige Widerstände und konstruieren Schaltung). Nur parallele und sequentielle Verbindungen sind erlaubt. So ist die formale Definition einer solchen Schaltung ist die folgende:

Circuit = Resistance | (Sequential (Circuit) (Circuit a)) | 
(Parallel (Circuit) (Circuit)) 

Die Gesamtzahl der Schaltungen mit N unmarkierten Widerstände (wo alle Widerstände verwendet werden) ist A000084 (Danke Axel Kemper). Aber in meinem Fall sind Widerstände beschriftet und ich weiß nicht, wie man alle Schaltkreise effizient überprüft.

Anzahl der Widerstände ist etwa 15, ist es möglich, dieses Problem zu lösen?

UPD. Widerstände können unterschiedliche Widerstände haben. Und natürlich können einige Widerstände nicht erreicht werden, in diesem Fall sagen wir einfach, dass es keine Lösungen gibt.

Answer 1

Integer Sequenz A000084 listet die Anzahl der Serie-parallele Netzwerke mit n unbeschrifteten Kanten. Auch als Jochketten von Cayley und MacMahon bezeichnet. MacMahons Papier ist online.

Die ersten 15 Elemente der Folge: 1, 2, 4, 10, 24, 66, 180, 522, 1532, 4624, 14136, 43930, 137.908, 437.502, 1399068

Wenn die Widerstände verschiedene Widerstandswerte, sie sind nicht "unmarkiert".

Die Anzahl der verschiedenen Gesamtwiderstände ist geringer als die Anzahl der Netzwerke.

Mit Blick auf die Zahlen ist Brute-Force-Enumeration wahrscheinlich für moderate Werte von n möglich.

Es ist nicht möglich, jeden erdenklichen Gesamtwiderstand genau abzugleichen. Wie in einem Kommentar erwähnt: Die Anzahl der 15 Widerstände könnte zu klein sein, um den erforderlichen Wert zu erreichen. Anderes Beispiel: Wenn alle 15 Restore jeweils 1 Ohm haben, darf der Gesamtwiderstand nicht kleiner als 1/15 Ohm sein.

Blick auf Seite 70 von Analytic Combinatorics eine Darstellung der Gleichwertigkeit zwischen einem Baum zu finden, die einen Klammerausdruck und einem Serien-Parallel-Diagramm:

wie in einem der Kommentare erwähnt, eine Suche Verfahren wie A* könnte verwendet werden, um den Raum von möglichen Bäumen zu suchen. Die Baumdarstellung des seriell-parallelen Netzwerks ist auch nützlich, um den Source-zu-Sink-Widerstand mit einer einfachen rekursiven Funktion zu bestimmen.