roboforum.ru

Технический форум по робототехнике.

Подбор резисторов из ряда

Автомат, адаптивный автомат ... разум

Подбор резисторов из ряда

Сообщение blindman » 19 мар 2013, 12:19

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

Простейший алгоритм - на каждом шаге берем максимальное сопротивление R из ряда, не большее Rx. Затем присваиваем Rx=Rx-R, и повторяем. Останавливаемся при достижении заданной точности, или после N итераций. Хотя это конечно и быстро, но по сравнению с перебором во многих случаях дает либо более длинные цепочки при той же точности, либо меньшую точность при той же длине цепочки.
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Подбор резисторов из ряда

Сообщение elmot » 19 мар 2013, 12:37

Гуглить
Линейное программирование
Симплекс-метод

ЕМНИП

Добавлено спустя 5 минут 19 секунд:
Кстати, у вас перебор оптимизирован? например, когда перебираем цепочки, все время храним "чемпиона" - самую лучшую из найденных. Перебирая остальные, заранее отбрасываем цепочки которые достигли той же длины. Такая простецкая оптимизация очень часто разгоняет переборные алгоритмы в десятки раз.
Аватара пользователя
elmot
 
Сообщения: 5691
Зарегистрирован: 10 ноя 2011, 12:02
Откуда: Turku, Finland
Skype: elmot73
прог. языки: Java и все-все=все
ФИО: Илья

Re: Подбор резисторов из ряда

Сообщение Michael_K » 19 мар 2013, 12:56

"Задача о ранце", не? Ну, вариация...
Вы реализовали "Жадный алгоритм"
Не существует оптимального решения.

Добавлено спустя 43 секунды:
N - какого порядка?

Добавлено спустя 2 минуты 8 секунд:
А может и не "задача о ранце".... Хм...

Добавлено спустя 4 минуты 20 секунд:
elmot писал(а):когда перебираем цепочки, все время храним "чемпиона" - самую лучшую из найденных.

Это называется Метод ветвей и границ http://ru.wikipedia.org/wiki/%D0%9C%D0% ... 0%B8%D1%86
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Подбор резисторов из ряда

Сообщение blindman » 19 мар 2013, 13:15

elmot писал(а):когда перебираем цепочки, все время храним "чемпиона" - самую лучшую из найденных. Перебирая остальные, заранее отбрасываем цепочки которые достигли той же длины.

Да, такое есть. Но все равно скорость очень быстро падает с ростом длины ряда.

Michael_K писал(а):Не существует оптимального решения.

Это понятно.
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Подбор резисторов из ряда

Сообщение Michael_K » 19 мар 2013, 13:21

Какого порядка цифры? Ряд резисторов действительно "стандартный" (в нем можно найти закономерность?)...
Он неограничен в обе стороны? (то есть от пикоом до тераом :))
Если ряд не очень длинный, то, вероятно, имеет смысл дополнить его наборами всех "пар резисторов" (троек, четверок и т.д.)
А потом уже натравить ваш "жадный" алгоритм.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Подбор резисторов из ряда

Сообщение dccharacter » 19 мар 2013, 13:24

Мой волшебник это я сам. Всю архитектуру программы придумал лично, а ребята помогли воплотить её. Я бы и сам мог написать, но лень учить язык и его конструкции.
Аватара пользователя
dccharacter
 
Сообщения: 4995
Зарегистрирован: 10 дек 2010, 13:16
Откуда: Красногорск МО
прог. языки: C, Python, wiring/processing
ФИО: Андрей

Re: Подбор резисторов из ряда

Сообщение Michael_K » 19 мар 2013, 13:25

И чем ограничен перебор? Числом резисторов в цепочке? Точностью попадания в значение?
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Подбор резисторов из ряда

Сообщение dccharacter » 19 мар 2013, 13:30

А какой интерес? Академический? Или практчиеский? Если практический, то плясать надо от:
1) Числа резисторов -> чем меньше, тем лучше
2) Наличия резисторов -> Давно замечено, что всегда не хватает резисторов 1К, 4К7, 10К и т.д., но полно всяких 1К2, 6К2 и т.д.
3) Точности -> Зачем мне подбирать на пуллап связку резисторов 5245Ом, если я могу воткнуть любой в диапазоне 2К-10К???
Мой волшебник это я сам. Всю архитектуру программы придумал лично, а ребята помогли воплотить её. Я бы и сам мог написать, но лень учить язык и его конструкции.
Аватара пользователя
dccharacter
 
