roboforum.ru

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

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

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

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

Сообщение blindman » 20 мар 2013, 17:02

Michael_K писал(а):Тогда формализуйте (и не меняйте условий на ходу :)).


Даны:
- массив S из M положительных вещественных чисел, упорядоченный по возрастанию. Первый элемент массива - 1.0, все элементы меньше 10, элементы не повторяются
- положительное вещественное число R
- целое N большее нуля
- положительное вещественное число e

Найти:
массив D из n вещественных чисел, каждое из которых можно представить в виде s*(10^k), где s - один из элементов массива S, k - произвольное целое, такой, что n<=N, и |R-sum(D)|<=e.
Из множества решений выбрать либо массив минимальной длины, либо массив с минимальным значением |R-sum(D)|. Это критерий оптимизации решения, можно выбрать любой, или оба с произвольным приоритетом - на усмотрение реализатора алгоритма

Составление и последовательной, и параллельной цепочки из резисторов стандартного ряда может быть сведено к этой задаче
Проект [[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 » 20 мар 2013, 18:03

Хм. Широко взяли....
Видимо, кроме переборов тут предложить нечего...
Куда перебирать и чем ограничивать - дело десятое - всегда найдется "плохой" набор данных.
Но попробовать можно.

blindman писал(а):Составление и последовательной, и параллельной цепочки из резисторов стандартного ряда может быть сведено к этой задаче

Ну... OK.
Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

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

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

цель то какая ? найти лучший алгоритм? уметь находить лучшие решения используя любой по качеству (быстродействие/ресурсоемкость) алгоритм?

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

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

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

Единственное, что не сделал - тормоз по количеству резисторов:

Resistance is: 575675677
Next resistor is 56.0 *10^ 7
Path: [560000000]
Resistance is: 15675677
Next resistor is 15.0 *10^ 6
Path: [560000000, 15000000]
Resistance is: 675677
Next resistor is 62.0 *10^ 4
Path: [560000000, 15000000, 620000]
Resistance is: 55677
Next resistor is 51.0 *10^ 3
Path: [560000000, 15000000, 620000, 51000]
Resistance is: 4677
Small resistance left, using search to solve for 4677
Solution: [560000000, 15000000, 620000, 51000, 27.0, 750.0, 3900.0] (7 elements, sum = 575675677.000000, dif = 0.000000)
>>> ================================ RESTART ================================
>>>
Resistance is: 56757567.7
Next resistor is 56.0 *10^ 6
Path: [56000000]
Resistance is: 757567.7
Next resistor is 75.0 *10^ 4
Path: [56000000, 750000]
Resistance is: 7567.7
Small resistance left, using search to solve for 7567.7
Solution: [56000000, 750000, 1.0, 4.7, 62.0, 7500.0] (6 elements, sum = 56757567.700000, dif = 0.000000)

До поры до времени выбираем самые большие сопротивления, потом остаток тупо перебором.
Решает мгновенно, памяти жрет ноль, поскольку используются питоновские итераторы.

Добавлено спустя 3 минуты 48 секунд:
гггггг
Resistance is: 5.67432432432e+23
Next resistor is 56.0 *10^ 22
Path: [560000000000000000000000L]
Resistance is: 7.43243243244e+21
Next resistor is 68.0 *10^ 20
Path: [560000000000000000000000L, 6800000000000000000000L]
Resistance is: 6.32432432437e+20
Next resistor is 62.0 *10^ 19
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L]
Resistance is: 1.24324324367e+19
Next resistor is 12.0 *10^ 18
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L]
Resistance is: 4.32432436734e+17
Next resistor is 43.0 *10^ 16
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L]
Resistance is: 2.4324367338e+15
Next resistor is 24.0 *10^ 14
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L]
Resistance is: 3.24367338045e+13
Next resistor is 30.0 *10^ 12
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L]
Resistance is: 2.43673380454e+12
Next resistor is 24.0 *10^ 11
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L]
Resistance is: 36733804544.0
Next resistor is 36.0 *10^ 9
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L]
Resistance is: 733804544.0
Next resistor is 68.0 *10^ 7
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L, 680000000]
Resistance is: 53804544.0
Next resistor is 51.0 *10^ 6
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L, 680000000, 51000000]
Resistance is: 2804544.0
Next resistor is 27.0 *10^ 5
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L, 680000000, 51000000, 2700000]
Resistance is: 104544.0
Next resistor is 10.0 *10^ 4
Path: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L, 680000000, 51000000, 2700000, 100000]
Resistance is: 4544.0
Small resistance left, using search to solve for 4544.0
Solution: [560000000000000000000000L, 6800000000000000000000L, 620000000000000000000L, 12000000000000000000L, 430000000000000000L, 2400000000000000L, 30000000000000L, 2400000000000L, 36000000000L, 680000000, 51000000, 2700000, 100000, 24.0, 220.00000000000003, 4300.0] (16 elements, sum = 567432432432436700250112.000000, dif = 67108864.000000)
Мой волшебник это я сам. Всю архитектуру программы придумал лично, а ребята помогли воплотить её. Я бы и сам мог написать, но лень учить язык и его конструкции.
Аватара пользователя
dccharacter
 
