Какой алгоритм я использую для вычисления напряжения в комбинированной схеме?

Я пытаюсь программно рассчитать изменения напряжения в очень большой цепи.

* Этот вопрос может показаться ориентированным на электронику, но это больше о применении алгоритма по набору данных.

Чтобы все было просто,
вот полная схема, с уже рассчитанными напряжениями:

Мне изначально дано напряжение батареи и сопротивления:

Проблема заключается в том, что напряжение рассчитывается по-разному между параллельными и последовательными схемами.
Несколько аналогичный вопрос, заданный по SO.

Некоторые формулы:

When resistors are in parallel:
Rtotal = 1/(1/R1 + 1/R2 + 1/R3 ... + 1/Rn)

When resistors are in series:
Rtotal = R1 + R2 + R3 ... + Rn

Закон Ома:

V = IR
I = V/R
R = V/I

V is voltage (volts)
I is current (amps)
R is resistance (ohms)

Каждый учебник, который я нашел в Интернете, состоит из людей, которые концептуально группируют параллельные схемы, чтобы получить общее сопротивление, а затем используя это сопротивление для расчета сопротивления в серии.

Это хорошо для небольших примеров, но трудно получить алгоритм из него для крупномасштабных схем.

Мой вопрос:
Учитывая матрицу всех полных путей,
есть ли способ для меня рассчитать все падения напряжения?

В настоящее время я имею систему как структуру данных графа.
Все узлы представлены (и могут быть просмотрены) номером id.

Итак, для примера выше, если я запускаю обходы, я верну список таких путей:

[[0,1,2,4,0]
,[0,1,3,4,0]]

Каждый номер может использоваться для получения фактического node и соответствующих ему данных. Какие преобразования/алгоритмы мне нужны для выполнения этого набора данных?

Очень вероятно, что части схемы будут составными, и эти составные секции могут оказаться параллельными или рядами с другими составными участками.

Я думаю, что моя проблема сродни этому:
http://en.wikipedia.org/wiki/Series-parallel_partial_order

Ответ 1

Некоторые схемы даже не анализируются в терминах серий и параллелей, например, схема, которая включает в себя ребра куба (там есть некоторый код в нижней части этой веб-страницы, которая может быть полезна, я не смотрел на нее). Другим примером, который не может быть проанализирован в последовательный/параллельный, является форма пентагона/пентаграммы.

Более надежное решение, чем размышление о рядах и параллелях, заключается в использовании законов Кирхгофа.

Вам нужно сделать переменные для токов в каждом линейном разделе схемы.
Примените действующий закон Кирхгофа (KCL) к узлам, где линейные сечения.
Применить закон напряжения Кирхгофа (KVL) на столько же как вы можете найти.
Используйте гауссово исключение для решения проблемы полученная линейная система уравнений.

Трудная часть - это идентификация циклов. В приведенном примере три цикла: через аккумулятор и левый резистор, аккумулятор и правый резистор, а также через левый и правый резисторы. Для планарных схем не слишком сложно найти полный набор циклов; для трехмерных схем это может быть трудно.

Вам действительно не нужны все циклы. В приведенном выше примере два будут достаточно (соответствующие двум ограниченным областям, в которые схема делит плоскость). Тогда у вас есть три переменные (токи в трех линейных частях схемы) и три уравнения (сумма токов в верхней части node, где встречаются три линейных сегмента, а напряжение падает примерно на два цикла). Этого достаточно для решения системы для токов путем исключения Гаусса, тогда вы можете рассчитать напряжения от токов.

Если вы выбрасываете слишком много уравнений (например, токи на обоих узлах вашего примера и напряжения в течение трех циклов вместо двух), все будет по-прежнему работать: устранение Гаусса просто устранит избыточность, и вы все равно получите уникальный, правильный ответ. Реальная проблема заключается в том, что у вас слишком мало уравнений. Например, если вы используете KCL на двух узлах вашего примера и KVL всего за один цикл, у вас будет три уравнения, но одно будет избыточным, так что у вас действительно будет только два независимых уравнения, чего недостаточно. Поэтому я бы сказал, бросьте каждое уравнение, которое вы можете найти, и дайте гауссовскому устранению его сортировку.

И, надеюсь, вы можете ограничить планарные схемы, для которых легко найти хороший набор циклов. В противном случае вам понадобится алгоритм перечисления цикла цикла. Я уверен, вы можете найти его, если вам это нужно.

Ответ 2

используйте алгоритм максимального потока (Дейкстра - ваш друг).

http://www.cs.princeton.edu/courses/archive/spr04/cos226/lectures/maxflow.4up.pdf

Вы притворяетесь перед проблемой потока воды (ну, на самом деле это проблема потока). Вы должны вычислить поток воды на каждый сегмент (ток). Затем вы можете легко вычислить падение напряжения (давление воды) на каждом резисторе.

Ответ 3

Я думаю, что путь сюда будет примерно таким:

Сортируйте все ваши пути в группы одинаковой длины.
Пока существует более одной группы, выберите группу с наибольшей длиной и:
2а. Найдите два пути с разницей одного элемента.
2b. "Объединить" их в путь с длиной, меньшей на единицу - слияние зависит от фактических элементов, которые отличаются.
2с. Добавьте новый путь в соответствующую группу.
2d. Если есть только пути с разницей в несколько раз, объедините различные элементы, чтобы у вас был только один элемент между путями.
2е. Когда осталось только один элемент, найдите элемент из "нижнего" (= длина меньше) с минимальными различиями и слейте элемент для соответствия.
Когда одна группа остается с несколькими элементами, продолжайте делать # 2, пока одна группа не останется с одним элементом.
Вычислить значение этого элемента напрямую.

Это очень оригинально, но я думаю, что основная идея понятна. Любые улучшения приветствуются.