Сообщения: 4995
Зарегистрирован: 10 дек 2010, 13:16
Откуда: Красногорск МО
прог. языки: C, Python, wiring/processing
ФИО: Андрей

Re: Подбор резисторов из ряда

Сообщение blindman » 19 мар 2013, 13:33

dccharacter, а ссылка тут при чем тут каким боком?

Michael_K, задача общего характера. То есть ряд бесконечный. И да, он именно стандартный. Уже для E24 размер массива с парами будет внушительным.

Максимальная точность и минимальное число резисторов при количестве резисторов не больше N. Приоритет у точности.

Добавлено спустя 1 минуту 31 секунду:
dccharacter, задача это. математическая :)
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Подбор резисторов из ряда

Сообщение Michael_K » 19 мар 2013, 14:00

Шкала логарифмическая (приблизительно). То есть, грубо, можно подбирать значения "слева направо".
Полный перебор - это алгоритм с отсечениями в небольшом диапазоне (перебор от Rx/2 до Rx - для ряда E24 это "всего" 7 или 8 значений).
Надо покумекать...
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Подбор резисторов из ряда

Сообщение dccharacter » 19 мар 2013, 18:30

короче обычный bsf поиск всегда найдет оптимальное решение с точки зрения и точности и количества резисторов.

Добавлено спустя 1 час 37 секунд:
Без эвристики на больших значениях время поиска стремилось к бесконечности. Приделал простенькую эвристику, которая сперва проверяла резисторы, максимально близкие к искомому значению. Считает почти мгновенно:

Please enter target resistance: 575675677
Solution: 575675677.0 , resistors used: (1.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 2200000.0, 160000.0, 15000.0, 620.0, 56.0)
Error is: 0.0 (0.000000)

Добавлено спустя 3 минуты 27 секунд:
Please enter target resistance: 56757567.7
Solution: 56757567.7 , resistors used: (1.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 9100000.0, 2000000.0, 150000.0, 7500.0, 62.0, 4.7)
Error is: 0.0 (0.000000)
Мой волшебник это я сам. Всю архитектуру программы придумал лично, а ребята помогли воплотить её. Я бы и сам мог написать, но лень учить язык и его конструкции.
Аватара пользователя
dccharacter
 
Сообщения: 4995
Зарегистрирован: 10 дек 2010, 13:16
Откуда: Красногорск МО
прог. языки: C, Python, wiring/processing
ФИО: Андрей

Re: Подбор резисторов из ряда

Сообщение Michael_K » 19 мар 2013, 18:41

dccharacter писал(а):короче обычный bsf поиск всегда найдет оптимальное решение

Вы как отличаете оптимальное решение от неоптимального? :)
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Подбор резисторов из ряда

Сообщение dccharacter » 19 мар 2013, 19:42

по количеству резисторов. 1 резистор = 1 единица стоимости.
Конечно, можно задать стоимость резисторам (например, соответствующую реальной стоимости или величине, обратной количеству имеющихся резисторов конкретного номинала)
Все это лишь усложнит задачу с точки зрения выработки функции оценки
Мой волшебник это я сам. Всю архитектуру программы придумал лично, а ребята помогли воплотить её. Я бы и сам мог написать, но лень учить язык и его конструкции.
Аватара пользователя
dccharacter
 
Сообщения: 4995
Зарегистрирован: 10 дек 2010, 13:16
Откуда: Красногорск МО
прог. языки: C, Python, wiring/processing
ФИО: Андрей

Re: Подбор резисторов из ряда

Сообщение Duhas » 19 мар 2013, 20:10

blindman писал(а): То есть ряд бесконечный. )

а я хотел ГА предложить... если на конечных рядах работать..
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Аватара пользователя
Duhas
 
Сообщения: 6338
Зарегистрирован: 15 сен 2007, 13:03
Откуда: Красноярск
прог. языки: ASM(МК), C(PC)
ФИО: Гагарский Андрей Александрович

Re: Подбор резисторов из ряда

Сообщение Madf » 19 мар 2013, 20:24

в андроид маркете есть готовые приложения (наша и забугорная)
Madf
 
Сообщения: 3298
Зарегистрирован: 03 янв 2012, 12:55
Откуда: Москва
прог. языки: VB6, BASCOM, ASM...

След.

Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4