Сообщения: 4995
Зарегистрирован: 10 дек 2010, 13:16
Откуда: Красногорск МО
прог. языки: C, Python, wiring/processing
ФИО: Андрей

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

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

Duhas писал(а):цель то какая ? найти лучший алгоритм? уметь находить лучшие решения используя любой по качеству (быстродействие/ресурсоемкость) алгоритм?
а то я ради интереса на ГА напишу ) если вариант второй..

Так, поразвлечься :)

Для практического применения у меня есть программа, там ограничены и разрядность исходных данных, и количество резисторов, так что вполне устраивает, без всяких ухищрений. Но интересно было бы найти хороший алгоритм в общем виде.
Проект [[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: Подбор резисторов из ряда

Сообщение dccharacter » 20 мар 2013, 22:09

А вот и депф-лимит

>>> ================================ RESTART ================================
>>>
Resistance is: 56743257543.1
Next resistor is 56.0 *10^ 9
Path: [56000000000L]
Resistance is: 743257543.07
Next resistor is 68.0 *10^ 7
Path: [56000000000L, 680000000]
Resistance is: 63257543.07
Next resistor is 62.0 *10^ 6
Path: [56000000000L, 680000000, 62000000]
Resistance is: 1257543.07
Next resistor is 12.0 *10^ 5
Path: [56000000000L, 680000000, 62000000, 1200000]
Resistance is: 57543.0699997
Next resistor is 56.0 *10^ 3
Path: [56000000000L, 680000000, 62000000, 1200000, 56000]
Resistance is: 1543.06999969
Small resistance left, using search to solve for 1543.06999969
Max depth reached 6 [56000000000L, 680000000, 62000000, 1200000, 56000]
Solution: [56000000000L, 680000000, 62000000, 1200000, 56000, 1500.0] (6 elements, sum = 56743257500.000000, dif = 43.070000)
>>> ================================ RESTART ================================
>>>
Resistance is: 56743257543.1
Next resistor is 56.0 *10^ 9
Path: [56000000000L]
Resistance is: 743257543.07
Next resistor is 68.0 *10^ 7
Path: [56000000000L, 680000000]
Resistance is: 63257543.07
Next resistor is 62.0 *10^ 6
Path: [56000000000L, 680000000, 62000000]
Resistance is: 1257543.07
Next resistor is 12.0 *10^ 5
Path: [56000000000L, 680000000, 62000000, 1200000]
Resistance is: 57543.0699997
Next resistor is 56.0 *10^ 3
Path: [56000000000L, 680000000, 62000000, 1200000, 56000]
Max depth reached 5 [56000000000L, 680000000, 62000000, 1200000, 56000]
Solution: [56000000000L, 680000000, 62000000, 1200000, 56000] (5 elements, sum = 56743256000.000000, dif = 1543.070000)
>>> ================================ RESTART ================================
>>>
Resistance is: 56743257543.1
Next resistor is 56.0 *10^ 9
Path: [56000000000L]
Resistance is: 743257543.07
Next resistor is 68.0 *10^ 7
Path: [56000000000L, 680000000]
Resistance is: 63257543.07
Next resistor is 62.0 *10^ 6
Path: [56000000000L, 680000000, 62000000]
Resistance is: 1257543.07
Next resistor is 12.0 *10^ 5
Path: [56000000000L, 680000000, 62000000, 1200000]
Max depth reached 4 [56000000000L, 680000000, 62000000, 1200000]
Solution: [56000000000L, 680000000, 62000000, 1200000] (4 elements, sum = 56743200000.000000, dif = 57543.070000)
>>> ================================ RESTART ================================
>>>
Resistance is: 56743257543.1
Next resistor is 56.0 *10^ 9
Path: [56000000000L]
Resistance is: 743257543.07
Next resistor is 68.0 *10^ 7
Path: [56000000000L, 680000000]
Resistance is: 63257543.07
Next resistor is 62.0 *10^ 6
Path: [56000000000L, 680000000, 62000000]
Resistance is: 1257543.07
Next resistor is 12.0 *10^ 5
Path: [56000000000L, 680000000, 62000000, 1200000]
Resistance is: 57543.0699997
Next resistor is 56.0 *10^ 3
Path: [56000000000L, 680000000, 62000000, 1200000, 56000]
Resistance is: 1543.06999969
Small resistance left, using search to solve for 1543.06999969
Solution: [56000000000L, 680000000, 62000000, 1200000, 56000, 43.0, 1500.0] (7 elements, sum = 56743257543.000000, dif = 0.070000)
>>>

Добавлено спустя 1 минуту 35 секунд:
Хотя и его можно допилить - сейчас только недолет возможен, а, может быть, перелет даст меньшую ошибку.

Добавлено спустя 28 минут 19 секунд:
Во, решает мгновенно :-р


Resistance is: 5.67432557568e+15
Next resistor is 56.0 *10^ 14
Path: [5600000000000000L]
Resistance is: 7.43255756775e+13
Next resistor is 68.0 *10^ 12
Path: [5600000000000000L, 68000000000000L]
Resistance is: 6.32557567754e+12
Next resistor is 62.0 *10^ 11
Path: [5600000000000000L, 68000000000000L, 6200000000000L]
Resistance is: 1.25575677543e+11
Next resistor is 12.0 *10^ 10
Path: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L]
Resistance is: 5575677543.0
Next resistor is 51.0 *10^ 8
Path: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L]
Resistance is: 475677543.0
Next resistor is 47.0 *10^ 7
Path: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L, 470000000]
Resistance is: 5677543.0
Next resistor is 56.0 *10^ 5
Path: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L, 470000000, 5600000]
Resistance is: 77543.0
Next resistor is 75.0 *10^ 3
Path: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L, 470000000, 5600000, 75000]
Resistance is: 2543.0
Small resistance left, using search to solve for 2543.0
Max depth reached 10 [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L, 470000000, 5600000, 75000]
Solution: [5600000000000000L, 68000000000000L, 6200000000000L, 120000000000L, 5100000000L, 470000000, 5600000, 75000, 150.0, 2400.0] (10 elements, sum = 5674325575677550.000000, dif = -7.000000)
Мой волшебник это я сам. Всю архитектуру программы придумал лично, а ребята помогли воплотить её. Я бы и сам мог написать, но лень учить язык и его конструкции.
Аватара пользователя
dccharacter
 
Сообщения: 4995
Зарегистрирован: 10 дек 2010, 13:16
Откуда: Красногорск МО
прог. языки: C, Python, wiring/processing
ФИО: Андрей

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

Сообщение Michael_K » 20 мар 2013, 22:45

dccharacter писал(а):До поры до времени выбираем самые большие сопротивления

Просто повезло.

Было бы какое-нибудь "990000001234", ваш алгоритм выбрал бы "самые большие" 9900 = 9100 + 750 + 47 + 3
Вместо очевидных 99 = 75 + 24 = 56 + 43

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

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

Сообщение dccharacter » 20 мар 2013, 22:58

Resistance is: 9.90000001234e+11
Solution: [910000000000L, 75000000000L, 4700000000L, 300000000, 1.0, 33.0, 1200.0] (7 elements, sum = 990000001234.000000, dif = 0.000000)

blindman, попробуй свою шайтан машину?

Добавлено спустя 1 минуту 2 секунды:
мне уже надоело, а то можно было бы запустить параллельно этот алгоритм и поиск и на ночь оставить :-)

Добавлено спустя 1 минуту 31 секунду:
Resistance is: 990.0
Small resistance left, using search to solve for 990.0
Solution: [240.0, 750.0] (2 elements, sum = 990.000000, dif = 0.000000)
>>> ================================ RESTART ================================
>>>
Resistance is: 9900.0
Small resistance left, using search to solve for 9900.0
Solution: [2400.0, 7500.0] (2 elements, sum = 9900.000000, dif = 0.000000)
>>> ================================ RESTART ================================
>>>
Resistance is: 99000.0
Next resistor is 91.0 *10^ 3
Path: [91000]
Resistance is: 8000.0
Small resistance left, using search to solve for 8000.0
Solution: [91000, 1200.0, 6800.0] (3 elements, sum = 99000.000000, dif = 0.000000)

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

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

Сообщение Michael_K » 20 мар 2013, 23:11

Блайндман же в самом первом сообщении написал про "жадный алгоритм" - который берет максимальное возможное значение. Что он далек от оптимума, хотя и быстрый, конечно.

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

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

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

Сообщение blindman » 21 мар 2013, 03:11

Resistance is: 9900.0
Solution: [2400.0, 7500.0] (2 elements, sum = 9900.000000, dif = 0.000000)
>>> ================================ RESTART ================================
Resistance is: 99000.0
Solution: [91000, 1200.0, 6800.0] (3 elements, sum = 99000.000000, dif = 0.000000)

Чтобы такого не было, надо либо предварительно нормализовать исходное число, либо понятие "Small" сделать относительным
Проект [[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(?)
ФИО: Андрей Юрьевич

Пред.

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

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

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

cron